US 8,300,807 B2Granted

Computing isogenies between genus-2 curves for cryptography

AssigneeMicrosoft Corporation

InventorsReinier M. Broker, Kristin E. Lauter, David Gruenewald

Life of this patent

Estimating the term…

Loading patent…

Abstract

This cryptographic curve generation technique provides a faster way of constructing a genus 2 curve. The technique provides a procedure to compute isogenies between genus 2 curves over finite fields. Instead of looping over possible roots, as is typically done when solving Igusa class polynomials, the technique only finds one root and then applies the isogenies to find the others. The technique computes a set of polynomials that define all isogenies. To do this, for a given root of an Igusa class polynomial over a finite field, the technique computes a value of a small modular function ƒ. To the value of this function ƒ, the technique applies an isogeny to find an isogenous ƒ-value. The technique then transforms the ƒ-value back into an Igusa value. Once the Igusa class polynomials are solved they can be used to generate a genus 2 curve which can be used in cryptographic applications.

Claims19

Dependent claims

A computer-implemented process for generating a curve for use in cryptography, comprising:

using a computer to perform the steps of:
selecting a suitable large prime number from a predefined set of large prime numbers;
generating an Igusa class polynomial over the rational numbers from Igusa class polynomials modulo small primes, comprising for a predefined set of small prime numbers,
(a) selecting a small prime number from a predefined set of small prime numbers;
(b) performing a single random search to identify a first root of an Igusa class polynomial modulo the selected small prime number;
(c) computing a value of a small modular function using the first root;
(d) applying an isogeny to the small modular function value to find a new value of the small modular function;
(e) using the new value of the small modular function to find the next root of the Igusa class polynomial modulo the selected small prime number;
(f) checking to determine if all of the roots of the Igusa class polynomial modulo the selected small prime are computed;
and
(g) if not, repeating process actions (d) through (f) until all roots are computed;
(h) constructing a new Igusa class polynomial from the computed roots;
(i) adding the new Igusa class polynomial to a set of Igusa class polynomials;
and
applying a Chinese remainder approach to construct an Igusa class polynomial over the rational numbers from the computed set of Igusa class polynomials modulo the small primes;
using the selected large prime number and the Igusa class polynomial over the rational numbers to compute a root of the Igusa class polynomial modulo the selected large prime number;
using the computed root to generate a genus 2 curve;
and
using the genus curve for a cryptographic application.

16 more elements

A computer-implemented process for generating a curve for use in cryptography, comprising:

using a computer to perform the steps of:
selecting a suitable large prime number from a predefined set of large prime numbers;
computing an Igusa class polynomial over the rational numbers from a set of Igusa class polynomials computed modulo a set of small primes, comprising the following process actions:
for a predefined set of small prime numbers,
(a) selecting a small prime number from the predefined set of small prime numbers;
(b) identifying a first root of an Igusa class polynomial modulo the selected small prime;
(c) computing a value of a small modular function using the first root;
(d) applying an isogeny to the small modular function value to find a new value of the small modular function;
(e) using the new value of the small modular function to find the next root of the Igusa class polynomial modulo the selected small prime;
(f) checking to determine if all of the roots of the Igusa class polynomial modulo the selected small prime are computed;
and
(g) if all roots are not computed, repeating process actions (d) through (f) until all roots are computed;
(h) constructing a new Igusa class polynomial from the computed roots;
(i) adding the new Igusa class polynomial to a set of lgusa class polynomials;
applying a Chinese remainder approach to construct an Igusa class polynomial over the rational numbers, from the computed set of Igusa class polynomials modulo the small primes;
using the selected large prime number and the Igusa class polynomial over the rational numbers to compute a root of the lgusa class polynomial modulo the selected large prime number;
using the computed root to generate a genus 2 curve;
and
using the genus curve for a cryptographic application.

16 more elements

A system for generating a curve for use with cryptography, comprising:

a general purpose computing device;
a computer program comprising program modules executable by the general purpose computing device, wherein the computing device is directed by the program modules of the computer program to,
for each of a set of small primes,
(a) input a small prime number selected from a predefined set of small prime numbers;
(b) perform a single random search to identify a first root of an Igusa class polynomial modulo the selected small prime number;
(c) compute a value of a small modular function using the first root;
(d) apply an isogeny to the small modular function value to find a new value of the small modular function;
(e) use the new value of the small modular function to find the next root of the Igusa class polynomial;
(f) make a check to determine if all roots of the Igusa class polynomial are computed and repeating (d)-(f) until all roots are computed;
(g) once all roots are computed, construct the Igusa class polynomial from the computed roots;
(h) add the constructed Igusa class polynomial to a set of constructed Igusa class polynomials;
(i) apply a combining approach to find an Igusa class polynomial over the rational numbers using the set of constructed Igusa class polynomials;
randomly select a large prime number selected from a predefined set of large prime numbers;
find a root of the Igusa class polynomial modulo the selected large prime;
and
use the root of the Igusa class polynomial modulo the selected large prime to find a genus 2 curve to be used in an application.

13 more elements

Dependencies are inferred from the claim text.