Controlled Gradual Disclosure Schemes for Random Bits and Their Applications

TitleControlled Gradual Disclosure Schemes for Random Bits and Their Applications
Publication TypeTechnical Report
Year of Publication1989
AuthorsCleve, R.
Other Numbers557

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 randomly according to the uniform distribution and 1/2 < p(subscript 1) < ... < p(subscript 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 S, based on all his interactions with Alice, is correct with probability exactly p(subscript i) (and a reasonable condition is satisfied in the case where S is not initially uniform). Furthermore, under an intractability assumption, our protocol can be made "oblivious" to Alice and "secure" against an Alice or Bob that might try to cheat in various ways. Previous proposed gradual disclosure schemes for single bits release information in a less controlled manner: the probabilities that represent Bob's confidence of his knowledge of S follow a random walk that eventually drifts towards 1, rather that a predetermined sequence of values.Using controlled gradual disclosure schemes, we show how to construct an improved 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.

Bibliographic Notes

ICSI Technical Report TR-89-058

Abbreviated Authors

R. Cleve

ICSI Publication Type

Technical Report