A New and Efficient All-Or-Nothing Disclosure of Secrets Protocol

Two-party protocols have been considered for a long time. Currently, there is a renewed effort to revisit specific protocols to gain efficiency. As an example, one may quote the breakthrough of [BF97], bringing a new solution to the problem of secretly generating RSA keys, which itself goes back to the pioneering work by Yao [Yao86]. The All-Or-Nothing Disclosure of Secrets protocol (ANDOS) was introduced in 1986 by Brassard, Crépeau and Robert [BCR87]. It involves two parties, a vendor and a buyer, and allows the vendor, who holds several secrets, to disclose one of them to the buyer, with the guarantee that no information about the other secrets will be gained. Furthermore, the buyer can freely choose his secret and has the guarantee that the vendor will not be able to find out which secret he picked. In this paper, we present a new protocol which achieves the same functionality, but which is much more efficient and can easily be implemented. Our protocol is especially efficient when a large number of secrets is involved and it can be used in various applications. The proof of security involves a novel use of computational zero-knowledge techniques combined with semantic security.