Abstract
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.
Chapter PDF
Similar content being viewed by others
Keywords
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
G. Brassard, C. Crépeau, and Jean-Marc Robert. All-or-nothing disclosure of secrets. In A.M. Odlyzko, ed., Proc. CRYPTO 86, pages 234–238. Springer-Verlag, 1987. Lecture Notes in Computer Science No. 263.
G. Brassard, C. Crépeau, and M. Sántha. Oblivious transfers and intersecting codes. In IEEE Transactions on Information Theory, pages 1769–1780, 1996.
M. V. D. Burmester and Y. Desmedt. All languages in NP have divertible zero-knowledge proofs and arguments under cryptographic assumptions. In Advances in Cryptology — Eurocrypt’ 90, pages 1–10, 1990.
J. D. C. Benaloh. Verifiable Secret-Ballot Elections. PhD thesis, Yale’s University, 1987.
D. Boneh and M. Franklin. Efficient generation of shared RSA keys. In B. S. Kaliski Jr, ed., Proc. CRYPTO’ 97, number 1294 in Lecture Notes in Computer Science, pages 425–439, Springer-Verlag, 1997.
I. Biehl and B. Meyer. Protocols for collusion secure asymmetric fingerprinting. In STACS’ 97, pages 399–412, 1997.
D. Boneh and J. Shaw. Collusion-secure fingerprinting for digital data. pages 452–465. Springer, 1995. Lecture Notes in Computer Science No. 963.
B. Chor, A. Fiat, and M. Naor. Tracing traitors. In Y. G. Desmedt, ed., Proc. CRYPTO’ 95, pages 257–270. Springer, 1994. Lecture Notes in Computer Science No. 839.
B. Chor and N. Gilboa. Computationally private information retrieval (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 304–313, El Paso, Texas, 4–6 May 1997.
B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In 36th Annual Symposium on Foundations of Computer Science, pages 41–50, Milwaukee, Wisconsin, 23–25 October1995. IEEE.
S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. In R. L. Rivest, A. Sherman, and D. Chaum, eds., Proc. CRYPTO 82, pages 205–210, New York, 1983. Plenum Press.
U. Feige, A. Fiat, and A. Shamir. Zero knowledge proofs of identity. Journal of Cryptology, 1(2):77–94, 1988.
S. Goldwasser and S. Micali. Probabilistic encryption. JCSS, 28(2):270–299, April 1984.
K. R. Iversen. A cryptographic scheme for computerized general elections. In J. Feigenbaum, ed., Advances in Cryptology—CRYPTO’ 91, volume 576 of Lecture Notes in Computer Science, pages 405–419. Springer-Verlag, 1992, 11–15 August 1991.
E. Kushilevitz and R. Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval (extended abstract). In 38th Annual Symposium on Foundations of Computer Science, pages 364–373, Miami Beach, Florida, 20–22 October 1997. IEEE.
V. Niemi and A. Renvall. Cryptographic protocols and voting. In Result and Trends in Theoretical Computer Science, number 812 in Lecture Notes in Computer Science, pages 307–316, 1994.
D. Naccache and J. Stern. A new candidate trapdoor function. To appear in 5th ACM Symposium on Computer and Communications Security, 1998.
H. Nurmi, A. Salomaa and L. Santean. Secret ballot elections in computer networks. In Computers and Security, volume 10, pages 553–560, 1991.
K. Ohta. Remarks on blind decryption. In Information Security Workshop, pages 59–64, 1997.
T. Okamoto and S. Uchiyama. An efficient public-key cryptosystem. In Advances in Cryptology—EUROCRYPT 98, pages 308–318, 1998.
B. Pfitzmann. Trials of traced traitors. In R. Anderson, ed., Information Hiding, volume 1174 of Lecture Notes in Computer Science, pages 49–64, Springer-Verlag, 1996.
B. Pfitzmann and M. Schunter. Asymmetric fingerprinting (extended abstract). In Ueli Maurer, ed., Advances in Cryptology—EUROCRYPT 96, volume 1070 of Lecture Notes in Computer Science, pages 84–95. Springer-Verlag, 12–16 May 1996.
B. Pfitzmann and M. Waidner. Asymmetric fingerprinting for larger collusions. In 4th ACM Conference on Computer and Communications Security, 1997.
A. Salomaa and L. Santean. Secret selling of secrets with several buyers. In 42th EATCS Bulletin, pages 178–186, 1990.
K. Sakurai and Y. Yamane. Blind decoding, blind undeniable signatures, and their applications to privacy protection. In R. Anderson, ed., Information Hiding, pages 257–264. Springer-Verlag, 1997. Lecture Notes in Computer Science No. 1174.
J. van de Graaf and R. Peralta. A simple and secure way to show the validity of your public key. In C. Pomerance, ed., Proc. CRYPTO’ 87, pages 128–134. Springer-Verlag, 1988. Lecture Notes in Computer Science No. 293.
S. Wiesner. Conjugate coding. In Sigact News, volume 18, pages 78–88, 1983. Original manuscript written circa 1970.
A. C. Yao. How to generate and exchange secrets. In Proc. 27th IEEE Symp. on Foundations of Comp. Science, pages 162–167, Toronto, 1986. IEEE.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stern, J.P. (1998). A New and Efficient All-Or-Nothing Disclosure of Secrets Protocol. In: Ohta, K., Pei, D. (eds) Advances in Cryptology — ASIACRYPT’98. ASIACRYPT 1998. Lecture Notes in Computer Science, vol 1514. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49649-1_28
Download citation
DOI: https://doi.org/10.1007/3-540-49649-1_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65109-3
Online ISBN: 978-3-540-49649-6
eBook Packages: Springer Book Archive