1994 | OriginalPaper | Buchkapitel
Global, Unpredictable Bit Generation Without Broadcast
verfasst von : Donald Beaver, Nicol So
Erschienen in: Advances in Cryptology — EUROCRYPT ’93
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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].