Robust efficient distributed RSA-key generation

Details Robust efficient distributed RSA-key generation Robust efficient distributed RSA-key generation

2007-12-25

2007-12-25

Zand, Kambiz (Department: 2134)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S168000, C713S172000, C713S173000, C713S174000, C705S064000

Reexamination Certificate

active

09860441

ABSTRACT:
The invention provides for robust efficient distributed generation of RSA keys. An efficient protocol is one which is independent of the primality test “circuit size”, while a robust protocol allows correct completion even in the presence of a minority of arbitrarily misbehaving malicious parties. The disclosed protocol is secure against any minority of malicious parties (which is optimal). The disclosed method is useful in establishing sensitive distributed cryptographic function sharing services (certification authorities, signature schemes with distributed trust, and key escrow authorities), as well as other applications besides RSA (namely: composite ElGamal, identification schemes, simultaneous bit exchange, etc.). The disclosed method can be combined with proactive function sharing techniques to establish the first efficient, optimal-resilience, robust and proactively-secure RSA-based distributed trust services where the key is never entrusted to a single entity (i.e., distributed trust totally “from scratch”). The disclosed method involves new efficient “robustness assurance techniques” which guarantee “correct computations” by mutually distrusting parties with malicious minority.

REFERENCES:
patent: 4351982 (1982-09-01), Miller et al.
patent: 6237097 (2001-05-01), Frankel et al.
Davenport, J.H., “Primality Testing Revisited”, Papers from the International Symposium on Symbolic and algebraic Computation, 1992, ACM, pp. 123-129.
Alexi et al., RSA and Rabin Functions: “Certain Parts Are As Hard As The Whole”, Apr. 1988, vol. 17, n. 2, pp. 194-209, In SIAM Journal of Computing.
Ben-Or M. et al., “Completeness Theorem for Non cryptographic Fault-tolerant Distributed Computing”, STOC 1988, pp. 1-10, ACM.
Blum, M. “Coin Flipping By Telephone: a protocol for solving impossible problems,” 1982, pp. 133-137, IEEE Computer Conference.
D. Boneh et al., Efficient Generation of Shared RSA Keys, Crypto 97, pp. 425-439.
Boyd, C., Digital Multisignatures, IMA Conference on Cryptography and Coding, 1986, pp. 241-246, Claredon Press (eds. H. Baker and F. Piper).
Brassard et al., Computationally Convincing Proofs Of Knowledge, In Proceedings of the 8thSymp. On Theoretical Aspects of Computer Science, pp. 251-262, (Springer, Berlin, 1991).
Brickell et al., Exponentiation with Precomputation Advances in Cryptology—Eurocrypt 92 Proceedings, Lecture Notes in Computer Science, vol. 658, 1992, R. Rueppel ed., Springer-Verlag.
Chaum et al., Multiparty Unconditionally Secure Protocols, STOC 1988, pp. 11-19, ACM.
Chaum, D. et al. An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations, Advances in Cryptology—Crypto 86 Proceedings, vol. 263, Lecture Notes in Computer Science, 1986, pp. 200-212 Springer-Verlag, A. Odlyzko ed.
Chor et al. “Verifiable Secret Sharing and Achieving Simultaneous Broadcast,” Proceeding of the 26thSymposium on Foundations of Computer Science, IEEE, pp. 235-344, 1985.
DeSantis et al. How To Share A Function Securely, ACM Proceedings of the 26thAnnuyal Symposium on Theory of Computing, 1994, pp. 522-533, ACM.
Desmedt et al., Threshold Cryptosystems, Advances in Cryptology—Crypto 89 Proceedings, vol. 435, Lecture Notes in Computer Science, 1989, pp. 307-315, Springer-Verlag, G. Brassard ed.
Diffle et al. New Directions in Cryptography, IEE Trans. on Information Theory 22(6), 1976, pp. 644-654.
Feldman et al., “A Practical Scheme for Non-Interactive Certifiable Secret Sharing”, Proceedings of the 28thSymposium on Foundations of Computer Science, IEEE, 1987, pp. 427-437.
Fiat et al., “How To Prove Yourself: Practical Solutions To Identification and Signature Problems,” in Advances in Cryptology—Crypto '86 Proceedings, vol. 263, Lecture Notes in Computer Science, 1987, pp. 186-194, Springer-Verlag, New York (ed. A. Odlyzko).
Frankel et al., “Witness Based Cryptographic Program Checking and Robust Function Sharing”, Proceedings of the 28thAnnual Symposium on Theory of Computing, 1996, pp. 499-508, ACM.
Frankel et al., “Proactive RSA”, Crypto 97.
Frankel et al., “Optimal Resilience Proactive Public-Key Cryptosystems”, FOCS 97.
Feige et al., “Zero Knowledge Proofs of Knowledge in Two Rounds”, pp. 526-544, Crypto 1989.
Feige et al., “Zero Knowledge Proofs of Identity”, The Weizmann Institute of Science, Department of Applied Mathematics, Rohovot, Israel, ACM Press pp. 210-217.
Franklin et al., “Secure and Efficient Off-line Digital Money”, Porch. of the 20thInt. Col. On Automata, Languages and Programming (ICALP), 1993, LNCS 700, Springer-Verlag, pp. 265-276.
Galil et al., Minimum-Knowledge Interactive Proof for Decision problems, SIAM Computer Journal, vol. 18, 9189, pp. 711-739.
Galil et al., Symmetric Public-Key Cryptography,m Crypto 85.
Galil et al., “Cryptographic Computations: Secure Fault Tolerant Protocols in the Public Key Model”, Crypto 87, pp. 135-155.
Gennaro et al., “Robust Threshold DSS Signatures”, Advances in Cryptology—Eurocrypt 96 Proceedings, vol. 1070, Lecture Notes in Computer Science, 1996, pp. 354-371, Springer-Verlag.
Goldreich, O., “On Foundations of Modern Cryptography”, Crypto 97, an invited paper.
Goldreich et al., “Proofs That Yield Nothing But Their Validity And a Methodology of Cryptographic Protocol Design,” IEEE FOCS, pp. 174-187, 1986.
Goldreich et al., “How To Play Any Mental Game”, Proceedings of the 19thAnnual ACM Symposium, 1987, pp. 218-229, Theory of Computing.
Goldwasser, S., “A New Direction In Cryptography: Twenty Something Years After”, FOCS 97, an invited paper.
Goldwasser et al., “The Knowledge Complexity of Interactive Proof-Systems”, SIAM Journal on Computing, vol. 18(1), 1989, pp. 186-208.
Hardy et al. An Introduction To The Theory Of Numbers, 1985, Oxford Science Publications, London, Great Britain, 5thed.
Impagliazzo et al., “Direct Minimum-Knowledge Computation”, in Advances in Cryptology—Crypto '87, Proceedings, 1988, Lecture Notes in Computer Science, vol. 293, Springer-Verlag, New York, ed. C. Pomerance, 40-50.
Kilian, J., “Founding Cryptography On Oblivious Transfer,”, 1988, ACM STOC, pp. 20-31.
Miller, G., “Riemann's Hypothesis And Test of Primality”, Journal of Computer and System Sciences, vol. 13, 1976, pp. 300-317.
Okamoto, T., “Provably Secure and Practical Identification and Corresponding Signature Scheme, Advances in Cryptology”—Crypto 92 Proceedings, vol. 740, Lectures Notes in Computer Science, 1992 Springer-Verlag, pp. 31-53 (E. Brickell ed.).
Ostrovsky et al., “How To Withstand Mobile Virus Attacks”, Proceedings of the 10thACM Symposium on the Principles of Distributed Computing, pp. 51-61, 1991.
Pedersen, T.P., “Distributed Provers With Applications to Undeniable Signatures”, Advances in Cryptology—Eurocrypt 91 Proceedings, vol. 547, Lecture Notes in Computer Science, 1991, pp. 221-242, Springer-Verlag.
Pedersen, T.P., “A Threshold Cryptosystem Without A Trusted Party”, Advances in Cryptology—Eurocrypt 91 Proceedings, vol. 547, Lectures Notes in Computer Science, 1991, pp. 129-140, Springer-Verlag.
Pedersen, T.P., “Non-interactive And Information theoretic Secure Verifiable Secret Sharing”, Advances in Cryptology—Crypto 91 Proceedings, vol. 576, Lecture Notes in Computer Science, 1991, pp. 129-140, Springer-Verlag.
Rivest et al., “A Method For Obtaining Digital Signature and Public Key Cryptosystems”, vol. 21, Comm. of ACM, 1978, pp. 120-126.
Shamir, A. “How To Share A Secret”, vol. 22, Comm. of ACM, 1979, pp. 612-613.
Yao, A.C., “Theory And Applications of Trapdoor Functions”, Proceedings of the 23rdSymposium on the Founda

Affiliated with

Also associated with

Rating

Robust efficient distributed RSA-key generation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Robust efficient distributed RSA-key generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust efficient distributed RSA-key generation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3829171