How to Convert the Flavor of a Quantum Bit Commitment
- 1.6k Downloads
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.
KeywordsQuantum Circuit Binding Condition Security Parameter Commitment Scheme Oblivious Transfer
- 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
- 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
- 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.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.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
- 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
- 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.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 http://www.cs.McGill.ca/~crepeau/students.html.
- 15.Mayers, D., “The Trouble With Quantum Bit Commitment”, available at http://xxx.lanl.gov/abs/quant-ph/9603015.
- 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