Robust efficient distributed RSA-key generation

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

1999-05-21

2001-05-22

Barron, Jr., Gilberto (Department: 2132)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C380S030000, C380S286000, C380S277000, C380S045000, C708S491000, C708S492000

Reexamination Certificate

active

06237097

ABSTRACT:

The application relates to the field of electronics and data processing, and particularly to methods and apparatus for generating cryptographic keys.
BACKGROUND
The notion of distributed cryptographic protocols has been in cryptography for over fifteen (15) years. Some protocols have been designed to solve communication problems which are impossible from an information-theoretic perspective, like the coin-flipping protocol [B82] and the millionaire-problem protocol [Y82]. Other protocols have been designed to solve generic problems. These protocols (called “general compiler protocols”) can securely compute any public function on secure inputs. The first such protocols were developed by Yao [Y86] and Goldreich, Micali and Wigderson [GMW], and various developments were made in subsequent works, e.g., [GHY, K, BGW, CCD].
Recently there has been a thrust to construct more efficient protocols for problems involving the distributed application of cryptographic functions (surveyed in GW97). Function sharing protocols are needed to provide increased memory security, distributed trust, and flexible management (i.e., adding and deleting trustees) of crucial functions like certification authorities and group signatures.
A major efficiency difference between a general compiler protocol (which should be thought of as a plausibility result—see [Gr97]) and a function sharing protocol results from the fact that the communication complexity of the former depends linearly on the actual size of the circuit computing the cryptographic functions, while the communication complexity of the latter is independent of the circuit size (and is typically a polynomial in the input/output size and the number of participants). This difference (pointed out first in FY93, DDFY94) is crucial to practitioners who require efficient protocols. A function sharing protocol involves a protocol for applying the function (based on distributed shares), and sometimes (in what is called a “proactive model”) also a protocol for re-randomizing the function shares.
Another important step regarding “distributed cryptographic functions” is the (efficient) distributed generation of the function (the key shares). For cryptographic functions based on modular exponentiation over a field (whose inverse is the discrete logarithm which is assumed to be a one-way function), a protocol for the distributed generation of keys was known [P2]. However, for the RSA function and related cryptographic functions to be described below, which requires the generation of a product of two primes and an inverse of a public exponent, this step was an open problem for many years. Note that Yao's central motivation [Y86] is introducing general compiler protocols that “computer circuits securely in communication” was the issue of distributed generation of RSA keys. Indeed the results of [Y86, GMW] show the plausibility of this task.
Another step forward was achieved by Boneh and Franklin [BF97] who showed how a set of participants can generate an RSA function efficiently, thus detouring the inefficient compiler. They showed that their protocol was secure in the limited model of “trusted but curious” parties. They left open the issue of robustness, i.e., generation in the presence of misbehaving (malicious) parties. If adversaries misbehave arbitrarily, the Boneh-Franklin protocol may be prevented from ever generating a shared RSA key (due to lack of robustness).
The following references provide additional background for the invention.
[ACGS] W. Alexi, B. Chor, O. Goldreich and C. Schnorr. RSA and Rabin Functions: Certain Parts are as Hard as the Whole. In
SIAM Journal of Computing
, volume 17, n. 2, pages 194-209, April 1988.
[B84] E. Bach, “Discrete Logarithms and Factoring”, Tech. Report No. UCB/CSD 84/186. Computer Science Division (EECS), University of California, Berkeley, Calif., June 1984.
[BGW] Ben-Or M., S. Goldwasser and A. Wigderson, Completeness Theorem for Non cryptographic Fault-tolerant Distributed Computing, STOC 1988, ACM, pp. 1-10.
[B82] M. Blum, “Coin flipping by telephone: a protocol for solving impossible problems,” IEEE Computer Conference 1982, 133-137.
[BF97] D. Boneh and M. Franklin, Efficient Generation of Shared RSA Keys, Crypto 97, pp. 425-439.
[B88] C. Boyd, Digital Multisignatures, IMA Conference on Cryptography and Coding, Claredon Press, 241-246 (eds. H. Baker and F. Piper), 1986.
[BCLL] G. Brassard, C. Crepeau, S. Laplante, C. Leger. Computationally Convincing proofs of knowledge, In Proceedings of the 8
th
Symp. On Theoretical Aspects of Computer Science (Springer, Berlin, 1991), pp. 251-262.
[BGM] E. Brickell, D. Gordon and K. McCurley. Fast Exponentiation with Precomputation Advances in Cryptology—Eurocrypt 92 Proceedings, Lecture Notes in Computer Science, Vol. 658, R. Rueppel ed., Springer-Verlag, 1992.
[CCD] D. Chaum, C. Crepeau and I. Damgard, Multiparty Unconditionally Secure Protocols, STOC 1988, ACM, pp. 11-19.
[CEG] D. Chau, M.-H. Evertse and J. van de Graff, Multiparty computations ensuring privacy of each party's input and correctness of the result, Advances in Cryptology—Europcrypt 88 Proceedings, Lecture Notes in Computer Science, Vol. 330, C. Gunther ed., Springer-Verlag, 1988 pp. 87-119.
[CEGP] D. Chaum, J.-H. Evertse, J van de Graaf and R. Peralta, An improved protocol for demonstrating possession of discrete logarithms and some generalizations, Advances in Cryptology—Crypto 86 Proceedings, Lecture Notes in Computer Science, Vol. 263, A. Odlyzko ed., Springer-Verlag, 1986, pp. 200-212.
[CGMA] B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, Verifiable Secret Sharing and Achieving Simultaneous Broadcast, Proceedings of the 26
th
Symposium on Foundations of Computer Science, IEEE, 1985, pp. 335-344.
[DDFY94] A. DeSantis, Y. Desmedt, Y. Frankel and M. Yung, How to Share a Function Securely, ACM Proceedings of the 26
th
Annual Symposium on Theory of Computing, ACM, 1994, pp. 522-533.
[DF89] Y. Desmedt and Y. Frankel, Threshold cryptosystems, Advances in Cryptology—Crypto 89 Proceedings, Lecture Notes in Computer Science, Vol. 435, G. Brassard ed., Springer-Verlag, 1989, pp. 307-315.
[DH] W. Diffle and M. Hellman, New Directions in Cryptography, IEEE Trans. On Information Theory 22(6), 1976, pp. 644-654.
[FFS] U. Feige, A. Fiat and A. Shamir, Zero-Knowledge Proof of Identity,. Proceedings of the Nineteenth annual ACM symp. Theory of Computing, 1987, pp. 210-217.
[F] P. Feldman, A Practical Scheme for Non-Interactive Certifiable Secret Sharing, Proceedings of the 28
th
Symposium on Foundations of Computer Science, IEEE, 1987, pp. 427-437.
[FS86] A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems,” in Advances in Cryptology—CRYPTO '86 Proceedings (Lecture Notes in Computer Science, Vol. 263), ed. A. Odlyzko 186-194, Springer-Verlag, New York, 1987.
[FGY] Y. Frankel, P. Gemmell and M. Yung, Witness Based Cryptographic Program Checking and Robust Function Sharing, Proceedings of the 28
th
Annual Symposium on Theory of Computing, ACM 1996, pp. 499-508.
[FGMY] Y. Frankel, P. Gemmel, P. MacKenzie and M. Yung, Proactive RSA, Crpto 97.
[FGMYa] Y. Frankel, P. Gemmel, P. MacKenzie and M. Yung, Optimal Resilience Proactive Public-Key Cryptosystems, FOCS 97.
[FS89] U. Feige and A. Shamir, Zero knowledge proofs of knowledge in two rounds, CRYPTO 1989, 20-24.
[FY93] M. Franklin and M. Yung, Secure and Efficient Off-line Digital Money, Porch. Of the 20
th
Int. Col. On Automata, Languages and Programming (ICALP), 1993, LNCS 700, Springer-Verlag, pp. 265-276.
[GHY] Z. Galil, S. Haber, and M. Yung, Minimum-Knowledge Interactive Proof for Decision Problems, SIAM j. Comp., 18, 9189, pp. 711-739.
[GHY85] Z

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-2533730