Reusable Online-Efficient Commitments

An online-efficient commitment is a succinct locally-openable commitment, where the bulk of the sender work is done offline, generating an encoding \(\tilde{x}\) of the committed data x. In the online phase, both the sender, given random access to \(\tilde{x}\) , and receiver run in polylogarithmic time in the length of x. Online-efficient commitments were recently constructed under the standard assumption of RingLWE by Lin, Mook, and Wichs, but with a significant caveat: they are not reusable. Their commitments are privately verifiable and cease to be binding if a malicious sender can learn whether the receiver accepts or rejects in repeated decommitment requests. We construct the first reusable online-efficient commitment under a standard assumption, Ring LWE. A main component in our analysis is a leakage lemma by Chung, Kalai, Liu, and Raz (CRYPTO ‘11) introduced in the context of streaming delegation schemes.