Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-194 | 28th November 2024 17:07

On Witness Encryption and Laconic Zero-Knowledge Arguments

RSS-Feed




TR24-194
Authors: Yanyi Liu, Noam Mazor, Rafael Pass
Publication: 28th November 2024 17:17
Downloads: 122
Keywords: 


Abstract:

Witness encryption (WE) (Garg et al, STOC’13) is a powerful cryptographic primitive that is closely related to the notion of indistinguishability obfuscation (Barak et, JACM’12, Garg et al, FOCS’13). For a given NP-language $L$, WE for $L$ enables encrypting a message $m$ using an instance $x$ as the public-key, while ensuring that efficient decryption is possible by anyone possessing a witness for $x \in L$, and if $x\notin L$, then the encryption is hiding. We show that this seemingly sophisticated primitive is equivalent to a communication-efficient version of one of the most classic cryptographic primitives—namely that of a zero-knowledge argument (Goldwasser et al, SIAM’89, Brassard et al, JCSS’88): for any NP-language $L$, the following are equivalent:
- There exists a witness encryption for L;
- There exists a laconic (i.e., the prover communication is bounded by $O(\log n)$) special-honest verifier zero-knowledge (SHVZK) argument for $L$.

Our approach is inspired by an elegant (one-sided) connection between (laconic) zero-knowledge arguments and public-key encryption established by Berman et al (CRYPTO’17) and Cramer-Shoup (EuroCrypt’02).



ISSN 1433-8092 | Imprint