Private Event
From Laconic Zero Knowledge to Public Key Cryptography
Speaker
Akshay Degwekar, MIT
MIT, CSAIL
Host
Vinod Vaikuntanathan
MIT CSAIL
Abstract: Since its inception, public-key encryption (PKE) has been a fundamental cryptographic primitive. Despite its significance, constructions of PKE are only known from a handful of specific intractability assumptions.
In this work, we construct a PKE scheme from a natural complexity-theoretic assumption. Specifically, we construct PKE assuming the hardness of a language in NP that with an honest-verifier statistical zero knowledge (SZK) argument-system in which the honest prover is efficient and laconic. That is, messages that the prover sends are efficiently computable (given the NP witness) and the prover's total communication is short (i.e., of sufficiently sub-logarithmic length). This gives us a common framework capturing assumptions known to imply PKE.
Joint work with Itay Berman, Ron Rothblum and Prashant Nalini Vasudevan.
In this work, we construct a PKE scheme from a natural complexity-theoretic assumption. Specifically, we construct PKE assuming the hardness of a language in NP that with an honest-verifier statistical zero knowledge (SZK) argument-system in which the honest prover is efficient and laconic. That is, messages that the prover sends are efficiently computable (given the NP witness) and the prover's total communication is short (i.e., of sufficiently sub-logarithmic length). This gives us a common framework capturing assumptions known to imply PKE.
Joint work with Itay Berman, Ron Rothblum and Prashant Nalini Vasudevan.