Speed enhanced cryptographic method and apparatus

• US 7,031,468 B2
• Filed: 08/24/2001
• Issued: 04/18/2006
• Est. Priority Date: 08/29/2000
• Status: Expired due to Fees

• Current Assignee: Onboard Security Inc. (Qualcomm, Inc.)
• Original Assignee: NTRU Cryptosystems Incorporated (Security Innovation Incorporated)
• Inventors: Silverman, Joseph H., Hoffstein, Jeffrey
• Primary Examiner(s): Zand, Kambiz
• Application Number:
  US09/939,531
• Publication Number:
  US 20020041681A1
• Time in Patent Office: 1,698 Days
• Field of Search: 380/28, 713/156, 713/175, 713/176, 708/255
• US Class Current: 380/28
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme

Abstract

A method for performing a cryptographic operation involving transforming digital information is described. A digital operator is provided that has a component selected from a large set of elements. The component is expanded into a plurality of factors, each factor having a low Hamming weight. Digital information is transformed using the digital operator. Computer readable medium embody instructions for the method.

Claims

1. A method for performing a cryptographic operation that comprises transforming digital information, the method comprising:

providing digital information;

providing a digital operator having a component selected from a large set of elements;

expanding the component into a plurality of factors, each factor having a low hamming weight; and

transforming the digital information using the digital operator, said transforming comprising computing multiples;

said method further comprising;

selecting a ring R;

selecting an R-module M;

selecting two or more subsets R₁, R₂, . . . , R_k of R with the property that r₁ is an element in R₁, r₂ is an element in R₂, . . . and r_k is an element in R_k;

computing r*m, where r is in R and m is in M, by expanding r as r₁*r₂ . . . r_k, where k is an integer and computing the quantity r₁*(r₂*( . . . (r_k*m).

2. The method of claim 1, wherein the cryptographic operation is selected from a group consisting of key generation, encryption, decryption, creation of a digital signature, verification of a digital signature, creation of a digital certificate, authentication of a digital certificate, identification, pseudorandom number generation and computation of a hash function.

3. The method of claim 1, wherein each r_k has a Hamming weight that is less than about 15.

4. The method of claim 1, wherein each r_k has a Hamming weight that is less than about 10.

5. The method of claim 1, wherein the subset R_i is a subset of R consisting of elements of the form,

a₁t^e(1)+a₂t^e(2)+ . . . +a_nt^e(n),

where n is an integer.

6. The method of claim 5, wherein each of the elements a₁, . . . , a_n are chosen from the set {0,1}.

7. The method of claim 5, wherein each of the elements a₁, . . . , a_n are chosen from the set {−

1,0,1}.

8. The method of claim 1, wherein the subset R_i is a subset of R consisting of polynomials in elements of t₁, . . . , t_k of R having coefficients a₁, . . . , a_k taken from a subset A of R where k is an integer.

9. The method of claim 8, wherein each of the coefficients a₁, . . . , a_k is chosen from the set {0,1}.

10. The method of claim 8, wherein each of the coefficients a₁, . . . , a_k is chosen from the set {−

1,0,1}.

11. The method of claim 1, wherein the ring R is the ring of integers, the R-module M is a group of nonzero elements in the field GF(p^m) with p^m elements, and wherein the subsets R₁, . . . , R_k consist of integers of the form

a₁p^e(1)+a₂p^e(2)+ . . . +a_np^e(n),

wherein n is an integer that is less than m and wherein a₁, . . . , a_n are elements of the set {0,1}.

12. The method of claim 1, wherein the ring R is the ring of integers, the R-module M is a group of nonzero elements in the field GF(p^m) with p^m elements, and wherein the subsets R₁, . . . , R_k consist of integers of the form

a₁p^e(1)+a₂p^e(2)+ . . . +a_np^e(n),

wherein n is an integer that is less than m and wherein a₁, . . . , a_n are elements of a small set of integers A.

13. The method of claim 1, wherein the ring R is an endomorphism ring of a group of points E(GF(q)) of an elliptic curve E over a finite field GF(q).

14. The method of claim 1, wherein the module M is a group of points e(GF(q)) of an elliptic curve E over a finite field GF(q).

15. The method of claim 5, wherein the ring R is an endomorphism ring of a group of points E(GF(q)) of an elliptic curve E over a finite field GF(q) of characteristic p, wherein the module M is a group of points E(GF(q)) and wherein the element t is a p-power Frobenius map.

16. The method of claim 5, wherein the ring R is an endomorphism ring of a group of points E(GF(q)) of an elliptic curve E over a finite field GF(q) of characteristic p, wherein the module M is a group of points E(GF(q)) and wherein the element t is a point halving map.

17. The method of claim 1, wherein the ring R is a ring of polynomials modulo an ideal A[X]/I, wherein A is a ring and I is an ideal of A[X], and wherein the subsets R₁, . . . , R_k are sets of polynomials with few nonzero terms.

18. The method of claim 17, wherein the ideal I is the ideal generated by the polynomimial X^N−

1.

19. The method of claim 17, wherein the ring R is a finite ring Z/qZ of integers modulo q, wherein q is a positive integer.

20. The method of claim 5, wherein the ring R is a ring of polynomials modulo an ideal A[X]/I, wherein A is a ring and I is an ideal of A[X], and wherein the element t is the polynomial X in R.

21. The method of claim 20, wherein the deal I is the ideal generated by the polynomimial X^N−

1.

22. The method of claim 20, wherein the ring R is a finite ring Z/qZ of integers modulo q, wherein q is a positive integer.

23. A computer readable medium containing instructions for a method for performing a cryptographic operation that comprises transforming digital information, the method comprising:

providing digital information;

providing a digital operator having a component selected from a large set of elements;

expanding the component into a plurality of factors, each factor having a low hamming weight; and

transforming the digital information using the digital operator, said transforming comprising computing multiples;

said method further comprising;

selecting a ring R;

selecting an R-module M;

selecting two or more subsets R₁, R₂, . . . , R_k of R with the property that r₁ is an element in R₁, r₂ is an element in R₂, . . . and r_k is an element in R_k;

computing r*m, where r is in R and m is in M, by expanding r as r₁* r₂* . . . r_k, where k is an integer and computing the quantity r₁*(r₂*( . . . (r_k*m).

24. The computer readable medium of claim 23, containing instructions for a method wherein the subset R_i is a subset of R consisting of elements of the form,

a₁t^e(1)+a₂t^e(2)+ . . . +a_nt^e(n),

where n is an integer.

25. The computer readable medium of claim 23, containing instructions for a method wherein the subset R_i is a subset of R consisting of polynomials in elements of t₁, . . . , t_k of R having coefficients a₁, . . . , a_k taken from a subset A of R where k is an integer.

26. The computer readable medium of claim 23, containing instructions for a method wherein the ring R is the ring of integers, the R-module M is a group of nonzero elements in the field GF(p^m) with p^m elements, and wherein the subsets R₁, . . . , R_k consist of integers of the form

a₁p^e(1)+a₂p^e(2)+ . . . +a_np^e(n),

wherein n is an integer that is less than m and wherein a₁, . . . , a_n are elements of the set {0,1}.

27. The computer readable medium of claim 23, containing instructions for a method wherein the ring R is the ring of integers, the R-module M is a group of nonzero elements in the field GF(p^m) with p^melements, and wherein the subsets R₁, . . . , R_k consist of integers of the form

a₁p^e(1)+a₂p^e(2)+ . . . +a_np^e(n),

wherein n is an integer that is less than m and wherein a₁, . . . , a_n are elements of a small set of integers A.

28. The computer readable medium of claim 23, containing instructions for a method wherein the ring R is an endomorphism ring of a group of points E(GF(q)) of an elliptic curve E over a finite field GF(q).

29. The computer readable medium of claim 23, containing instructions for a method wherein the module M is a group of points e(GF(q)) of an elliptic curve E over a finite field GF(q).

30. The computer readable medium of claim 24, containing instructions for a method wherein the ring R is an endomorphism ring of a group of points E(GF(q)) of an elliptic curve E over a finite field GF(q) of characteristic p, wherein the module M is a group of points E(GF(q)) and wherein the element t is a p-power Frobenius map.

31. The computer readable medium of claim 24, containing instructions for a method wherein the ring R is an endomorphism ring of a group of points E(GF(q)) of an elliptic curve E over a finite field GF(q) of characteristic p, wherein the module M is a group of points E(GF(q)) and wherein the element t is a point halving map.

32. The computer readable medium of claim 23, containing instructions for a method wherein the ring R is a ring of polynomials modulo an ideal A[X]/I, wherein A is a ring and I is an ideal of A[X], and wherein the subsets R₁, . . . , R_k are sets of polynomials with few nonzero terms.

33. The computer readable medium of claim 24, containing instructions for a method wherein the ring R is a ring of polynomials modulo an ideal A[X]/I, wherein A is a ring and I is an ideal of A[X], and wherein the element t is the polynomial X in R.