Computing endomorphism rings of Abelian surfaces over finite fields

1. A method at least partially implemented by a computing device, the method comprising:

probabilistically computing, by the computing device, an endomorphism ring of an Abelian surface over a finite field, wherein probabilistically computing the endomorphism ring comprises probabilistically determining a field of definition over which n-torsion of the Abelian surface is defined independent of locating a group structure over respective ones of multiple extension fields;

constructing, by the computing device, a genus-2 curve based on results of probabilistically computing the endomorphism ring;

generating a key by employing the genus-2 curve for key generation in respective encryption or decryption operations of a cryptosystem; and

encrypting or decrypting data with the key in the respective encryption or decryption operations of the cryptosystem.

2. The method of claim 1 , wherein probabilistically determining the field of definition further comprises:

multiplying random points by scalar multiples to obtain a set of results; and

for each of the results, evaluating the result to determine if the result is an n-torsion point.

3. The method of claim 2 , wherein the method further comprises:

repeating the evaluating until it is probable that evaluated ones of the random points span the n-torsion; and

providing the field of definition for use to compute the endomorphism ring.

4. The method of claim 1 , wherein the method further comprises:

identifying an action of Frobenius on the n-torsion; and

evaluating respective random points of a Jacobian over the field of definition to determine if the points have the action of Frobenius; and

probabilistically determining if the Jacobian has an element of a ring of integers as one of its endomorphisms, the element corresponding to the action of Frobenius on the n-torsion.

5. A tangible computer-readable memory comprising computer-program instructions executable by a processor that when executed perform operations comprising:

probabilistically computing an endomorphism ring of an Abelian surface over a finite field, wherein probabilistically computing the endomorphism ring comprises probabilistically determining a field of definition over which n-torsion of the Abelian surface is defined independent of locating a group structure over respective ones of multiple extension fields;

computing class polynomials for quartic CM fields, the class polynomials being Igusa class polynomials that are based on the probabilistically computed endomorphism ring of the Abelian surface over the finite field, wherein roots of the class polynomials are utilized to generate a genus-2 curve for cryptographic application; and

generating a key in the cryptographic application, basing the key, at least in part, on the genus-2 curve, wherein the cryptographic application includes at least one of encrypting data or decrypting data with the key.

6. The computer-readable memory of claim 5 , wherein the computer-program instructions for probabilistically determining the field of definition further comprise instructions for:

multiplying random points by scalar multiples to obtain a set of results; and

for each of the results, evaluating the result to determine if the result is an n-torsion point.

7. The computer-readable memory of claim 5 , wherein the computer-program instructions for probabilistically determining the field of definition further comprises instructions for:

identifying an action of Frobenius on the n-torsion; and

evaluating respective random points of a Jacobian over the field of definition to probabilistically determine if the points have the action; and

probabilistically determining if said Jacobian has an element of a ring of integers as one of its endomorphisms, the element corresponding to the action of Frobenius on the n-torsion.

8. The computer-readable memory of claim 7 , wherein the computerizing program instructions further comprise instructions for repeating operations associated with the evaluating until it is probable that evaluated ones of the random points span the n-torsion.

9. The computer-readable memory of claim 5 , wherein the computer-program instructions further comprise instructions for constructing the genus-2 from respective ones of the invariants.

10. A computing device comprising:

a processor; and

a memory coupled to the processor, the memory comprising computer-program instructions executable by the processor for performing operations comprising:

probabilistically determining a field of definition over which n-torsion of an Abelian surface is defined, wherein the probabilistically determining the field of definition is independent of determining group structures of the Abelian surface over extension fields;

utilizing the field of definition to generate genus-2 curves for cryptographic application; and

generating a key from, at least in part, the genus-2 curves in the cryptographic application, wherein the cryptographic application includes at least one of encrypting data or decrypting data with the key.

11. The computing device of claim 10 , wherein the computer-program instructions for probabilistically determining the field of definition further comprise instructions for:

multiplying random points by scalar multiples to obtain a set of results;

for each of the results, evaluating the result to determine if the result is an n-torsion point; and

determining whether an identity of a Jacobian is obtained in the set of results of n-torsion points.

12. The computing device of claim 10 , wherein the computer-program instructions further comprise instructions for probabilistically computing an endomorphism ring of the Abelian surface over the finite field in view of the field of definition.

13. The computing device of claim 12 , wherein the computer-program instructions for probabilistically computing the endomorphism ring further comprise instructions for:

probabilistically identifying an action of Frobenius on the n-torsion; and

evaluating respective random points of a Jacobian over the field of definition to probabilistically determine if the points have the action.

14. The computing device of claim 10 , wherein the computer-program instructions further comprise instructions for:

constructing a genus-2 curve from invariants of Igusa class polynomials generated using the probabilistic computation of endomorphism rings; and

encrypting the data with point operations based on a Jacobian of the genus-2 curve, the data for subsequent decryption in presentation to a user.

15. The computing device of claim 10 , wherein the computer-program instructions further comprise instructions for:

receiving inputs comprising:

a prime power n=l d ,

an Abelian variety A defined over a finite field F p (p≠l), and

a basis {g 1 , g 2 , g 3 , g 4 } of A[n] (defined over some extension field F q of F p ); and

responsive to the inputs, outputting two matrices F,VεGL 4 (Z/nZ) representing the Frobenius and Verschiebung endomorphisms of the Abelian variety A with respect to the basis.

16. The computing device of claim 10 , wherein the computer-program instructions further comprise instructions for probabilistically identifying a basis of the field of definition of the n-torsion to check the action of a Frobenius matrix.

17. The method of claim 1 , wherein the method further comprises:

receiving inputs comprising:

a Jacobian of a genus-2 curve over the finite field;

an algebraic number corresponding to a Frobenius endomorphism of the Jacobian over the finite field;

probabilistically computing an action of Frobenius on the n-torsion of the Abelian surface over the finite field.

18. The method of claim 1 , wherein the method further comprises:

receiving inputs comprising:

a prime power n=l d ,

an Abelian variety A defined over a finite field F p (p≠l), and

a basis {g 1 , g 2 , g 3 , g 4 } of A[n] (defined over some extension field F q of F p ); and

responsive to the inputs, outputting two matrices F,VεGL 4 (Z/nZ) representing the Frobenius and Verschiebung endomorphisms of the Abelian variety A with respect to the basis.

19. The computer-readable memory of claim 5 , wherein the computer-program instructions further comprise instructions for:

receiving inputs comprising:

a Jacobian of a genus-2 curve over the finite field;

an algebraic number corresponding to a Frobenius endomorphism of the Jacobian over the finite field;

probabilistically computing an action of Frobenius on the n-torsion of the Abelian surface over the finite field.

20. The computing device of claim 10 , wherein the computer-program instructions further comprise instructions for:

receiving inputs comprising:

a Jacobian of a genus-2 curve over the finite field;

an algebraic number corresponding to a Frobenius endomorphism of the Jacobian over the finite field;

probabilistically computing an action of Frobenius on the n-torsion of the Abelian surface over the finite field.