Paper 2019/745

Efficient Perfectly Sound One-message Zero-Knowledge Proofs via Oracle-aided Simulation

Vincenzo Iovino

Abstract

In this paper we put forth new efficient one-message proof systems for several practical applications, like proving that an El Gamal ciphertext (over a multiplicative group) decrypts to a given value and correctness of a shuffle. Our proof systems are built from multiplicative groups of hidden order, are not based on any setup/trust assumption like the RO or the common reference string model and are perfectly sound, that is they are written proofs in the sense of mathematics. Our proof systems satisfy a generalization of zero-knowledge (ZK) that we call harmless zero-knowledge (HZK). The simulator of an $O$-HZK proof for a relation over a language $L$ is given the additional capability of invoking an oracle $O$ relative to which $L$ is hard to decide. That is, the proof does not leak any knowledge that an adversary might not compute by itself interacting with an oracle $O$ that does not help to decide the language. Unlike ZK, non-interactivity and perfect soundness do not contradict HZK and HZK can replace ZK in any application in which, basically, the computational assumptions used in the application hold even against adversaries with access to $O$. An $O$-HZK proof is witness hiding (WH) for distributions hard against adversaries with access to $O$, and strong-WI when quantifying over distributions that are indistinguishable by adversaries with access to $O$. Moreover, an $O$-HZK proof is witness indistinguishable (and the property does not depend on the oracle). We provide a specific oracle DHInvO that is enough powerful to make our main proof systems DHInvO-HZK but not trivial: indeed, we show concrete and practical cryptographic protocols that can be proven secure employing a DHInvO-HZK proof in the reduction and that are instead not achievable using traditional ZK (unless resorting to the CRS/RO models). Efficient one-message proof systems with perfect soundness were only known for relations over bilinear groups and were proven only witness indistinguishable. As byproduct, we also obtain a perfectly sound non-interactive ZAP, WH and HZK proof system for $NP$ relations from number-theoretic assumptions over multiplicative groups of hidden order. No non-interactive WH proof system for $NP$ (neither for simpler non-trivial relations) was previously known.

Note: added appendix on analysis of the witness hiding assumption in a generic group model