Title: Secure user identification based on ring homomorphisms
Abstract: A method for authenticating, by a second user, the identity of a first user, that includes a challenge communication from the second user to the first user, a response communication from the first user to the second user, and a verification by the second user, includes the steps: selection by the first user of a private key f in a ring R and a public key that includes φ(f) in a ring B that is mapped from f using the ring homomorphism φ: R→B, and publication by the first user of the public key; generation of the challenge communication by the second user that includes selection of a challenge c in the ring R; generation of the response communication by the first user that includes computation of a response comprising h in the ring R, where h is a function of c and f; and performing of a verification by the second user that includes determination of φ(c) from c, φ(h) from h, and an evaluation that depends on φ(h), φ(c) and φ(f).
Patent Number: 6,959,085 Issued on 10/25/2005 to Hoffstein, et al.
| Inventors:
|
Hoffstein; Jeffrey (Pawtucket, RI);
Silverman; Joseph H. (Needham, MA);
Lieman; Daniel (Columbia, MO)
|
| Assignee:
|
NTRU Cryptosystems, Inc. (Burlington, MA)
|
| Appl. No.:
|
564112 |
| Filed:
|
May 3, 2000 |
| Current U.S. Class: |
380/30; 380/2; 380/28; 713/156; 713/168; 713/171; 713/176; 713/180 |
| Intern'l Class: |
H04L 009/00 |
| Field of Search: |
380/30
|
References Cited [Referenced By]
U.S. Patent Documents
| 4995082 | Feb., 1991 | Schnorr.
| |
| 5054066 | Oct., 1991 | Riek et al.
| |
| 5220606 | Jun., 1993 | Greenberg.
| |
| 5740250 | Apr., 1998 | Moh.
| |
| 5790675 | Aug., 1998 | Patarin.
| |
| 5805703 | Sep., 1998 | Crandall.
| |
| 5889865 | Mar., 1999 | Vanstone et al.
| |
| 5974142 | Oct., 1999 | Heer et al.
| |
| 5982891 | Nov., 1999 | Ginter et al.
| |
| 6076163 | Jun., 2000 | Hoffstein et al.
| |
| 6081597 | Jun., 2000 | Hoffstein et al.
| |
| 6144740 | Nov., 2000 | Laih et al.
| |
| 6286022 | Sep., 2001 | Kaliski et al.
| |
| 6298137 | Oct., 2001 | Hoffstein et al.
| |
| 6480605 | Nov., 2002 | Uchiyama et al.
| |
| 6526509 | Feb., 2003 | Horn et al.
| |
| Foreign Patent Documents |
| 2737370 | Jan., 1997 | FR.
| |
Other References
M. Ajtai, C. Dwork, "Public-Key Cryptosystem With Worst Case/Average Case Equivalence"
In Proc. 29th ACM Symposium On Theory Of Computing, 1997, pp. 284-294.
E.R. Brickell and K.S. McCurley, "Interactive Identification And Digital Signatures",
AT&T Technical Journal, Nov./Dec., 1991, pp. 73-86.
O. Goldreich, S. Goldwasser, S. Halevy, "Public-Key Cryptography From Lattice
Reduction Problems", In Proc. CRYPTO'97 Lect. Notes in Computer Science 1294, Springer-Verlag,
1997, pp. 112-131.
L.C. Guillou and J.-J. Quisquater, "A Practical Zero-Knowledge Protocol Fitted
To Security Microprocessor Minimizing Both Transmission And Memory", In C.G. Gunther,
Editor, Advances In Cryptology—Eurocrypt '88, Lecture Notes In Computer Science
330, Springer-Verlag (1988) pp. 123-128.
J. Hoffstein, J. Pipher, J. Silverman, NTRU: "A Ring-Based Public Key System",
Proceedings of ANTS III, Portland (1998), Springer-Verlag.
A.K. Lenstra, H.W. Lenstra Jr., L. Lovasz, "Factoring Polynomials With Rational
Coefficients", Mathematische Ann. 261 (1982), pp. 513-643.
A. May, "Cryptanalysis of NTRU", preprint, Feb. 1999.
R. Merkle, M. Hellman, "Hiding Information And Signatures In Trapdoor Knapsacks",
IEEE Trans. Inform. Theory, IT-24: pp. 525-530, Sep. 1978.
T. Okamoto, "Provably Secure And Practical Identification Schemes And Corresponding
Signature Schemes", In E.F. Brickell, Editor, Advances In Cryptology—Crypto
'92, Lecture Notes In Computer Science 740, Springer-Verlag.
C.-P. Schnorr, "A Hierarchy Of Polynomial Time Lattice Basis Reduction Algorithms",
Theoretical Computer Science 53 (1987), pp. 201-224.
C.-P. Schnorr, "A More Efficient Algorithm For Lattice Basis Reduction", J. Algorithms
(1988), pp. 47-62, (1993) pp. 31-53.
C.-P. Schnorr, "Efficient Identification And Signatures For Smart Cards", In
G. Brassard, Editor, Advances In Cryptology—Crypto '89, Lecture Notes In
Computer Science 435, Springer-Verlag (1990) pp. 239-251.
A. Shamir, "A Polynomial-Time Algorithm For Breaking The Basic Merkel-Hellman
Cryptosystem", In Proceedings Of The 23rd IEEE Symposium On Foundations of Computer
Science, IEEE, 1982, 145-152.
A. Shamir, "An Efficient Identification Scheme Based On Permuted Kernels", In
G. Brassard, Editor, Advances In Cryptology—Crypto '89, lecture Notes In
Computer Science 435, Springer-Verlag (1990) pp. 606-609.
J./h. Silverman, "Dimension-Reduced Lattices, Zero-Forced Lattices, and The NTRU
Public Key Cryptosystem", NTRU Technical Note 013, Mar. 2, 1999, <www.ntru.com>.
J. Stern, "A New Identification Scheme Based On Syndrome Decoding", In D. Stinson,
Editor, Advances In Cryptology—Crypto '93, Lecture Notes In Computer Science
773, Springer-Verlag (1994) pp. 13-41.
J. Stern, "Designing Identification Schemes With Keys Of Short Size", In Y.G.
Desmedt, Editor, Advances In Cryptology—Crypto '94, Lecture Notes In Computer
Science 839, Springer-Verlag (1994) pp. 164-173.
|
Primary Examiner: Peeso; Thomas R.
Assistant Examiner: Zla; Syed A.
Attorney, Agent or Firm: Novack; Martin
Parent Case Text
RELATED APPLICATION
This application claims priority from U.S. Provisional Patent Application No.
60/132,199, filed May 3, 1999, and said Provisional Patent Application is incorporated
herein by reference.
Claims
1. A method of communicating information between users of a communication system,
the method comprising the steps of:
transmitting from a first user to a second user a result ø(g) of evaluating
an element g in a ring R by a ring homomorphism ø:R→B, wherein the
element g satisfies a first set of predetermined conditions;
generating an element h in the ring R as a function of an element c in the ring
R satisfying a second set of predetermined conditions, a private key element f
of the first user in the ring R, wherein the element f satisfies a third set of
predetermined conditions; and
transmitting the element h from the first user to the second user, such that
the second user can authenticate the communication from the first user by verifying
that the element h satisfies a fourth set of predetermined conditions and by comparing
the result ø(h) of evaluating the element h by the ring homomorphism o to
a function of ø(g), ø(c), and a public key ø(f) of the first user.
2. The method of claim 1 wherein the element c is generated by the second user
as a challenge to the first user in response to receipt of the result ø(g).
3. The method of claim 2 wherein the second user authenticates the identity of
the first user based on the result of the step of comparing ø(h) to a function
of ø(g), ø(c) and ø(f).
4. The method of claim 1 wherein the element c is generated by the first user
applying a hash function to the result ø(g) and a message m, and the method
further includes the step of transmitting the message m from the first user to
the second user.
5. The method of claim 4 wherein the second user authenticates a digital signature
of the first user based on the result of the step of applying a hash function to
the result ø(g) and the message m to generate an element c, and the method
further includes the step of comparing ø(h) to a function of ø(g), ø(c)
and ø(f).
6. The method of claim 1 wherein the ring R is a ring of functions.
7. The method of claim 6 wherein the homomorphism øis the evaluation homomorphism
at a set of values a
1,a
2 . . . a
s.
8. The method of claim 1 wherein the element h generated as a function of the
element c, a private key f, and the first element g, is generated as the value
of a polynomial P(f,c,g), wherein P(X,Y,Z) is a polynomial with coefficients in R.
9. The method of claim 8 wherein the second user authenticates the communication
from the first user by comparing the result ø(h) of evaluating the element
h by the ring homomorphism øto the result of evaluating ø(P)(ø(f)ø,ø(c),ø(g)),
wherein ø(P) is the polynomial obtained by evaluating the coefficients of
the polynomial P by the ring homomorphism ø.
10. The method of claim 8 wherein the polynomial P(X,Y,Z) is the polynomial ZX+Z
2Y.
11. The method of claim 8 wherein f is a nc-tuple, c is an nc-tuple, and g is
an ng-tuple and P is a polynomial in n
f+n
c+n
g variables.
12. The method of claim 11 wherein n
c is equal to n
fn
g
and the polynomial P is equal to the summation of X
iY
ijZ
j
as i ranges from 1 to n
f and j ranges from 1 to n
g.
13. The method of claim 1 wherein the ring R is the ring Fq[X]/(X
N-1)
of polynomials over the field F
q of q elements modulo the ideal generated
by the polynomial X
N-1 and wherein N is a divisor of q-1.
14. The method of claim 13 wherein the first set of predetermined conditions
on the element g are that the coefficients of g are small compared to q.
15. The method of claim 13 wherein the second set of predetermined conditions
on the element c are that the coefficients of c are small compared to q.
16. The method of claim 13 wherein the third set of predetermined conditions
on the element f are that the coefficients of f are small compared to q.
17. The method of claim 13 wherein the fourth set of predetermined conditions
on the element h are that the coefficients of h are small compared to q.
18. A method of communicating information between users of a communication system,
the method comprising the steps of:
generating an element h in a ring R as a function of an element g in the ring
R satisfying a first set of predetermined conditions, an element c in the ring
R satisfying a second set of predetermined conditions, and a private key element
f of a first user in the ring R satisfying a third set of predetermined conditions;
transmitting the element h from the first user to a second user, such that the
second user can authenticate the communication from the first user by verifying
that the element h satisfies a fourth set of predetermined conditions and by using
a ring homomorphism ø:R+B and verifying that the quantity ø(h), the quantity
ø(c), and a public key ø(f) of the first user satisfy a fifth set of
predetermined conditions.
19. The method of claim 18 wherein h is also a function of an element g, in the
ring R, and wherein the element +(g
1) is transmitted from the first
user to the second user and wherein the second user also uses ø(g
1)
to authenticate the communication.
20. The method of claim 18 wherein the element c is generated by the second user
as a challenge to the first user.
21. The method of claim 20 wherein the second user authenticates the identity
of the first user based on the result of the step of verifying that the element
h satisfies the fourth set of predetermined conditions and that the quantities
ø(h), ø(c), and ø(f) satisfy the fifth set of predetermined conditions.
22. The method of claim 18 wherein the element c is generated by the first user
applying a hash function to the message m, and the method further includes the
step of transmitting the message m from the first user to the second user.
23. The method of claim 22 wherein the second user authenticates a digital signature
of the first user based on the result of the step of applying a hash function to
the message m to generate an element c, and the method further includes the step
verifying that the element h satisfies the fourth set of predetermined conditions
and that the quantities ø(h), ø(c), and ø(f) satisfy the fifth set
of predetermined conditions.
24. The method of claim 18 wherein the ring R is a ring of functions.
25. The method of claim 24 wherein the homomorphism øis the evaluation homomorphism
at a set of values a
1, a
2 . . . , a
s.
26. The method of claim 18 wherein the element h generated as a function of the
element c, a private key f, and the first element g, is generated as the value
of a polynomial P(f,c,g), wherein P(X,Y,Z) is a polynomial with coefficients in R.
27. The method of claim 26 wherein the fifth set of predetermined conditions
by which the second user authenticates the communication from the first user are
that the equation ø(P)(ø(f),ø(c),Z)=
0 has a solution Z in
the ring R, wherein ø(P) is the polynomial obtained by evaluating the coefficients
of the polynomial P by the ring homomorphism ø.
28. The method of claim 26 wherein the polynomial P(X,Y,Z) is the polynomial ZX+Z
2Y.
29. The method of claim 26 wherein f is a n
f-tuple, c is an n
c-tuple,
and g is an n
g-tuple and P is a polynomial in n
f+n
c+n
g variables.
30. The method of claim 29 wherein the polynomial P is equal to XZ
2+Y
1Z
1Z
2+Y
2Z
22.
31. The method of claim 30 wherein the fifth set of predetermined conditions
is that (φ(φ+φ(C
1)φ(g
1))
2+4(c
2)φ(h)
is the square of an element of the ring B.
32. The method of claim 28 wherein the fifth set of predetermined conditions
by which the second user authenticates the communication from the first user are
that the quantity ø(f)
2+4ø(c)ø(h) is the square of an
element of the ring B.
33. The method of claim 18 wherein the ring R is the ring Fq[X]/(X
N-1)
of polynomials over the field F
q of q elements modulo the ideal generated
by the polynomial X
N-1 and wherein N is a divisor of q-1.
34. The method of claim 33 wherein the first set of predetermined conditions
on the element g are that the coefficients of g are small compared to q.
35. The method of claim 33 wherein the second set of predetermined conditions
on the element c are that the coefficients of c are small compared to q.
36. The method of claim 33 wherein the third set of predetermined conditions
on the element f are that the coefficients of f are small compared to q.
37. The method of claim 33 wherein the fourth set of predetermined conditions
on the element h are that the coefficients of h are small compared to q.
38. A method for authenticating, by a second user, the identity of a first user,
that includes a challenge communication from the second user to the first user,
a response communication from the first user to the second user, and a verification
by the second user, comprising the steps of:
selection by the first user of a private key f in a ring R and a public key that
includes φ(f) in a ring B that is mapped from f using the ring homomorphism
φ: R→B, and publication by the first user of the public key;
generation of the challenge communication by the second user that includes selection
of a challenge c in the ring R;
generation of the response communication by the first user that includes computation
of a response comprising h in the ring R, where h is a function of c and f, and
performing of a verification by the second user that includes determination of
φ(c) from c, φ(h) from h, and an evaluation that depends on φ(h),
φ(c) and φ(f).
39. The method as defined by claim 38, wherein said generation of the response
communication by the first user includes selection by the first user of an element
g in the ring R, and wherein h is also a function of g.
40. The method as defined by claim 39, wherein φ(g) is also communicated
to the second user, and wherein said performing of a verification includes an evaluation
that also depends on φ(g).
41. The method as defined by claim 39, wherein said authentication includes an
initial commitment communication from said first user to said second user, and
wherein said commitment communication includes φ(g).
42. The method as defined by claim 39, wherein said first user further selects
an element g, in the ring R and determines φ(g
1) therefrom, and
further comprising communicating φ(g
1) to the second user.
43. The method as defined by claim 42, wherein said authentication includes an
initial commitment communication from said first user to said second user, and
wherein said commitment communication includes φ(g
1).
44. The method as defined by claim 39, wherein f, c, and g are elements in respective
subsets of the ring R.
45. The method as defined by claim 42, wherein f, c, g, and g, are elements in
respective subsets of the ring R.
46. The method as defined by claim 39, wherein f, c, g, and h are polynomials,
and wherein φ(f), φ(c), φ(g) and φ(h) each represent one
or more values of the respective polynomials from which they are mapped.
47. The method as defined by claim 43, wherein f, c, g, g, and h are polynomials,
and wherein φ(f), φ(c), φ(g), φ(g
1) and φ(h)
each represent one or more values of the respective polynomials from which they
are mapped.
48. The method as defined by claim 39, wherein said step of generation of the
response includes computation of h in the form h=(f+cg)g.
49. The method as defined by claim 39, wherein at least one of the elements f,
c, and g is an n-tuple with n greater than 1, and φ evaluated at an n-tuple
of elements (r
1, r
2 . . . r
n) of R is equal to
the n-tuple of respective values (φ(r
1), φ(r
2)
. . . φ(r
n)) of φ.
50. The method as defined by claim 40, wherein at least one of the elements f,
c, and g is an n-tuple with n greater than 1, and φevaluated at an n-tuple
of elements (r
1, r
2, . . . r
n) of R is equal to
the n-tuple of respective values (φ(r
1), φ(r
2)
. . . φ(r
n)) of φ.
51. The method as defined by claim 41, wherein at least one of the elements f,
c, and g is an n-tuple with n greater than 1, and φ evaluated at an n-tuple
of elements (r
1, r
2 . . . r
n) of R is equal to
the n-tuple of respective values (φ(r
1), φ(r
2)
. . . (r
n)) of φ.
52. The method as defined by claim 42, wherein at least one of the elements f,
c, and g is an n-tuple with n greater than 1, and φ evaluated at an n-tuple
of elements (r
1, r
2 . . . r
n) of R is equal to
the n-tuple of respective values (φ(r
1), φ(r
2)
. . . (r
n)) of φ.
53. The method as defined by claim 43, wherein at least one of the elements f,
c, and g is an n-tuple with n greater than 1, and φevaluated at an n-tuple
of elements (r
1, r
2 . . . r
n) of R is equal to
the n-tuple of respective values (φ(r
1), φ(r
2)
. . . (r
n)) of φ.
54. The method as defined by claim 52, wherein element c includes the pair c
1,
c
2 and elements g
1, g
2, correspond respectively
to the pair g
1, g
2, and wherein h is of the form
55. The method as defined by claim 53, wherein element c includes the pair c
1,
c
2 and elements g
1, g correspond respectively to the pair
g
1, g
1, and wherein h is of the form
56. The method as defined by claim 50, wherein element f includes the pair f
1,
f
2, element g includes the pair g
1, g
2, and element
c includes the 4-tuple C
11, c
12, c
12, c
21,
C
22, and wherein h is of the form
57. The method as defined by claim 51, wherein element f includes the pair f
1,
f
2, element g includes the pair g
1, g
2, and element
c includes the 4-tuple c
11, c
12, C
12, c
21,
c
22, and wherein h is of the form
58. The method as defined by claim 42, wherein said verification includes a determination
of whether certain values of functions of φ(f), φ(c), φ(g
1),
φ(h) are squares modulo q, where q is a certain integer modulus used in key
creation by the first user.
59. The method as defined by claim 43, wherein said verification includes a determination
of whether certain values of functions of φ(f), φ(c), φ(g
1),
φ(h) are squares modulo q, where q is a certain integer modulus used in key
creation by the first user.
60. The method as defined by claim 53, wherein said verification includes a determination
of whether certain values of functions of φ(f)φ, φ(c), φ(g
1),
φ(h) are squares modulo q, where q is a certain integer modulus used in key
creation by the first user.
61. The method as defined by claim 55, wherein said verification includes a determination
of whether certain values of functions of φ(f), φ(c), φ(g
1),
φ(h) are squares modulo q, where q is a certain integer modulus used in key
creation by the first user.
62. An authentication method that includes authenticating, by a second user,
of a signed digital message of a first user communicated from said first user to
said second user, comprising the steps of:
selecting by the first user, of a private key f in a ring R and a public key
that includes φ(f) in a ring B that is mapped from f using the ring homomorphism
φ: R→B, and publication by the first user of the public key;
selecting, by the first user, of an element g
1 in the ring R, determining
φ(g
1), and applying a hash function to at least a message m to
produce an element c;
generating, by the first user, an element h which is a function of c and f;
communicating, from the first user to the second user, the message m and a digital
signature comprising φ(g
1) and h;
determining, by the second user, of the element c, by applying a hash function
to at least the message m, and determining, by the second user of φ(c) from
c and φ(h) from h; and
authenticating, by the second user, of the digital signature, said authenticating
including an evaluation that depends on φ(h), φ(f) and φ(c).
63. The method as defined by claim 62, wherein said steps, by the first user
and the second user, of applying a hash function to at least the message m, comprise
applying a hash function to the message m.
64. The method as defined by claim 62, wherein said steps, by the first user
and the second user, of applying a hash function to at least the message m, comprise
applying a hash function to a combination of the message m and φ(g
1).
65. The method as defined by claim 62, wherein f, c, and g, are elements in respective
subsets of the ring R.
66. The method as defined by claim 62, wherein f, c, g
1, and h are
polynomials, and wherein φ(f), φ(c), φ(g
1) and φ(h)
each represent one or more values of the respective polynomials from which they
are mapped.
67. The method as defined by claim 54, wherein f, c, g
1, and h are
polynomials, and wherein φ(f), φ(c), φ(g
1) and φ(h)
each represent one or more values of the respective polynomials from which they
are mapped.
68. The method as defined by claim 62, wherein h is of the form h=(f+cg
1)g
1.
69. The method as defined by claim 66, wherein at least one of the elements f,
c, and g
1 is an n-tuple with n greater than 1.
70. The method as defined by claim 67, wherein at least one of the elements f,
c, and g
1 is an n-tuple with n greater than 1.
71. The method as defined by claim 70, wherein element c includes the pair c
1,
c
2 and element g
1 is part of the pair g
1, g
2,
and wherein h is of the form
72. The method as defined by claim 69, wherein element f includes the pair f
1,
f
2, element g, is part of the pair g
1, g
2, and
element c includes the 4-tuple c
11, c
12, C
12,
c
21, c
22, and wherein h is of the form
73. The method as defined by claim 58, wherein said verification includes a determination
of whether certain values of functions of φ(f), φ(c), φ(g
1),
φ(h) are squares modulo q, where q is a certain integer modulus used in key
creation by the first user.
74. A method for use by a first user to prove its identity to a second user who
sends a challenge to the first user and wishes to authenticate the identity of
the first user, comprising the steps of:
selecting a private key f in a ring R and a public key that includes φ(f)
in a ring B that is mapped from f using the ring homomorphism φ: R→B,
and publication by the first user of the public key;
receiving the challenge communication from the second user that includes selection
of a challenge element c in the ring R; and
generation of the response communication that includes computation of a response
comprising h in the ring R, where h is a function of c and f;
whereby the second user can perform a verification that includes determination
of φ(c) from c, φ(h) from h, and an evaluation that depends on φ(h),
φ(c) and φ(f).
75. A method for producing and sending a signed digital message comprising the
steps of:
selecting a private key f in a ring R and a public key that includes φ(f)
in a ring B that is mapped from f using the ring homomorphism φ: R→B,
and publication by the first user of the public key;
selecting an element g
1 in the ring R, determining φ(g
1),
and applying a hash function to at least a message m to produce an element c;
generating an element h which is a function of c and f; and
communicating the message m and a digital signature comprising φ(g
1)
and h.
Description
FIELD OF THE INVENTION
The present invention relates generally to secure communication and document
identification over computer networks or other types of communication systems and,
more particularly, to secure user identification and digital signature techniques
based on ring homomorphisms. The invention also has application to communication
between a card, such as a "smart card", or other media, and a user terminal.
BACKGROUND OF THE INVENTION
User identification techniques provide data security in a computer network or
other communications system by allowing a given user to prove its identity to one
or more other system users before communicating with those users. The other system
users are thereby assured that they are in fact communicating with the given user.
The users may represent individual computers or other types of terminals in the
system. A typical user identification process of the challenge-response type is
initiated when one system user, referred to as the Prover, sends certain information
in the form of a commitment to another system user, referred to as the Verifier.
Upon receipt of the commitment, the verifier sends a challenge to the Prover. The
Prover uses the commitment, the challenge, and its private key to generate a response,
which is sent to the Verifier. The Verifier uses the commitment, the response and
a public key to verify that the response was generated by a legitimate prover.
The information passed between the Prover and the Verifier is generated in accordance
with cryptographic techniques which insure that eavesdroppers or other attackers
cannot interfere with or forge the identification process.
It is well known that a challenge-response user identification technique can
be
converted to a digital signature technique by the Prover utilizing a one-way hash
function to simulate a challenge from a Verifier. In such a digital signature technique,
a Prover generates a commitment and applies the one-way hash function to it and
a message to generate the simulated challenge. The Prover then utilizes the simulated
challenge, the commitment and a private key to generate a digital signature, which
is sent along with the message to the Verifier. The Verifier applies the same one-way
hash function to the commitment and the message to recover the simulated challenge
and uses the challenge, the commitment, and a public key to validate the digital signature.
One type of user identification technique relies on the one-way property of the
exponentiation function in the multiplicative group of a finite field or in the
group of points on an elliptic curve defined over a finite field. This technique
is described in U.S. Pat. No. 4,995,082 and in C. P. Schnorr, "Efficient Identification
and Signatures for Smart Cards," in G. Brassard, ed., Advances in Cryptology—Crypto
'89, Lecture Notes in Computer Science 435, Springer-Verlag, 1990, pp. 239-252.
This technique involves the Prover exponentiating a fixed base element g of the
group to some randomly selected power k and sending it to the verifier. An instance
of the Schnorr technique uses two prime numbers p and q chosen at random such that
q divides p-1, and a number g of order q modulo p is selected. The numbers p, q,
and g are made available to all users. The private key of the Prover is x modulo
q and the public key y of the Prover is g
-x modulo p. The Prover initiates
the identification process by selecting a random non-zero number z modulo q. The
Prover computes the quantity gz modulo p and sends it as a commitment to the Verifier.
The Verifies selects a random number w from the set of integers {1,2, . . . , 2
t}
where t is a security number which depends on the application and in the above-cited
article is selected as 72. The Verifier sends w as a challenge to the Prover. The
Prover computes a quantity u that is equal to the quantity z+xw modulo q as a response
and sends it to the Verifier. The Verifier accepts the Prover as securely identified
if gz is found to be congruent modulo p to the quantity g
uy
z.
Another type of user identification technique relies on the difficulty of
factoring a product of two large prime numbers. A user identification technique
of this type is described in L. C. Guillou and J. J. Quisquater, "A Practical Zero-Knowledge
Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory,"
in C. G. Gunther, Ed. Advances in Cryptology—Eurocrypt '88, Lecture Notes
in Computer Science 330, Springer-Verlag, 1988, pp. 123-128. This technique
involves a Prover raising a randomly selected argument g to a power b modulo n
and sending it to a Verifier. An instance of the Guillou-Quisquater technique uses
two prime numbers p and q selected at random, a number n generated as the product
of p and q, and a large prime number b also selected at random. The numbers n and
b are made available to all users. The private key of the Prover is x modulo n
and the public key y of the Prover is x
-b modulo n. The Prover initiates
the identification process by randomly selecting the number g from the set of non-zero
numbers modulo n. The Prover computes the quantity g
b modulo n and sends
it as a commitment to the Verifier. The Verifier randomly selects a number c from
the set of non-zero numbers modulo b and sends c as a challenge to the Prover.
The Prover computes the number h that is equal to the quantity gx
c modulo
n as a response and sends it to the Verifier. The Verifier accepts the Prover as
securely identified if g
b is found to be congruent modulo n to h
by
c.
Although the above-described Schnorr and Guillou-Quisquater techniques can
provide acceptable performance in many applications, there is a need for an improved
technique which can provide greater computational efficiency than these and other
prior art techniques, and which relies for security on features other than discrete
logarithms and integer factorization.
SUMMARY OF THE INVENTION
The present invention provides a method, system and apparatus for performing
user identification, digital signatures and other secure communication functions
based on ring homomorphisms. The ring homomorphism in accordance with the invention
may utilize two rings R and B, a ring homomorphism ø:R→B, and four
subsets R
f, R
g, R
h, and R
c, of R. One
element f in the set R
f serves as a private key for a given user. The
result ø(f) of evaluating the homomorphism ø at the element f serves
as the public key of the given user.
Copending U.S. patent application Ser. No. 08/954,712, filed Oct. 20, 1997,
and assigned, in joint ownership, to the same assignee as the present Application,
discloses a user identification technique and digital signature technique based
on partial evaluation of constrained polynomials over a finite field, and describes
use of a response signal (such as in a commitment/challenge/response type of technique)
that is generated by computing a polynomial as the product of a commitment polynomial
with the sum of a private key and a challenge polynomial. The techniques hereof
provide substantial improvements in computational efficiencies and lowering of
processing requirements at equivalent security levels.
In accordance with one aspect of the invention, a secure user identification
technique
is provided in which one of the system users, referred to as a Prover, randomly
selects an element g from the set R
g. The Prover evaluates the homomorphism
ø at the element g and transmits the result ø(g) to another user referred
to as the Verifier. The Verifier randomly selects a challenge element c from the
set R
c. The Verifier transmits c to the Prover. The Prover generates
a response element h using the private key f and the elements c and g. The element
h may be generated in the form g*(f+c*g) using addition + and multiplication *
in the ring R; or more generally by choosing a set of elements g
i, receiving
a set of challenge elements c
i, creating modified challenge elements
d
i from the challenge elements c
i, transmitting the modified
challenge elements d
i to the Verifier, and generating the response element
h as a polynomial function of the secret key f and the selected elements g
i,
c
i, and d
i. The Verifier checks that the element h is in
the set R
h. The Verifier also evaluates the homomorphism ø at the
element h and compares the result ø(h) to a function of ø(g), ø(c),
and the public key ø(f) of the Prover. For example, if the element h is generated
in the form g*(f+c*g), then the verifier may check if the value ø(h) is equal
to the value ø(g)*(ø(f)+ø(c)*ø(g)) using addition + and multiplication
* in the ring B. If the element h is in the set R
h and if the comparison
of ø(h) to the function of ø(g), ø(c), and the public key ø(f)
is correct, then the Verifier accepts the identity of the Prover. The Verifier
may use the above-noted comparison for secure identification of the Prover, for
authentication of data transmitted by the Prover, or for other secure communication functions.
In accordance with another aspect of the invention, a secure user identification
technique is provided in which one of the system users, referred to as a Verifier,
randomly selects a challenge element c from the set R
c. The Verifier
transmits c to another user referred to as the Prover. The Prover randomly chooses
an element g from the set R
g and generates a response element h using
the private key f and the elements c and g. The element h may be generated in the
form g*(f+c*g) using addition + and multiplication * in the ring R; or more generally
by generating the response element h as a polynomial function P(f,c,g) of the secret
key f and the selected elements g and c. The Verifier checks that the element h
is in the set R
h. The Verifier also evaluates the homomorphism φ
at the element h and verifies that the polynomial equation P(ø(f),ø(c),X)-ø(h)=0
has a solution X in the ring B. For example, if the element h is generated in the
form g*(f+c*g), then the verifier may check if the polynomial ø(c)X
2+ø(f)X-ø(h)=0
has a solution in B by checking if the element ø(f)
2+4ø(c)ø(h)
is the square of an element in B. If the element h is in the set R
h and
if the polynomial equation P(ø(f),ø(c),X)-ø(h)=0 has a solution
X in the ring B, then the Verifier accepts the identity of the Prover. The Verifier
may use the above-noted comparison for secure identification of the Prover, for
authentication of data transmitted by the Prover, or for other secure communication functions.
In accordance with another aspect of the invention, a digital signature technique
is provided. A Prover randomly selects an element g from the set R
g.
The Prover then computes ø(g) and applies a hash function to the element ø(g)
and a message m to generate a challenge element c=Hash(ø(g),m) in the set
R
c. The Prover utilizes g, c, and the private key f to generate an element
h. The element h may be generated in the form g*(f+c*g) using addition + and multiplication
* in the ring R, or more generally by choosing a set of polynomials g
i,
generating a corresponding set of elements c
i using the hash function,
and generating the response element h as a polynomial function h=P(f,c
i,g
i).
The Prover than transmits m, ø(g) and h to the Verifier. The Verifier checks
that the element h is in the set R
h. The Verifier computes c=Hash(ø(g),m),
evaluates ø(c) and ø(h), and compares the values of ø(g), ø(c),
and ø(h) with the public key ø(f) of the Prover. For example, if the
element h is generated in the form g*(f+c*g), then the verifier may check if the
value ø(h) is equal to the value ø(g)*(ø(f)+(c)*ø(g)) using
addition + and multiplication * in the ring B. If the element h is in the set R
h
and if the comparison of ø(h) to the function of ø(g), ø(c),
and the public key ø(f) is correct, then the Verifier accepts the signature
of the Prover on the message m.
In accordance with another aspect of the invention, a digital signature technique
is provided. A Prover randomly selects an element g from the set R
g.
The Prover then applies a hash function to a message m to generate a challenge
element c=Hash(m) in the set R
c. The Prover utilizes g, c, and the private
key f to generate an element h. The element h may be generated in the form g*(f+c*g)
using addition + and multiplication * in the ring R; or more generally by generating
the response element h as a polynomial function P(f,c,g) of the secret key f and
the selected elements g and c. The Prover than transmits m and h to the Verifier.
The Verifier checks that the element h is in the set R
h. The Verifier
computes c=Hash(m), evaluates ø(c) and ø(h), and verifies that the polynomial
equation ø(P)(ø(f),ø(c), X)-ø(h)=0 has a solution X
in the ring B, where ø(P) is the polynomial P with the homomorphism øapplied
to its coefficients. For example, if the element h is generated in the form g*(f+c*g),
then the verifier may check if the polynomial ø(c)X
2+ø(f)X-ø(h)=0
has a solution in B by checking if the element ø(f)
2+4ø(c)ø(h)
is the square of an element in B. If the element h is in the set R
h
and if the polynomial equation ø(P)(ø(f),ø(c),X)-ø(h)=0
has a solution X in the ring B, then the Verifier accepts the signature of the
Prover on the message m.
The present invention provides a method, system and apparatus for performing
user identification, digital signatures and other secure communication functions
based more particularly on ring homomorphisms given by partial evaluation of constrained
polynomials over a finite field. The ring R in accordance with the invention may
utilize polynomials of degree less than N with coefficients in the field F
q
of q elements, where N divides q-1 and q is a power of a prime number. An exemplary
predetermined condition on the subsets R
f, R
g and R
c
of R may specify that the coefficients are chosen from a predetermined set
of values such as, for example, the values 0, 1, and -1 in the field F
q,
and an exemplary predetermined condition on the subset R
h may specify
that the coefficients are small, as for example the number q is a prime number,
the coefficients of h are chosen between -q/2 and q/2, and the sum of the squares
of the coefficients of h is smaller than q
2. A number of other conditions
on the subsets R
f, R
g and R
c may be used in conjunction
with or in place of these exemplary conditions. The partial evaluation ring homomorphism
in accordance with the invention may consist of a ring B=F
qs and
a set of elements a
1, . . . , a
s in a public subset S of
F
q and a homomorphism ø:R→B corresponding to evaluation
of a polynomial at the values in S according to the formula ø(p(X))=(p(a
1),
p(a
2), . . . , p(a
3)). An exemplary condition on the ring
R may specify that R is the ring of polynomials modulo the relation X
N-1
and an exemplary condition on the set of elements S may specify that each element
a
i in the set S satisfies the formula a
iN=1. A
number of other conditions on the ring R and on the set S may be used in conjunction
with or in place of these exemplary conditions.
The use of ring homomorphisms, and more particularly ring homomorphisms given
by partial evaluation of constrained polynomials over a finite field, in accordance
with the invention provides user identification and digital signature techniques
which are computationally more efficient than prior art techniques. The security
of the techniques of the present invention depend on the fact that recovering an
element of a ring from its value by a homomorphism, and more particularly recovering
a polynomial from its partial evaluation, can, in certain circumstances, be a particularly
difficult task.
Further features and advantages of the invention will become more readily
apparent from the following detailed description when taken in conjunction with
the accompanying drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of a type of system that can be used in practicing
embodiments of the invention, for example when the processors thereof are suitably
programmed in accordance with the flow diagrams hereof.
FIG. 2 is a flow diagram which illustrates a key creation technique in accordance
with an exemplary embodiment of the present invention.
FIG. 3 is a flow diagram which illustrates a user identification technique in
accordance with an exemplary embodiment of the present invention.
FIG. 4 is a flow diagram which illustrates a further user identification technique
in accordance with another exemplary embodiment of the present invention.
FIG. 5 is a flow diagram which illustrates a digital signature technique in
accordance with an exemplary embodiment of the present invention.
FIG. 6 is a flow diagram which illustrates a further digital signature technique
in accordance with another exemplary embodiment of the present invention.
DETAILED DESCRIPTION
FIG. 1 is a block diagram of a system that can be used in practicing embodiments
of the invention. A number of processor-based subsystems, represented at
105,
155,
185, and
195, are shown as being in communication over
an insecure channel or network
50, which may be, for example, any wired,
optical, and/or wireless communication channel such as a telephone or internet
communication channel or network. The subsystem
105 includes processor
110
and the subsystem
155 includes processor
160. When programmed in
the manner to be described, the processors
110 and
160 and their
associated circuits can be used to practice embodiments of the invention. The processors
110 and
160 may each be any suitable processor, for example an electronic
digital processor or microprocessor. It will be understood that any general purpose
or special purpose processor, or other machine or circuitry that can perform the
functions described herein, electronically, optically, or by other means, can be
utilized. The processors may be, for example, Intel Pentium processors. The subsystem
105 may typically include memories
123, clock and timing circuitry
121, input/output functions
118, and monitor
125, which may
all be of conventional types. Inputs can include a keyboard input as represented
at
103 and any other suitable input. Communication is via transceiver
135,
which may comprise a modem, high speed coupler, or any suitable device for communicating
signals. The subsystem
155 in this illustrative system can have a similar
configuration to that of subsystem
105. The processor
160 has associated
input/output circuitry
164, memories
168, clock and timing circuitry
173, and a monitor
176. Inputs include a keyboard
163 and
any other suitable input. Communication of subsystem
155 with the outside
world is via transceiver
162 which, again, may comprise a modem, high speed
coupler, or any suitable device for communicating signals. As represented in the
subsystem
155, a terminal
181 can be provided for receiving a smart
card
182 or other media. A "user" can also be a person's or entity's "smart
card", the card and its owner typically communicating with a terminal in which
the card is inserted. The terminal can be an intelligent terminal, or can communicate
with an intelligent terminal. It will be understood that the processing and communications
media that are described are exemplary, and that the invention can have application
in many other settings. The blocks
185 and
195 represent further
subsystems on the channel or network.
The present invention will be illustrated below in conjunction with exemplary
user identification and digital signature techniques carried out by a Prover and
a Verifier in a communication network such as that of FIG. 1 in which, for example,
for a particular communication or transaction, any of the subsystems can serve
either role. It should be understood, however, that the present invention is not
limited to any particular type of application. For example, the invention may be
applied to a variety of other user and data authentication applications. The term
"user" may refer to both a user terminal as well as an individual using that terminal,
and, as indicated above, the terminal maybe any type of computer or other digital
data processor suitable for directing data communication operations. The term "Prover"
as used herein is intended to include any user which initiates an identification,
digital signature or other secure communication process. The term "Verifier" is
intended to include any user which makes a determination as to whether a particular
communication is legitimate. The term "user identification" is intended to include
identification techniques of the challenge-response type as well as other types
of identification, authentication and verification techniques.
The user identification and digital signature techniques in accordance with the
present invention are based on evaluation of ring homomorphisms. An exemplary embodiment
of the present invention is based on the partial evaluation homomorphism of constrained
polynomials over a finite field. An exemplary finite field F
q=Z/qZ is
defined for a prime number q. An exemplary ring R=F
q[X]/(X
q-1-1)
is a ring of polynomials with coefficients in the finite field F
q modulo
the ideal generated by the polynomial X
q-1-1. An exemplary homomorphism
ø:R→F
qs is a homomorphism ø(f(X))=(f(a
1),
. . . , f(a
t)) for an ordered set S={a
1, . . . , a
t}
of non-zero integers modulo q. An additional exemplary condition is that if a is
in S, then a
-1 is also in S. With suitable restrictions on f(X) and
a suitable choice of set S, it is infeasible to recover f(X) when given only ø(f(X)).
As will be described in greater detail below, this provides a one-way function
which is particularly well-suited to use in implementing efficient user identification
and digital signatures.
The identification and digital signature techniques make use of the multiplication
rule in the ring R. Given a polynomial A(X)=A
0+A
1X+ . . .
+A
q-2X
q-2 in R and a polynomial B(X)=B
0+B
1X+
. . . +B
q-2X
q-2 in R, an exemplary product may be given by:
where C
0, . . . , C
q-2 are given by:
All reference to multiplication of polynomials in the remaining description should
be understood to refer to the above-described exemplary multiplication in R. It
should also be noted that the above-described multiplication rule is not a requirement
of the invention, and alternative embodiments may use other types of multiplication rules.
An exemplary set of constrained polynomials R
f is the set of polynomials
in R with bounded coefficients. Given the prime number q and the polynomial f(X),
it is relatively easy to generate ø(f)=(f(a
1), . . . , f(a
t)).
However, appropriately selected restrictions on the polynomials in R
f can
make it extremely difficult to invert this function to determine a polynomial F(X)
in R
f such that ø(F)=ø(f). The difficulty of the inversion
is generally dependent on the type of restrictions placed on the polynomials in
R
f. For example, if easily satisfied restrictions are placed on the
polynomials, basic interpolation techniques could be used to find some polynomial
F(X) in R
f such that ø(F)=ø(f). It will be shown in greater
detail below that establishing appropriate restrictions on the polynomials in R
f
can provide adequate levels of security. An exemplary identification technique
in accordance with the invention uses a number of system parameters which are established
by a central authority and made public to all users. These system parameters include
the above-noted prime number q and set S={a
1, . . . , a
t}
of t non-zero elements of the finite field F
q and appropriate sets of
bounded coefficient polynomials R
f,R
g,R
c. FIG.
2 illustrates the creation of a public/private key pair. After establishment of
parameters (block
220) a Prover randomly chooses a secret polynomial f(X)
in R
f as its private key (block
230). The public key of the Prover
is then generated as ø(f)=(f(a
1), . . . , f(a
t)) which
represents the ordered evaluation of the secret polynomial f(X) at the t elements
of S, and the public key can be published (block
240).
FIG. 3 illustrates an exemplary identification process. The identification process
is initiated in the Commitment Phase (block
310) by the Prover generating
a polynomial g(X) with bounded coefficients. The polynomial g(X) may be selected
at random from a set R
g that is restricted in a manner to be described
below. The Prover uses the polynomial g(X) and the public set of values S={a
1,
. . . , a
t} to compute a commitment ø(g)=(g(a
1), . .
. , g(a
t)) and sends the commitment to the Verifier.
The Verifier initiates the Challenge Phase (block
330) by generating a
challenge polynomial c(X) with bounded coefficients and sending it to the Prover.
The polynomial c(X) may be generated by random selection from a set of polynomials
R
c that is restricted in a manner to be described below. The Prover
initiates the Response Phase (block
350) by verifying that the challenge
polynomial c(X) is in the restricted set of polynomials R
c and then
using the polynomials c(X),g(X) and the secret polynomial f(X) to generate the
response polynomial h(X) given by
and sending the response polynomial h(X) to the Verifier. The Verifier initiates
the Verification Phase (block
360) by using its knowledge of ø(g),
c(X), and the public key ø(f) to check that the response polynomial h(X) was
generated using the private key f(X) of the Prover by comparing:
This check may be expressed as comparing whether ø(h) is equal to ø(g)(ø(f)+ø(c)ø(g)).
The Verifier in the Verification Phase also checks whether or not the coefficients
of h(X) are appropriately bounded, given that a legitimate h(X) will have bounded
coefficients and will belong to a restricted set R
h of polynomials.
The restrictions on the set R
h depend on the choice of the above noted
sets R
f,R
g and R
c. The Verifier accepts the Prover
as legitimate if the response polynomial h(X) transmitted by the Prover passes
the checks of steps (A) and (B) of the Verification Phase. The Verifier may perform
a number of other checks as part of the identification process. For example, prior
to performing steps (A) and (B) of the Verification Phase, the Verifier may check
that g(1), provided by the Prover as an element of the commitment ø(g), has
a particular expected value.
A first exemplary set of system parameters suitable for use with the above-described
identification technique will now be described. It should be emphasized that these
and other exemplary parameters described herein are illustrative only and that
numerous alternative sets of parameters could also be used. In the first exemplary
set of parameters, the prime number q is selected as
769, and the set S
includes t=384 non-zero integers modulo q. The set S is constructed such that if
a is an element of S, then a
-1 is also an element of S. It should be
noted that a given implementation may utilize only a subset of the t elements of
S. The set R
f is the set of all polynomials f(X) of degree less than
768 constructed with 51 coefficients of value 1, with 51 coefficients of value
-1, and all other coefficients set to zero. The set R
g is the set of
all polynomials g(X) of degree less than 768 constructed with 51 coefficients of
value 1, with 51 coefficients of value -1, and all other coefficients set to zero.
The set R
c is the set of all polynomials c(X) of degree less than 768
constructed with 5 coefficients of value 1, with
