Paper 2015/628

An Unconditionally Hiding and Long-Term Binding Post-Quantum Commitment Scheme

Daniel Cabarcas and Denise Demirel and Florian Göpfert and Jean Lancrenon and Thomas Wunderer

Abstract

Commitment schemes are among cryptography's most important building blocks. Besides their basic properties, hidingness and bindingness, for many applications it is important that the schemes applied support proofs of knowledge. However, all existing solutions which have been proven to provide these protocols are only computationally hiding or are not resistant against quantum adversaries. This is not suitable for long-lived systems, such as long-term archives, where commitments have to provide security also in the long run. Thus, in this work we present a new post-quantum unconditionally hiding commitment scheme that supports (statistical) zero-knowledge protocols and allows to refreshes the binding property over time. The bindingness of our construction relies on the approximate shortest vector problem, a lattice problem which is conjectured to be hard for polynomial approximation factors, even for a quantum adversary. Furthermore, we provide a protocol that allows the committer to prolong the bindingness property of a given commitment, while showing in zero-knowledge fashion that the value committed to did not change. In addition, our construction yields two more interesting features: 1) the ability to "convert" a Pedersen commitment into a lattice-based one, and 2) the construction of a hybrid approach whose bindingness relies on the discrete logarithm and approximate shortest vector problems.