Classical Binding for Quantum Commitments

Nir Bitansky and Zvika Brakerski

Abstract

In classical commitments, statistical binding means that for almost any commitment transcript there is at most one possible opening. While quantum commitments (for classical messages) sometimes have benefits over their classical counterparts (e.g.\ in terms of assumptions), they provide a weaker notion of binding. Essentially that the sender cannot open a given commitment to a random value with probability noticeably greater than $1/2$. We introduce a notion of classical binding for quantum commitments which provides guarantees analogous to the classical case. In our notion, the receiver performs a (partial) measurement of the quantum commitment string, and the outcome of this measurement determines a single value that the sender may open. We expect that our notion can replace classical commitments in various settings, leaving the security proof essentially unchanged. As an example we show a soundness proof for the GMW zero-knowledge proof system. We construct a non-interactive quantum commitment scheme which is classically statistically-binding and has a classical opening, based on the existence of any post-quantum one-way function. Prior candidates had inherently quantum openings and were not classically binding. In contrast, we show that it is impossible to achieve classical binding for statistically hiding commitments, regardless of assumption or round complexity. Our scheme is simply Naor's commitment scheme (which classically requires a common random string, CRS), but executed in superposition over all possible values of the CRS, and repeated several times. We hope that this technique for using quantum communication to remove a CRS may find other uses.

Available format(s)
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2021
Keywords
QuantumCommitmentsZero-Knowledge
Contact author(s)
nbitansky @ gmail com
zvika brakerski @ weizmann ac il
History
2021-09-17: last of 2 revisions
See all versions
Short URL
https://ia.cr/2021/1001

CC BY

BibTeX

@misc{cryptoeprint:2021/1001,
author = {Nir Bitansky and Zvika Brakerski},
title = {Classical Binding for Quantum Commitments},
howpublished = {Cryptology ePrint Archive, Paper 2021/1001},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1001}},
url = {https://eprint.iacr.org/2021/1001}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.