Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
2005-10-04
2005-10-04
Caldwell, Andrew (Department: 2137)
Cryptography
Particular algorithmic function encoding
Public key
C380S277000, C713S169000
Reexamination Certificate
active
06952476
ABSTRACT:
A method of exchanging digital public-key verification data whereby a first computing entity (102) enables a second computing entity (104) to obtain probabilistic evidence that a given public-key number n is the product of exactly two odd primes p and q, not known to the second party, whose bit lengths (l(p), l(q)) differ by not more than d bits. The method provides an efficient proof of knowledge protocol for demonstrating Monte-Carlo evidence that a number n is the product of two odd primes of roughly equal size. The evidence is shown “in the dark”, which means that the structure is verified without the prime factors of n disclosed. The cost of a proof amounts to 12klog2n multiplications of integers of size of n where k is the number of the iterations in the proof and relates to an error probability bounded by max(½k, 24
1/4).
REFERENCES:
patent: 4405829 (1983-09-01), Rivest et al.
patent: 4633036 (1986-12-01), Hellman et al.
patent: 6411715 (2002-06-01), Liskov et al.
patent: 0 202 768 (1986-11-01), None
patent: 0 534 420 (1993-03-01), None
Mao, Wenbo. “Fast Monte-Carlo Primality Evidence Shown in the Dark”, Hewlett-Packard Company, Oct. 27, 1999.
Berger, Richard, et al., “A Framework for the Study of Cryptographic Protocols,”Advances in Cryptology-Proceedings of CRYPTO 85, Lecture Notes in Computer Science, Springer-Verlag, pp. 87-103 (Aug. 1985).
Blum, Manuel, “Coin flipping by telephone: a protocol for solving impossible problems,”Proceedings of 24th IEEE Computer Conference(CompCon), pp. 133-137 (Feb. 1982).
Goldwasser, Shafi, “Multi-Party Computations: Past and Present,”Proceeding of the 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 1-6 (Aug. 1997).
Camenisch, Jan and Michels, Markus, “Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes,”Advances in Cryptology-EUROCRYPT 99, Lecture Notes in Computer Science, Springer-Verlag, 1592, pp. 106-121 (1999).
Liskov, Moses and Silverman, Robert D., “A Statistical Limited-Knowledge Proof for Secure RSA Keys,”5th ACM Conference on Computer and Communications Security, IEEE P1363 Research Contributions, pp. 1-14 (1998).
Damgard, Ivan Bjerre, “Practical and Provable Secure Release of a Secret and Exchange of Signatures,”Advances in Cryptology-Proceedings of EUROCRYPT 93, Lecture Notes in Computer Science, Springer-Verlag, 765, pp. 200-217 (1994).
Karanakis, E.,Primality and Cryptography, Wiley-Teubner Series in Computer Science, John Wiley & Sons, p. 28 (1986).
Blackburn, S.R. and Galbraith, Steven D., “Certification of Secure RSA Keys,”Technical Report CORR 90-44, University of Waterloo Centre for Applied Cryptographic Research, pp. 1-10 (May 6, 1999).
Boyar, Joan, et al., “Practical Zero-Knowledge Proofs: Giving Hints and Using Deficiencies,.”Advances in Cryptology-Proceedings of EUROCRYPT 89, Lecture Notes in Computer Science, Springer-Verlag, 434, pp. 155-172 (1990).
Galil, Zvi, et al., “A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems,”26th FOCS, pp. 360-371 (1985).
Gennaro, Rosario, et al., “An Efficient Non-Interactive Statistical Zero-Knowledge Proof System for Quasi-Safe Prime Products,”5th ACM Conference on Computer and Communications Security, pp. 1-13 (Oct. 1998).
Van de Graaf, Jeroen and Peralta, Rene, “A Simple and Secure Way to Show the Validity of Your Public Key,”Advances in Cryptology-Proceedings of CRYPTO 87, Lecture Notes in Computer Science, Springer-Verlag, 293, pp. 128-134 (1988).
ISO/IEC 9798-3, “Information technology—Security techniques—Entity authentication mechanisms; Part 3; Entity authentication using a public key algorithm,” International Organization for Standardization, Geneva, Switzerland, pp. 1-9 (1993)
Micali, Silvio, “Fair Public-Key Cryptosystems,”Advances in Cryptology-Proceedings of CRYPTO 92, Lecture Notes in Computer Science, Springer-Verlag, 740, pp. 113-138 (1993).
Solovay, R. and Strassen, V., “A Fast Monte-Carlo Test for Primality,”SIAM Journal of Computing, vol. 6, No. 1, pp. 84-85 (Mar. 1977).
Caldwell Andrew
Davis Zachary
Hewlett--Packard Development Company, L.P.
LandOfFree
Verification of the private components of a public-key... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Verification of the private components of a public-key..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Verification of the private components of a public-key... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3450476