Post-Quantum Commitment Scheme with Extending Message Length

Hideaki Miyaji, Yuntao Wang, Atsuko Miyaji

Hideaki Miyaji, Yuntao Wang, Atsuko Miyaji

Commitment schemes are cryptographic schemes that can be applied to zero-knowledge proof construction and blockchain construction. Recently, lattice-based cryptography has been intensively investigated due to the promising potential in quantum cryptography. Accordingly, commitment schemes based on lattice assumptions have been studied for practical applications. Notably, applications often require committing an arbitrary message with low communication costs, so commitment schemes must be satisfied with fewer length restrictions and fewer extensions to the messages. Several studies have been conducted to achieve the problem, including the study published by Baum et al. in 2018. However, the scheme in question still utilizes the message domain for extraneous purposes. We design a length-extension-free commitment scheme ComMWMin which the length of the message string is large relative to the length of the commitment string, improving on the commitment scheme of Baum et al. Furthermore, we prove that the hiding and binding properties of ComMWMare based on the hardness of the decisional search knapsack problem and extended search knapsack problems, respectively. Finally, we evaluate the computation costs of generating commitment value between ours and Baum et al.’s commitment scheme.

Chanyoung Ko, Youngkyung Lee, Kwangsu Lee +1 more

Marcel Dall’Agnol, Nicholas Spooner

Collapse binding and collapsing were proposed by Unruh (Eurocrypt '16) as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the "lifting" of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: are they the weakest notions that suffice for such lifting? In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information. As a consequence, we establish that a variety of "weak" binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a "win-win" result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives). This strengthens a result due to Zhandry (Eurocrypt '19) showing that the same object yields quantum lightning.

Ariel Danan, Lev Vaidman A

Mingqiang Wang, Xue Wang, Tao Zhan

A new unconditionally secure multi-party quantum commitment is proposed in this paper by encoding the committed message to the phase of a quantum state. Multi-party means that there are more than one recipient in our scheme. We show that our quantum commitment scheme is unconditional hiding and binding, and hiding is perfect. Our technique is based on the interference of phase-encoded coherent states of light. Its security proof relies on the no-cloning theorem of quantum theory and the properties of quantum information.