Abstract
We construct a protocol that enables a secret bit to be revealed gradually in a very controlled manner. In particular, if Alice possesses a bit S that was generated ran- domly according to the uniform distribution and 1/2 < p i < ... < p m = 1 then, using our protocol with Bob, Alice can achieve the following. The protocol consists of m stages and, after the i-th stage, Bob’s best prediction of 5, based on all his interac- tions with Alice, is correct with probability exactly p i- (and a reasonable condition is satisfied in the case where S is not initially uniform). Furthermore, under an in- tractability assumption, our protocol can be made “oblivious” to Alice and “secure” against an Alice or Bob that might try to cheat in various ways. Previously proposed gradual disclosure schemes for single bits release information in a less controlled man- ner: the probabilities that represent Bob’s confidence of his knowledge of 5 follow a random walk that eventually drifts towards 1, rather than a predetermined sequence of values.
Using controlled gradual disclosure schemes, we show how to construct an im- proved version of the protocol proposed by Luby, Micali and Rackoff for two-party secret bit exchanging (“How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin”, Proc. 22nd Ann. IEEE Symp. on Foundations of Computer Science, 1983, pp. 11–21) that is secure against additional kinds of attacks that the previous protocol is not secure against. Also, our protocol is more efficient in the number of rounds that it requires to attain a given level of security, and is proven to be asymptotically optimal in this respect.
We also show how to use controlled gradual disclosure schemes to improve existing protocols for other cryptographic problems, such as multi-party function evaluation.
Research partially conducted while the author was at the University of Toronto, partially supported by an NSERC postgraduate scholarship.
Chapter PDF
Similar content being viewed by others
References
D. Beaver, and S. Goldwasser, “Multiparty Computation with Faulty Majority”, Advances in Cryptology — CRYPTO’ 89 Proc, these proceedings.
M. Blum., “How to Exchange (Secret) Keys”, Proc. 15th Ann. ACM Symp. on Theory of Computing, 1983, pp. 440–447.
M. Blum, and S. Micali, “How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits”, Proc. 23th Ann. IEEE Symp. on Foundations of Computer Science, 1982, pp. 112–117.
G. Brassard, C. Crépeau, and J.-M. Robert, “Information Theoretic Reductions Among Disclosure Problems”, Proc. 27th Ann. IEEE Symp. on Foundations of Computer Science, 1986, pp. 168–173.
E. F. Brickell, D. Chaum, I. B. Damgård, and J. van de Graaf, “Gradual and Verifiable Release of a Secret”, Advances in Cryptology — CRYPTO’ 87 Proc, C. Pomerance (ed.), Lecture Notes in Computer Science 293, Springer, 1988, pp. 156–166.
O. Goldreich, S. Micali, and A. Wigderson, “Proofs That Yield Nothing But Their Validity and a Methodology for Cryptographic Protocol Design”, Proc. 27th Ann. IEEE Symp. on Foundations of Computer Science, 1986, pp. 174–187.
O. Goldreich, S. Micali, and A. Wigderson, “How to Play Any Mental Game”, Proc. 19th Ann. ACM Symp. on Theory of Computing, 1987, pp. 218–229.
S. Goldwasser, S. Micali, “Probabilistic Encryption & How to Play Mental Poker, Keeping Secret All Partial Information”, Proc. 14th Ann. ACM Symp. on Theory of Computing, 1982, pp. 365–377.
J. Y. Halpern, and M. O. Rabin, “A Logic to Reason About Likelihood”, Proc. 15th Ann. ACM Symp. on Theory of Computing, 1983, pp. 310–319.
M. Luby, S. Micali, and C. Rackoff, C, “How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin”, Proc. 22nd Ann. IEEE Symp. on Foundations of Computer Science, 1983, pp. 11–21.
T. Tedrick, “How to Exchange Half a Bit”, Advances in Cryptology: Proc. of CRYPTO’ 83, D. Chaum (ed.), Plenum, 1984, pp. 147–151.
U. Vazirani, and V. Vazirani, V., “Trapdoor Pseudo-Random Number Generators, With Applications to Protocol Design”, Proc. 22nd Ann. IEEE Symp. on Foundations of Computer Science, 1983, pp. 23–30.
A. Yao, “Theory and Applications of Trapdoor Functions”, Proc. 21st Ann. IEEE Symp. on Foundations of Computer Science, 1982, pp. 80–91.
A. Yao, “Protocols for Secure Computations”, Proc. 21st Ann. IEEE Symp. on Foundations of Computer Science, 1982, pp.160–169.
A. Yao, “How to Generate and Exchange Secrets”, Proc. 25th Ann. IEEE Symp. on Foundations of Computer Science, 1986, pp. 162–167.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cleve, R. (1990). Controlled Gradual Disclosure Schemes for Random Bits and Their Applications. In: Brassard, G. (eds) Advances in Cryptology — CRYPTO’ 89 Proceedings. CRYPTO 1989. Lecture Notes in Computer Science, vol 435. Springer, New York, NY. https://doi.org/10.1007/0-387-34805-0_50
Download citation
DOI: https://doi.org/10.1007/0-387-34805-0_50
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-0-387-97317-3
Online ISBN: 978-0-387-34805-6
eBook Packages: Springer Book Archive