Tate pairing techniques for use with hyperelliptic curves

{
  "publication_number": "US2005025311A1",
  "country": "US",
  "kind": "A1",
  "title": "Tate pairing techniques for use with hyperelliptic curves",
  "abstract": "Methods and apparati are provided for determining a “Squared Tate pairing” for hyperelliptic curves and using the results so support at least one cryptographic process. The improved techniques provide increased efficiency and an alternative method to the conventional method of implementing the Tate pairing for Jacobians of hyperelliptic curves. With the Squared Tate pairing for hyperelliptic curves, one may obtain a significant speed-up over a contemporary implementation of the Tate pairing for hyperelliptic curves. The Squared Tate pairing for hyperelliptic curves can be substituted for the Tate pairing for hyperelliptic curves in any applicable cryptographic application.",
  "claims": [
    "1. A method comprising: determining at least one Squared Tate pairing for at least one hyperelliptic curve; and cryptographically processing selected information based on said determined Squared Tate pairing.",
    "2. The method as recited in claim 1, wherein said Squared Tate pairing is defined for at least one hyperelliptic curve C of genus g over a field K.",
    "3. The method as recited in claim 1, wherein determining said Squared Tate pairing further includes: forming a mathematical chain for m, wherein m is a positive integer and an m-torsion element D is fixed on Jacobian of said hyperelliptic curve C.",
    "4. The method as recited in claim 3, wherein said mathematical chain includes a mathematical chain selected from a group of mathematical chains comprising an addition chain and an addition-subtraction chain.",
    "5. A computer-readable medium having computer-implementable instructions for causing at least one processing unit to perform acts comprising: calculating at least one Squared Tate pairing for at least one hyperelliptic curve; and cryptographically processing selected information based on said determined Squared Tate pairing.",
    "6. The computer-readable medium as recited in claim 5, wherein said Squared Tate pairing is defined for at least one hyperelliptic curve C of genus g over a field K.",
    "7. The computer-readable medium as recited in claim 5, wherein determining said Squared Tate pairing further includes: forming a mathematical chain for m, wherein m is a positive integer and an m-torsion element D is fixed on Jacobian of said hyperelliptic curve C.",
    "8. The computer-readable medium as recited in claim 7, wherein said mathematical chain includes a mathematical chain selected from a group of mathematical chains comprising an addition chain and an addition-subtraction chain.",
    "9. An apparatus comprising: memory configured to store information suitable for use with using a cryptographic process; logic operatively coupled to said memory and configured to calculate at least one Squared Tate pairing for at least one hyperelliptic curve, and at least partially support cryptographic processing of selected stored information based on said determined Squared Tate pairing.",
    "10. The apparatus as recited in claim 9, wherein said Squared Tate pairing is defined for at least one hyperelliptic curve C of genus g over a field K.",
    "11. The apparatus as recited in claim 9, wherein said logic is further configured to form a mathematical chain for m, wherein m is a positive integer and an m-torsion element D is fixed on Jacobian of said hyperelliptic curve C.",
    "12. The apparatus as recited in claim 11, wherein said mathematical chain includes a mathematical chain selected from a group of mathematical chains comprising an addition chain and an addition-subtraction chain.",
    "13. A method comprising: determining a hyperelliptic curve C of genus g over a field K and a positive integer m; determining a Jacobian J(C) of said hyperelliptic curve C, and wherein each element D of J(C) contains a representative of the form A−g(P 0), where A is an effective divisor of degree g; and determining a plurality of functions h j,D that are iterative building blocks for the formation of a function h m,D in order to evaluate ν m which is a Squared Tate pairing.",
    "14. The method as recited in claim 13, wherein said hyperelliptic curve C is over a field not of characteristic 2.",
    "15. The method as recited in claim 13, wherein for at least one element D of J(C), a representative for iD will be A i −g(P 0), where A i is effective of degree g.",
    "16. The method as recited in claim 13, wherein if P=(x, y) is a point on said hyperelliptic curve C, then −P denotes a point −P:=(x, −y), and wherein if a point P=(x, y) occurs in A and y≠0, then −P:=(x,−y) does not occur in A and a representative for identity will be g(P 0).",
    "17. The method as recited in claim 16, further comprising: to a representative A i, associating two polynomials (a i, b i) which represent a divisor.",
    "18. The method as recited in claim 16, further comprising: determining D as an m-torsion element of J(C).",
    "19. The method as recited in claim 18, further comprising: if j is an integer, then h j,D =h j,D (X) denoting a rational function on C with divisor (h j,D)=jA 1 −A j −((j−1)g)(P 0).",
    "20. The method as recited in claim 18, wherein D is an m-torsion divisor and A m =g(P 0), and a divisor of h m,D is (h m,D)=mA 1 −mg(P 0). 21 The method as recited in claim 18, wherein h m,D is well-defined up to a multiplicative constant.",
    "22. The method as recited in claim 18, further comprising: evaluating h m,D at a degree zero divisor E on said hyperelliptic curve C, wherein E does not contain P 0 and E is prime to A i.",
    "23. The method as recited in claim 18, wherein E is prime to A i for all i in an addition-subtraction chain for m.",
    "24. The method as recited in claim 22, wherein given A i, A j, and A i+j, further comprising determining a function u i,j such that a divisor of u i,j is (u i,j)=A i +A j −A i+j −g(P 0).",
    "25. The method as recited in claim 22, further comprising: evaluating h j,D (E) such that when j=1, h 1,D is 1.",
    "26. The method as recited in claim 22, further comprising: given A i, A j, h i,D (E) and h j,D (E), evaluating u i,j to be (u i,j)=A i +A j −A i+j −g(P 0),, and h i+j,D (E)=h i,D (E)h j,D (E)u i,j (E).",
    "27. The method as recited in claim 13, further comprising: determining a function (u i,j)=A i +A j −A i+j −g(P 0).",
    "28. The method as recited in claim 27, wherein g=2 and (u i,j)=A i +A j −A i+j −2(P 0) is determined as follows u i, j ⁡ (X):= a new ⁡ (x ⁡ (X)) b new ⁡ (x ⁡ (X)) + y ⁡ (X) * d ⁡ (x ⁡ (X)), if the degree of a new is greater than 2, otherwise, u i,j is determined as u i,j (X):=d(x(X)), wherein d(x) is the greatest common divisor of three polynomials (a i (x), a j (x), b i (x)+b j (x)).",
    "29. The method as recited in claim 13, further comprising: determining a Squared Tate pairing for a hyperelliptic curves ν m, for an m-torsion element D of a Jacobian J(C) and an element E of J(C), with representatives (P 1)+(P 2)+... +(P g)−g(P 0) and (Q 1)+(Q 2)+... +(Q g)−g(P 0), respectively, with each P i and each Q j on the curve C, with P i not equal to ±Q j for all i,j, determining that v m ⁡ (D, E):= (h m, D ⁡ ((Q 1) - (- Q 1) + (Q 2) - (- Q 2) + … + (Q g) - (- Q g)) q - 1 m.",
    "30. A computer-readable medium having computer-implementable instructions for causing at least one processing unit to perform acts comprising: determining a hyperelliptic curve C of genus g over a field K and a positive integer m; determining a Jacobian J(C) of said hyperelliptic curve C, and wherein each element D of J(C) contains a representative of the form A−g(P 0), where A is an effective divisor of degree g; and determining a plurality of functions h j,D that are iterative building blocks for the formation of a function h m,D in order to evaluate ν m which is a Squared Tate pairing.",
    "31. The computer-readable medium as recited in claim 30, wherein said hyperelliptic curve C is not of characteristic 2.",
    "32. The computer-readable medium as recited in claim 30, wherein for at least one element D of J(C), a representative for iD will be A i −g(P 0), where A i is effective of degree g.",
    "33. The computer-readable medium as recited in claim 30, wherein if P=(x, y) is a point on said hyperelliptic curve C, then −P denotes a point −P:=(x, −y), and wherein if a point P=(x, y) occurs in A and y≠0, then −P:=(x,−y) does not occur in A and a representative for identity will be g(P 0).",
    "34. The computer-readable medium as recited in claim 33, further comprising: to a representative A i, associating two polynomials (a i, b i) which represent a divisor.",
    "35. The computer-readable medium as recited in claim 33, further comprising: determining D as an m-torsion element of J(C).",
    "36. The computer-readable medium as recited in claim 35, further comprising: if j is an integer, then h j,D=h j,D (X) denoting a rational function on C with divisor (h j,D)=jA 1 −A j −((j−1)g)(P 0).",
    "37. The computer-readable medium as recited in claim 35, wherein D is an m-torsion divisor and A m =g(P 0), and a divisor of h m,D is (h m,D)=mA 1 −mg(P 0). 38 The computer-readable medium as recited in claim 35, wherein h m,D is well-defined up to a multiplicative constant.",
    "39. The computer-readable medium as recited in claim 35, further comprising: evaluating h m,D at a degree zero divisor E on said hyperelliptic curve C, wherein E does not contain P 0 and E is prime to A i.",
    "40. The computer-readable medium as recited in claim 35, wherein E is prime to A i for all i in an addition-subtraction chain for m.",
    "41. The computer-readable medium as recited in claim 39, wherein given A i, A j, and A i+j, further comprising determining a function u i,j such that a divisor of u i,j is (u i,j)=A i +A j −A i+j −g(P 0).",
    "42. The computer-readable medium as recited in claim 39, further comprising: evaluating h j,D (E) such that when j=1, h 1,D is 1.",
    "43. The computer-readable medium as recited in claim 39, further comprising: given A i, A j, h i,D (E) and h j,D (E), evaluating u i,j to be (u i,j)=A i +A j −A i+j −g(P 0),, and h i+j,D (E)=h i,D (E)h j,D (E)u i,j (E).",
    "44. The computer-readable medium as recited in claim 30, further comprising: determining a function (u i,j)=A i +A j −A i+j −g(P 0).",
    "45. The computer-readable medium as recited in claim 44, wherein g=2 and (u i,j)=A i +A j −A i+j −2(P 0) is determined as follows u i, j ⁡ (X):= a new ⁡ (x ⁡ (X)) b new ⁡ (x ⁡ (X)) + y ⁡ (X) * d ⁡ (x ⁡ (X)), if the degree of a new is greater than 2, otherwise, u i,j is determined as u i,j (X):=d(x(X)), wherein d(x) is the greatest common divisor of three polynomials (a i (x), a j (x), b i (x)+b j (x)).",
    "46. The computer-readable medium as recited in claim 30, further comprising: determining a Squared Tate pairing for a hyperelliptic curves ν m, for an m-torsion element D of a Jacobian J(C) and an element E of J(C), with representatives (P 1)+(P 2)+... +(P g)−g(P 0) and (Q 1)+(Q 2)+... +(Q g)−g(P 0), respectively, with each P i and each Q j on the curve C, with P i not equal to ±Q j for all i,j, determining that v m ⁡ (D, E):= (h m, D ⁡ ((Q 1) - (- Q 1) + (Q 2) - (- Q 2) + … + (Q g) - (- Q g)) q - 1 m.",
    "47. An apparatus comprising: memory configured to store information suitable for use with using a cryptographic process; and logic operatively coupled to said memory and configured to determine a hyperelliptic curve C of genus g over a field K and a positive integer m, determine a Jacobian J(C) of said hyperelliptic curve C, wherein each element D of J(C) contains a representative of the form A−g(P 0) and A is an effective divisor of degree g, and determine a plurality of functions h j,D that are iterative building blocks for the formation of a function h m,D in order to evaluate ν m which is a Squared Tate pairing.",
    "48. The apparatus as recited in claim 47, wherein said hyperelliptic curve C is not of characteristic 2.",
    "49. The apparatus as recited in claim 47, wherein for at least one element D of J(C), a representative for iD will be A i −g(P 0), where A i is effective of degree g.",
    "50. The apparatus as recited in claim 47, wherein if P=(x, y) is a point on said hyperelliptic curve C, then −P denotes a point −P:=(x, −y), and wherein if a point P=(x, y) occurs in A and y≠0, then −P:=(x,−y) does not occur in A and a representative for identity will be g(P 0).",
    "51. The apparatus as recited in claim 50, wherein said logic is further configured to, for a representative A i, associate two polynomials (a i, b i) which represent a divisor.",
    "52. The apparatus as recited in claim 50, wherein said logic is further configured to determine D as an m-torsion element of J(C).",
    "53. The apparatus as recited in claim 52, wherein said logic is further configured to, if j is an integer, then determine h j,D =h j,D (X) by denoting a rational function on C with divisor (h j,D)=jA 1 −A j −((j−1)g)(P 0).",
    "54. The computer-readable medium as recited in claim 52, wherein D is an m-torsion divisor and A m =g(P 0), and a divisor of h m,D is (h m,D)=mA 1 −mg(P 0). 55 The apparatus as recited in claim 52, wherein h m,D is well-defined up to a multiplicative constant.",
    "56. The apparatus as recited in claim 52, wherein said logic is further configured to evaluate h m,D at a degree zero divisor E on said hyperelliptic curve C, wherein E does not contain P 0 and E is prime to A i.",
    "57. The apparatus as recited in claim 52, wherein E is prime to A i for all i in an addition-subtraction chain for m.",
    "58. The apparatus as recited in claim 56, wherein given A i, A j, and A i+j, and wherein said logic is further configured to determine a function u i,j such that a divisor of u i,j is (u i,j)=A i +A j −A i+j −g(P 0).",
    "59. The apparatus as recited in claim 56, wherein said logic is further configured to evaluate h j,D (E) such that when j=1, h 1,D is 1.",
    "60. The apparatus as recited in claim 56, wherein said logic is further configured to, given A i, A j, h i,D (E) and h j,D (E), evaluate u i,j to be (u i,j)=A i +A j −A i+j −g(P 0),, and h i+j,D (E)=h i,D (E)h j,D (E)u i,j (E).",
    "61. The apparatus as recited in claim 47, wherein said logic is further configured to determine a function (u i,j)=A i +A j −A i+j −g(P 0).",
    "62. The apparatus as recited in claim 61, wherein g=2 and (u i,j)=A i +A j −A i+j −2(P 0) is determined by said logic as follows u i, j ⁡ (X):= a new ⁡ (x ⁡ (X)) b new ⁡ (x ⁡ (X)) + y ⁡ (X) * d ⁡ (x ⁡ (X)), if the degree of a new is greater than 2, otherwise, u i,j is determined as u i,j (X):=d(x(X)), wherein d(x) is the greatest common divisor of three polynomials (a i (x), a j (x), b i (x)+b j (x)).",
    "63. The apparatus as recited in claim 47, wherein said logic is further configured to determine a Squared Tate pairing for a hyperelliptic curves ν m, for an m-torsion element D of a Jacobian J(C) and an element E of J(C), with representatives (P 1)+(P 2)+... +(P g)−g(P 0) and (Q 1)+(Q 2)+... +(Q g)−g(P 0), respectively, with each P i and each Q j on the curve C, with P i not equal to ±Q j for all i,j, and to determine that v m ⁡ (D, E):= (h m, D ⁡ ((Q 1) - (- Q 1) + (Q 2) - (- Q 2) + … + (Q g) - (- Q g)) q - 1 m."
  ],
  "description_excerpt": "This invention relates to cryptography, and more particularly to methods and apparati that implement improved processing techniques for Tate pairings on hyperelliptic curves.\n\nAs computers have become increasingly commonplace in homes and businesses throughout the world, and such computers have become increasingly interconnected via networks (such as the Internet), security and authentication concerns have become increasingly important. One manner in which these concerns have been addressed is the use of a cryptographic technique involving a key-based cipher. Using a key-based cipher, sequences of intelligible data (typically referred to as plaintext) that collectively form a message are mathematically transformed, through an enciphering process, into seemingly unintelligible data (typically referred to as ciphertext). The enciphering can be reversed, allowing recipients of the ciphertext with the appropriate key to transform the ciphertext back to plaintext, while making it very difficult, if not nearly impossible, for those without the appropriate key to recover the plaintext.\n\nPublic-key cryptographic techniques are one type of key-based cipher. In public-key cryptography, each communicating party has a public/private key pair. The public key of each pair is made publicly available (or at least available to others who are intended to send encrypted communications), but the private key is kept secret.",
  "cpc": [
    "H04L 9/3073",
    "H04L 2209/12",
    "H04L 9/50"
  ],
  "ipc": [
    "H04L 9/30",
    "H04L 9/00"
  ],
  "assignees": [
    "Microsoft Corp"
  ],
  "inventors": [
    "Anne Eisentraeger",
    "Kristin Lauter",
    "Peter Montgomery"
  ],
  "filing_date": "2003-07-28",
  "publication_date": "2005-02-03",
  "priority_date": "2003-07-28",
  "application_number": "US-62872903-A",
  "family_id": "34103436",
  "cited_by_count": 18,
  "citations": [
    "US5026153A",
    "US5230400A",
    "US5272755A",
    "US6249589B1",
    "US5892855A",
    "US6185499B1",
    "US6446205B1",
    "US7079650B1",
    "US6968354B2",
    "US6986054B2",
    "US20030072443A1",
    "US20030081785A1",
    "US20030182554A1",
    "US20040131191A1",
    "US6795014B2"
  ]
}