Hashing byte streams into elements of the Shafarevich-Tate group of an abelian variety

• US 7,707,426 B2
• Filed: 10/28/2005
• Issued: 04/27/2010
• Est. Priority Date: 12/14/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jetchev, Dimitar Petkov, Lauter, Kristin E.
• Primary Examiner(s): Kim; Jung
• Assistant Examiner(s): Okeke; Izunna
• Application Number:
  US11/260,950
• Publication Number:
  US 20070076865A1
• Time in Patent Office: 1,642 Days
• Field of Search: 713/176, 713/180
• US Class Current: 713/180
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

Systems and methods for cryptographically processing data as a function of a Cassels-Tate pairing are described. In one aspect, a Shafarevich-Tate group is generated from an abelian variety. A Cassels-Tate pairing is determined as a function of elements of the Shafarevich-Tate group. Data is then cryptographically processed as a function of the Cassels-Tate pairing by using Kolyvagin cohomology classes to hash the data into an element of the Shafarevich-Tate group.

Claims

1. A computer-implemented method comprising:

generating, via a computer, a Shafarevich-Tate group from an abelian variety;

determining, via the computer, a Cassels-Tate pairing based on elements of the Shafarevich-Tate group;

cryptographically processing, via the computer, data based on the Cassels-Tate pairing by hashing the data into an element of the Shafarevich-Tate group using Kolyvagin cohomology classes; and

communicating, by the computer, the cryptographically processed data that includes signed data and a calculated signature that is used to verify the signed data based on a calculated Cassels-Tate pairing.

2. The method of claim 1, wherein the cohomology group is associated to an abelian variety selected from an elliptic curve or a Jacobian variety of a higher genus curve.

3. The method of claim 1, wherein the Cassels-Tate pairing is a sum of local pairings.

4. The method of claim 1, wherein the cryptographic processing is a signature-based verification scheme or an identity-based encryption scheme.

5. The method of claim 1, wherein the cryptographic processing selects a public element x from the Shafarevich-Tate group of the dual of A, and messages M are hashed into the Shafarevich-Tate group of A.

6. The method of claim 1, wherein the cryptographic processing is based on the Shafarevich-Tate group and a dual of A, wherein roles of A and the dual of A are switched.

7. The method of claim 1, wherein cryptographically processing further comprises signing the data by hashing the data with hashing function h acting on data space {0,1}*, the data being hashed into III(Â

/K), wherein {0,1}* represents a set of bit-strings of a length.

8. The method of claim 1, wherein cryptographically processing further comprises:

selecting an element x from the Shafarevich-Tate group;

selecting a random number r;

composing the element x, r times with itself to generate a public key; and

wherein r is maintained as a secret.

9. The method of claim 1, wherein cryptographically processing further comprises:

selecting an element x from the Shafarevich-Tate group;

generating a public key equal to the r-th multiple of the element x, r being the secret; and

publishing the element x, the public key r*x, wherein r*x denotes the r^th multiple of x, and the abelian variety so that the data can be decrypted or verified by an independent entity.

10. The method of claim 1, wherein the Cassels-Tate pairing is evaluated on different inputs and their values are compared, and wherein the method further comprises:

receiving a public key generated from a secret determined as a function of an element of the Shafarevich group; and

decrypting or verifying the data as a function of the public key and the Cassels-Tate pairing.

11. The method of claim 1, wherein the signature σ

=r*h(M) and message M are transmitted, and wherein the method further comprises verifying the data by;

(a) constructing the Kolyvagin cohomology classes to produce provably non-trivial elements;

(b) hashing the data using the non-trivial elements;

(c) computing a second Cassels-Tate pairing using hashed data, CT(r*x,h(M)); and

(d) comparing the second Cassels-Tate pairing with the first Cassels-Tate pairing, CT(x,σ

).

12. The method of claim 1, wherein cryptographically processing further comprises signing the data by:

computing a hash h of the data such that h(the data) is an element of III(Â

/K);

determining an rth multiple r*h(the data), wherein r is a random number; and

evaluating the Cassels-Tate pairing to obtain signature σ

=r*h(M).

13. A computer-implemented method comprising:

generating, via a computer, a Shafarevich-Tate group from an abelian variety;

determining, via the computer, a Cassels-Tate pairing based on elements of the Shafarevich-Tate group;

cryptographically processing, via the computer, data based on the Cassels-Tate pairing by;

selecting a public element x from the Shafarevich-Tate group of a dual of A; and

hashing a messages M into the Shafarevich-Tate group of A using a Kolyvagin construction; and

communicating, via the computer, the cryptographically processed data that includes signed data and a calculated signature that is used to verify the signed data based on a calculated Cassels-Tate pairing.

14. The method of claim 13, wherein the cohomology group is associated to an abelian variety selected from an elliptic curve or a Jacobian variety of a higher genus curve.

15. The method of claim 13, wherein the Cassels-Tate pairing is a sum of local pairings.

16. The method of claim 13, wherein the cryptographic processing is a signature-based verification scheme or an identity-based encryption scheme.

17. The method of claim 13, wherein the cryptographic processing is based on the Shafarevich-Tate group and a dual of A, wherein roles of A and the dual of A are switched.

18. The method of claim 13, wherein cryptographically processing further comprises:

selecting an element x from the Shafarevich-Tate group;

selecting a random number r

composing the element x, r times with itself to generate a public key; and

wherein r is a maintained as a secret.

19. The method of claim 13, wherein cryptographically processing further comprises:

selecting an element x from the Shafarevich-Tate group;

composing the element x, r times with itself to generate a public key, r being the secret; and

publishing the element x, the public key r*x and the abelian variety so that the data can be decrypted or verified by an independent entity.

20. A computing device comprising:

a processor; and

a memory encoded with computer-executable instructions that, when executed, configure the computing device to perform operations comprising;

generating a Shafarevich-Tate group from a cohomology group;

determining a Cassels-Tate pairing based on elements of the Shafarevich-Tate group;

cryptographically processing data based on the Cassels-Tate pairing by hashing the data into an element of the Shafarevich-Tate group using Kolyvagin cohomology classes; and

communicating the cryptographically processed data that includes signed data and a calculated signature that is used to verify the signed data based on a calculated Cassels-Tate pairing.