International Association
for Cryptologic Research

An {\em 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: {\em 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 {\em reusable} online-efficient commitment under a standard assumption, RingLWE. A main component in our analysis is a leakage lemma by Chung, Kalai, Liu, and Raz (CRYPTO `11) introduced in the context of {\em streaming delegation schemes.}

In 2002, Barak and Goldreich introduced the notion of a {\em universal argument} and constructed an interactive universal argument for non-deterministic computations based on polynomially hard collision-resistant hash functions. Since then, and especially in recent years, there have been tremendous developments in the construction of {\em non-interactive} succinct arguments for deterministic computations under standard hardness assumptions. However, the constructed succinct arguments can be proven universal only under {\em sub-exponential} assumptions. Assuming {\em polynomially hard} fully homomorphic encryption and a widely believed worst-case complexity assumption, we prove a general lifting theorem showing that all existing non-interactive succinct arguments can be made universal. The required complexity assumption is that non-uniformity does not allow arbitrary polynomial speedup. In the setting of uniform adversaries, this extra assumption is not needed.