Abstract
We investigate the problem of generating a global, unpredictable coin in a distributed system. A fast, efficient solution is of fundamental importance to distributed protocols, especially those that rely on broadcast channels. We present two unpredictable bit generators, based on the Blum-Blum-Shub generator, that can be evaluated non-interactively; that is, each bit (or group of bits) requires each processor merely to send one message to the other processors, without requiring a broadcast or Byzantine Agreement.
The unpredictability of our generators (and the security of our protocols) are based provably on the QRA or the intractability of factoring. Remarkably, their structure seems to violate an impossibility result of [8], but our generators escape that lower bound because they achieve a slightly weaker goal: producing unpredictable bits directly, rather than producing “shares” of random bits. In doing so, they avoid the extra machinery (eg., “sharing shares”) of similar results discovered independently in [8].
Chapter PDF
Similar content being viewed by others
Keywords
- Secret Sharing
- Pseudorandom Sequence
- Broadcast Channel
- Pseudorandom Number Generator
- Impossibility Result
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
W. Alexi, B. Chor, O. Goldreich, C.P. Schnorr. “RSA and Rabin Functions: Certain Parts are as Hard as the Whole.” SIAM J. Computing, 17:2 (1988), 194–209.
D. Beaver. “Foundations of Secure Interactive Computing.” Proc. of Crypto 1991, 377–391.
D. Beaver, H. Shan. In preparation.
M. Ben-Or. “Another Advantage of Free Choice.” Proc. of 2nd PODC, 1983.
Blakley, “Security Proofs for Information Protection Systems.” Proceedings of the the 1980 Symposium on Security and Privacy, IEEE Computer Society Press, NY (1981), 79–88.
M. Blum, S. Micali. “How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits.” SIAM J. Comput. 13 (1984), 850–864.
L. Blum, M. Blum, M. Shub. “A Simple Unpredictable Pseudo-Random Number Generator.” SIAM J. Computing, 15:2 (1986), 364–383.
M. Cerecedo, T. Matsumoto, H. Imai. “Non-Interactive Generation of Shared Pseudorandom Sequences.” To appear, Auscrypt 92.
P. Feldman. “A Practical Scheme for Non-Interactive Verifiable Secret Sharing.” Proc. of the 28th FOCS, IEEE, 1987, 427–437.
O. Goldreich, S. Goldwasser, S. Micali. “How to Construct Random Functions.” JACM 33:4 (1986), 792–807.
S. Goldwasser, S. Micali. “Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information.
S. Micali, P. Rogaway. “Secure Computation.” Proc. of Crypto 1991, 392–404.
M. Pease, R. Shostak, L. Lamport. “Reaching Agreement in the Presence of Faults.” JACM 27:2 (1980), 228–234.
T. Pedersen. “Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing.” Proceedings of CRYPTO 91, 129–140.
M.O. Rabin. “Digitalized Signatures and Public-Key Functions as Intractable as Factorization.” Technical Report LCS/TR-212, MIT, January, 1979.
M.O. Rabin. “Randomized Byzantine Generals.” Proc. of the 24th FOCS, IEEE, 1983, 403–409.
A. Shamir. “How to Share a Secret.” Communications of the ACM, 22 (1979), 612–613.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beaver, D., So, N. (1994). Global, Unpredictable Bit Generation Without Broadcast. In: Helleseth, T. (eds) Advances in Cryptology — EUROCRYPT ’93. EUROCRYPT 1993. Lecture Notes in Computer Science, vol 765. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48285-7_36
Download citation
DOI: https://doi.org/10.1007/3-540-48285-7_36
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57600-6
Online ISBN: 978-3-540-48285-7
eBook Packages: Springer Book Archive