Digital certificates

• US 20060107053A1
• Filed: 12/29/2003
• Published: 05/18/2006
• Est. Priority Date: 06/23/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: NDS Limited (Cisco Systems, Inc.)
• Inventors: Kipnis, Aviad, Shen-Orr, Chaim D., Halperin, Victor, Belenky, Yaacow
• Granted Patent: US 7,340,606 B2
• Time in Patent Office: Days
• US Class Current: 713/175
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823

Abstract

A method for producing a certificate, the certificate including data, the method including choosing a seed s, the seed s including a result of applying a function H to the data, generating a key pair (E,D), such that E=F(s,t), F being a publicly known function, and including s and t in the certificate. Related methods, and certificates produced by the various methods, are also described.

Claims

1. A method for producing a certificate, the certificate comprising data, the method comprising:

choosing a seed s, the seed s comprising a result of applying a function H to the data;

generating a key pair (E,D), such that E=F(s,t), F being a publicly known function; and

including s and t in the certificate.

2. The method according to claim 1 and wherein the including s and t in the certificate comprises:

including s concatenated with t in the certificate.

3. The method according to claim 1 and wherein the function H comprises a hash function.

4. The method according to claim 1 and wherein the function H comprises a checksum function.

5. The method according to claim 1 and wherein the function H comprises adding redundancy to the data.

6. A certificate produced by the method of claim 1.

7. A method for producing a certificate, the certificate comprising data, the method comprising:

generating a modulus N, the modulus N being generated by;

a scattering method L;

a function R; and

a seed s,

N being generated, in part, by scattering the bits of R(s) throughout N using the scattering method L, all bits of N other than those scattered by the scattering method L being denoted t; and

including s and t in the certificate.

8. The method according to claim 7 and wherein the R(s) comprises data associated with an owner of the certificate.

9. The method according to claim 8 and wherein the data comprises an owner identifier.

10. The method according to claim 7 and wherein N comprises an RSA modulus.

11. The method according to claim 10 and wherein L comprises applying a Lenstra, Lenstra and Lovasz (LLL) method to a lattice.

12. The method according to claim 11 and wherein the lattice is defined, in part, by a generalized pattern G.

13. The method according to claim 12 and wherein the lattice comprises:

V₁=(2^2n+L1 0 . . . 0 0

     0)
V₂=(0 2^2n+L2 . . . 0 0

     0)
V_k=(0 0 . . . 2^2n+Lk 0

     0)
V_k+1=(2<sup>2n−

S1+L1</sup>p 2<sup>2n−

S2+L2</sup>p . . . 2<sup>2n−

Sk+Lk</sup>p 2<sup>n+x−

z</sup> 0)
V_k+2=(2²ⁿ(r₁+0.5) 2²ⁿ(r₂+0.5) . . . 2²ⁿ(r_k+0.5) 0 2²ⁿ)

and wherein;

n, x, z are integers, and

S1, . . . , Sk are position numbers of contiguous groups of symbols “

*”

in a generalized 2n-bit pattern G, where positions are numbered from the least significant (0) to the most significant (2n−

1), and S1≧

S2≧

. . . ≧

Sk, and

L1, . . . , Lk are lengths of the contiguous groups, numbered correspondingly to the contiguous groups, and

p is a (n−

x)-bit prime, and

s is a seed, and

R is a function that expands s to R(s)=r1∥

r2∥

. . . ∥

rk, ∥

denoting concatenation, such that, for each i, ri has a length equal to Li.

14. A certificate produced by the method claim 7.

15. A method for producing a plurality of certificates, each certificate comprising data, the method comprising:

providing a plurality of generalized patterns; and

for each generalized pattern G of the plurality of generalized patterns, performing the following steps;

generating a modulus N, the modulus N being generated by;

a scattering method L;

a function R; and

a seed s,

N being generated, in part, by scattering the bits of R(s) throughout N using the scattering method L, all bits of N other than those scattered by the scattering method L being denoted t; and

including s and t in a certificate associated with G,

wherein N comprises an RSA modulus, and

L comprises applying a Lenstra, Lenstra and Lovasz (LLL) method to a lattice, and

the lattice is defined, in part, by G,

thereby producing a plurality of certificates.

19. The method according to claim 15 and wherein the lattice comprises:

V₁=(2^2n+L1 0 . . . 0 0

     0)
V₂=(0 2^2n+L2 . . . 0 0

     0)
V_k=(0 0 . . . 2^2n+Lk 0

     0)
V_k+1=(2<sup>2n−

S1+L1</sup>p 2<sup>2n−

S2+L2</sup>p . . . 2<sup>2n−

Sk+Lk</sup>p 2<sup>n+x−

z</sup> 0)
V_k+2=(2²ⁿ(r₁+0.5) 2²ⁿ(r₂+0.5) . . . 2²ⁿ(r_k+0.5) 0 2²ⁿ)

and wherein;

n, x, z are integers, and

S1, . . . , Sk are position numbers of contiguous groups of symbols “

*”

in a generalized 2n-bit pattern G, where positions are numbered from the least significant (0) to the most significant (2n−

1), and S1≧

S2≧

. . . ≧

Sk, and

L1, . . . , Lk are lengths of the contiguous groups, numbered correspondingly to the contiguous groups, and

p is a (n−

x)-bit prime, and

s is a seed, and

R is a function that expands s to R(s)=r1∥

r2∥

. . . ∥

rk, ∥

denoting concatenation, such that, for each i, ri has a length equal to Li.

20. A plurality of certificates, produced by the method of claim 15.

16. A method for producing a plurality of certificates, each certificate comprising data, the method comprising:

providing a plurality of generalized patterns; and

for each generalized pattern G of the plurality of generalized patterns, performing the following steps;

generating a plurality of moduli N_i, each modulus N_i being generated by;

a scattering method L;

a function R; and

a seed s_i,

each N_i being generated, in part, by scattering the bits of R(s_i) throughout N_i using the scattering method L, all bits of N_i other than those scattered by the scattering method L being denoted t_i; and

for each N_i, including s_i and t_i in a certificate associated with G,

wherein N_i comprises an RSA modulus, and

L comprises applying a Lenstra, Lenstra and Lovasz (LLL) method to a lattice, and

the lattice is defined, in part, by G,

thereby producing a plurality of certificates.

17. The method according to claim 16 and wherein the lattice comprises:

V₁=(2^2n+L1 0 . . . 0 0

     0)
V₂=(0 2^2n+L2 . . . 0 0

     0)
V_k=(0 0 . . . 2^2n+Lk 0

     0)
V_k+1=(2<sup>2n−

S1+L1</sup>p 2<sup>2n−

S2+L2</sup>p . . . 2<sup>2n−

Sk+Lk</sup>p 2<sup>n+x−

z</sup> 0)
V_k+2=(2²ⁿ(r₁+0.5) 2²ⁿ(r₂+0.5) . . . 2²ⁿ(r_k+0.5) 0 2²ⁿ)

and wherein;

n, x, z are integers, and

S1, . . . , Sk are position numbers of contiguous groups of symbols “

*”

in a generalized 2n-bit pattern G, where positions are numbered from the least significant (0) to the most significant (2n−

1), and S1≧

S2≧

. . . ≧

Sk, and

L1, . . . , Lk are lengths of the contiguous groups, numbered correspondingly to the contiguous groups, and

p is a (n−

x)-bit prime, and

s is a seed, and

R is a function that expands s to R(s)=r1∥

r2∥

. . . ∥

rk, ∥

denoting concatenation, such that, for each i, ri has a length equal to Li.

18. A plurality of certificates, produced by the method of claim 16.