Welcome to the resource topic for 2019/745
Title:
Efficient Perfectly Sound One-message Zero-Knowledge Proofs via Oracle-aided Simulation
Authors: 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.
ePrint: https://eprint.iacr.org/2019/745
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .