Processing math: 100%

International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 29 November 2024

Yanyi Liu, Noam Mazor, Rafael Pass
ePrint Report ePrint Report
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 xL, and if xL, 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(logn)) 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).

Additional news items may be found on the IACR news page.