Quantum commitments from complexity assumptions

André Chailloux, Iordanis Kerenidis, Bill Rosgen

Louis Salvail

Louis Salvail

André Chailloux, Iordanis Kerenidis, Bill Rosgen

Bit commitment schemes are at the basis of modern cryptography. Since information-theoretic security is impossible both in the classical and the quantum regime, we need to look at 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 included in QMA implies a computationally hiding and statistically binding auxiliary-input quantum commitment scheme. Additionally, we give auxiliary-input commitment schemes using quantum advice that depend on the much weaker assumption that QIP is not included in QMA (which is weaker than PSPACE not included in PP). Finally, 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.

Dominique Unruh

Eiichiro Fujisaki

At Eurocrypt 2011, Lindell presented practical static and adaptively UC-secure commitment schemes based on the DDH assumption. Later, Blazy et al. (at ACNS 2013) improved the efficiency of the Lindell's commitment schemes. In this paper, we present static and adaptively UC-secure commitment schemes based on the same assumption and further improve the communication and computational complexity, as well as the size of the common reference string.