Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
2005-10-25
2005-10-25
Peeso, Thomas R. (Department: 2131)
Cryptography
Particular algorithmic function encoding
Public key
C380S002000, C380S028000, C380S030000, C380S044000, C713S156000, C713S168000, C713S171000, C713S176000, C713S180000
Reexamination Certificate
active
06959085
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).
REFERENCES:
patent: 4995082 (1991-02-01), Schnorr
patent: 5054066 (1991-10-01), Riek et al.
patent: 5220606 (1993-06-01), Greenberg
patent: 5740250 (1998-04-01), Moh
patent: 5790675 (1998-08-01), Patarin
patent: 5805703 (1998-09-01), Crandall
patent: 5889865 (1999-03-01), Vanstone et al.
patent: 5974142 (1999-10-01), Heer et al.
patent: 5982891 (1999-11-01), Ginter et al.
patent: 6076163 (2000-06-01), Hoffstein et al.
patent: 6081597 (2000-06-01), Hoffstein et al.
patent: 6144740 (2000-11-01), Laih et al.
patent: 6286022 (2001-09-01), Kaliski et al.
patent: 6298137 (2001-10-01), Hoffstein et al.
patent: 6480605 (2002-11-01), Uchiyama et al.
patent: 6526509 (2003-02-01), Horn et al.
patent: 2737370 (1997-01-01), None
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.
Hoffstein Jeffrey
Lieman Daniel
Silverman Joseph H.
Novack Martin
NTRU Cryptosystems, Inc.
Peeso Thomas R.
Zla Syed A.
LandOfFree
Secure user identification based on ring homomorphisms does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Secure user identification based on ring homomorphisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Secure user identification based on ring homomorphisms will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3491306