How to Convert the Flavor of a Quantum Bit Commitment

  • Claude Crépeau
  • Frédéric Légaré
  • Louis Salvail
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


In this paper we show how to convert a statistically binding but computationally concealing quantum bit commitment scheme into a computationally binding but statistically concealing qbc scheme. For a security parameter n, the construction of the statistically concealing scheme requires O(n 2) executions of the statistically binding scheme. As a consequence, statistically concealing but computationally binding quantum bit commitments can be based upon any family of quantum one-way functions. Such a construction is not known to exist in the classical world.


Quantum Circuit Binding Condition Security Parameter Commitment Scheme Oblivious Transfer 
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.


  1. 1.
    C. H. Bennett and G. Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, pages 175–179. IEEE, 1984.Google Scholar
  2. 2.
    Barenco, A., C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin and H. Weinfurter, “Elementary Gates for Quantum Computation”, Physical Review A, vol. 52, no 5, November 1995, pp. 3457–3467.CrossRefGoogle Scholar
  3. 3.
    Bennett, C. H., G. Brassard, C. Crépeau and M.-H. Skubiszewska, “Practical Quantum Oblivious Transfer”, Advances in Cryptology: CRYPTO '91: Proceedings, Lecture Notes in Computer Science, vol. 576, Springer-Verlag, August 1992, pp. 362–371.Google Scholar
  4. 4.
    Brassard, G., D. Chaum and C. Crépeau, “Minimum Disclosure Proofs of Knowledge”, Journal of Computing and System Science, vol. 37, 1988, pp. 156–189.zbMATHCrossRefGoogle Scholar
  5. 5.
    Crépeau, C., “Quantum Oblivious Transfer”, Journal of Modern Optics, vol. 41, no 12, December 1994, pp. 2445–2454. A preliminary version of this work appeared in Crépeau, C. and J. Kilian, “Achieving oblivious transfer using weakened security assumptions”, Proceedings of 29th IEEE Symposium on the Foundations of Computer Science, October 1988, pp. 42–52.zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Dumais, P., D. Mayers, and L. Salvail, “Perfectly Concealing Quantum Bit Commitment From Any Quantum One-Way Permutation”, Advances in Cryptology: EUROCRYPT '00: Proceedings, Lecture Notes in Computer Science, vol. 1807, Springer-Verlag, 2000, pp. 300–315.Google Scholar
  7. 7.
    Goldreich, O., and L. Levin, “A Hard-Core Predicate for Any One-Way Function”, Proceedings of the 21st ACM Symposium on Theory of Computing, 1989, pp. 25–32.Google Scholar
  8. 8.
    Goldwasser, S., S. Micali and C. Rackoff, “The Knowledge Complexity of Interactive Proof Systems”, SIAM Journal on Computing, vol. 18, 1989, pp. 186–208.zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    Goldreich, O., S. Micali, and A. Wigderson, “Proofs that Yield Nothing but their Validity or All Language in NP Have Zero-Knowledge Proof Systems”, Journal of the ACM, vol. 38, no 1, 1991, pp. 691–729.zbMATHMathSciNetGoogle Scholar
  10. 10.
    Goldreich, O., S. Micali, and A. Wigderson, “How to play any mental game or a completeness theorem for protocols with honest majority”, Proceedings of the 19th ACM Symposium on Theory of Computing, 1987, pp. 218–229.Google Scholar
  11. 11.
    Håstad, J., R. Impagliazzo, L. Levin and M. Luby “A pseudo-random generator from any one-way function”, SIAM Journal on Computing, vol. 28, no 4, 1999, pp. 1364–1396.zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Impagliazzo, R. and S. Rudich, “Limits on Provable Consequences of One-Way Permutations”, Advances in Cryptology: CRYPTO '88: Proceedings, Lecture Notes in Computer Science, vol. 403, Springer-Verlag, 1989, pp. 2–7.Google Scholar
  13. 13.
    Légaré, F., “Converting the flavor of a quantum bit commitment”, M.Sc. thesis, School of Computer Science, McGill University, 2001. Supervised by C. Crépeau. Thesis available at
  14. 14.
    Lo, H.-K. and H. F. Chau, “Is quantum Bit Commitment Really Possible?”, Physical Review Letters, vol. 78, no 17, April 1997, pp. 3410–3413.CrossRefGoogle Scholar
  15. 15.
    Mayers, D., “The Trouble With Quantum Bit Commitment”, available at
  16. 16.
    Mayers, D., “Unconditionally Secure Quantum Bit Commitment is Impossible”, Physical Review Letters, vol. 78, no 17, April 1997, pp. 3414–3417.CrossRefGoogle Scholar
  17. 17.
    Naor, M., “Bit Commitment Using Pseudo-Randomness”, Journal of Cryptology, vol. 4, 1991, pp. 151–158.zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    Naor, M., R. Ostrovsky, R. Ventkatesan, and M. Young, “Perfect Zero-Knowledge Arguments For NP Using Any One-Way Permutation”, Journal of Cryptology, vol. 11, no 2, 1998, pp. 87–108.zbMATHCrossRefGoogle Scholar
  19. 19.
    Yao, A. C., “Security of Quantum Protocols Against Coherent Measurements”, Proceedings of the 27th ACM Symposium on Theory of Computing, 1995, pp. 67–75.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Claude Crépeau
    • 1
  • Frédéric Légaré
    • 2
  • Louis Salvail
    • 3
  1. 1.School of Computer ScienceMcGill UniversityCanada
  2. 2.KLabsZero-Knowledge Systems Inc.Canada
  3. 3.BRICS, Dept. of Computer ScienceUniversity of ÅrhusÅrhus

Personalised recommendations