Quantum commitments from complexity assumptions |
| |
Authors: | André Chailloux Iordanis Kerenidis Bill Rosgen |
| |
Affiliation: | 1.INRIA, Paris Rocquencourt,Rocquencourt,France;2.LIAFA, CNRS,Paris,France;3.CQT, National University of Singapore,Singapore,Singapore |
| |
Abstract: | Bit commitment schemes are at the basis of modern cryptography. Since information-theoretic security is impossible both in the classical and in the quantum regime, we examine computationally secure commitment schemes. In this paper we study worst-case complexity assumptions that imply quantum bit commitment schemes. First, we show that QSZK \({\not\subseteq}\) QMA implies a computationally hiding and statistically binding auxiliary-input quantum commitment scheme. We then extend our result to show that the much weaker assumption QIP \({\not\subseteq}\) QMA (which is weaker than PSPACE \({\not\subseteq}\) PP) implies the existence of auxiliary-input commitment schemes with quantum advice. Finally, to strengthen the plausibility of the separation QSZK \({\not\subseteq}\) QMA, we find a quantum oracle relative to which honest-verifier QSZK is not contained in QCMA, the class of languages that can be verified using a classical proof in quantum polynomial time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|