Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1807))
Included in the following conference series:
3588Accesses
Abstract
We show that although unconditionally secure quantum bit commitment is impossible, it can be based upon any family of quantum one-way permutations. The resulting scheme is unconditionally concealing and computationally binding. Unlike the classical reduction of Naor, Ostrovski, Ventkatesen and Young, our protocol is non-interactive and has communication complexityO(n) qubits forn a security parameter.
Supported by a NSERC grant, part of this work was done while visiting BRICS and McGill SOCS.
Part of this work was done while visiting BRICS and NEC Tsukuba Laboratory, Japan.
Supported by the Thomas B. Thriges Center for KvanteInformatik (CKI).
Basic Research in Computer Science of the Danish National Research Foundation.
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
Barenco, A.,C.H. Bennett, R. Cleve, D.P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin andH. Weinfurter, “Elementary Gates for Quantum Computation”,Physical Review A, vol. 52, no 5, November 1995, pp. 3457–3467.
Bennett, C.H.,F. Bessette, G. Brassard, L. Salvail andJ. Smolin, “Experimental Quantum Cryptography”,Journal of Cryptology, vol. 5, no. 1, 1992, pp. 3–28.
Bennett, C. H. andG. Brassard, “Quantum Cryptography: Public Key Distribution and Coin Tossing”,Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, India, December 1984, pp. 175–179.
Bennett, C. H.,G. Brassard, C. Crépeau andM.-H. Skubiszewska, “Practical Quantum Oblivious Transfer”,Advances in Cryptology: CRYPTO’ 91: Proceedings, Lecture Notes in Computer Science, no 576, Springer-Verlag, August 1992, pp. 362–371.
Brassard, G.,D. Chaum andC. Crépeau, “Minimum Disclosure Proofs of Knowledge”,Journal of Computer and System Sciences, vol. 37, 1988, pp. 156–189.
Damgård, I., personal communication, December 1998.
DiVincenzo, D.P., “Two-Bit Gates Are Universal For Quantum Computation”,Physical Review A, vol. 51, no 2, February 1995, pp. 1015–1022.
Impagliazzo, R. andS. Rudich, “Limits on Provable Consequences of One-Way Permutations”,Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, May 1989, pp. 44–61.
Lo, H.-K. andH. F. Chau, “Is quantum Bit Commitment Really Possible?”,Physical Review Letters, vol. 78, no 17, April 1997, pp. 3410–3413.
Luby, M.,Pseudorandomness and Cryptographic Applications, Princeton University Press, 1996.
Mayers, D., “The Trouble With Quantum Bit Commitment”,http://xxx.lanl.gov/abs/quant-ph/9603015, March 1996.
Mayers, D., “Quantum Key Distribution and String Oblivious Transfer in Noisy Channels”,Advances in Cryptology: CRYPTO’ 96: Proceedings, Lecture Notes in Computer Science, no 1109, Springer-Verlag, August 1996, pp. 343–357.
Mayers, D., “Unconditionally Secure Quantum Bit Commitment is Impossible”,Physical Review Letters, vol. 78, no 17, April 1997, pp. 3414–3417.
Mayers, D., “Unconditional Security in Quantum Cryptography”,http://xxx.lanl.gov/abs/quant-ph/9802025, February 1998.
Naor, M.,R. Ostrovsky, R. Ventkatesan andM. Young, “Perfect Zero-Knowledge Arguments For NP Using Any One-Way Permutation”,Journal of Cryptology, vol. 11, no 2, 1998, pp. 87–108.
Salvail, L., “Quantum Bit Commitment From a Physical Assumption”,Advances in Cryptology: CRYPTO’ 98: Proceedings, Lecture Notes in Computer Science, no 1462, Springer-Verlag, August 1998, pp. 338–353.
Shor, P., “Algorithms for Quantum Computation: Discrete Logarithms and Factoring”,Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 124–134.
van de Graaf, J.,Torwards a Formal Definition of Security for Quantum Protocols, Ph.D. thesis, Département d’informatique et de recherche opérationelle, Université de Montréal, 1997.
Yao, A. C.-C., “Security of Quantum Protocols Against Coherent Measurements”,Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, May 1995, pp. 67–75.
Author information
Authors and Affiliations
Dept. of Computer Science, Université de Montréal, Montréal
Paul Dumais
NEC Research Institute, Princeton, N-J, USA
Dominic Mayers
BRICS, Dept. of Computer Science, University of Århus, Århus, Denmark
Louis Salvail
- Paul Dumais
You can also search for this author inPubMed Google Scholar
- Dominic Mayers
You can also search for this author inPubMed Google Scholar
- Louis Salvail
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Department of Electrical Engineering - ESAT / COSIC, Katholieke Universiteit Leuven, Kardinaal Mercierlaan 94, B-3001, Heverlee, Belgium
Bart Preneel
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dumais, P., Mayers, D., Salvail, L. (2000). Perfectly Concealing Quantum Bit Commitment from any Quantum One-Way Permutation. In: Preneel, B. (eds) Advances in Cryptology — EUROCRYPT 2000. EUROCRYPT 2000. Lecture Notes in Computer Science, vol 1807. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45539-6_21
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-67517-4
Online ISBN:978-3-540-45539-4
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative