Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

Perfectly Concealing Quantum Bit Commitment from any Quantum One-Way Permutation

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1807))

  • 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.

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

  1. 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.

    Article  Google Scholar 

  2. 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.

    Article MATH  Google Scholar 

  3. 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.

    Google Scholar 

  4. 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.

    Google Scholar 

  5. Brassard, G.,D. Chaum andC. Crépeau, “Minimum Disclosure Proofs of Knowledge”,Journal of Computer and System Sciences, vol. 37, 1988, pp. 156–189.

    Article MATH MathSciNet  Google Scholar 

  6. Damgård, I., personal communication, December 1998.

    Google Scholar 

  7. DiVincenzo, D.P., “Two-Bit Gates Are Universal For Quantum Computation”,Physical Review A, vol. 51, no 2, February 1995, pp. 1015–1022.

    Article MathSciNet  Google Scholar 

  8. 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.

    Google Scholar 

  9. Lo, H.-K. andH. F. Chau, “Is quantum Bit Commitment Really Possible?”,Physical Review Letters, vol. 78, no 17, April 1997, pp. 3410–3413.

    Article  Google Scholar 

  10. Luby, M.,Pseudorandomness and Cryptographic Applications, Princeton University Press, 1996.

    Google Scholar 

  11. Mayers, D., “The Trouble With Quantum Bit Commitment”,http://xxx.lanl.gov/abs/quant-ph/9603015, March 1996.

  12. 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.

    Google Scholar 

  13. Mayers, D., “Unconditionally Secure Quantum Bit Commitment is Impossible”,Physical Review Letters, vol. 78, no 17, April 1997, pp. 3414–3417.

    Article  Google Scholar 

  14. Mayers, D., “Unconditional Security in Quantum Cryptography”,http://xxx.lanl.gov/abs/quant-ph/9802025, February 1998.

  15. 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.

    Article MATH MathSciNet  Google Scholar 

  16. 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.

    Chapter  Google Scholar 

  17. 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.

    Google Scholar 

  18. 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.

    Google Scholar 

  19. 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.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, Université de Montréal, Montréal

    Paul Dumais

  2. NEC Research Institute, Princeton, N-J, USA

    Dominic Mayers

  3. BRICS, Dept. of Computer Science, University of Århus, Århus, Denmark

    Louis Salvail

Authors
  1. Paul Dumais

    You can also search for this author inPubMed Google Scholar

  2. Dominic Mayers

    You can also search for this author inPubMed Google Scholar

  3. Louis Salvail

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. 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

Publish with us


[8]ページ先頭

©2009-2025 Movatter.jp