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 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 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, assuming some computational problem to be hard for adversaries with access to $O$, and strong-WI when quantifying over distributions that are indistinguishable by adversaries with access to $O$. We provide a specific oracle $Q$ that is enough powerful to make our main proof systems $Q$-HZK but not trivial: indeed, we show concrete and practical cryptographic protocols that can be proven secure employing a $Q$-HZK proof in the reduction and that are instead not achievable using traditional ZK (unless assuming a CRS/RO). 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 and HZK proof for NP from a number-theoretic assumption over multiplicative groups of hidden order.

Note: typos, corrections and more on HPoK