Crypto Seminar - Quang Dao

— 5:30pm

Location:
In Person and Virtual - ETQUANG DAO - Blelloch Skees Conference Room, Gates Hillman 8115

Speaker:
QUANG DAO, Ph.D. Student, Computer Science Department, Carnegie Mellon University,
https://quangvdao.github.io/

Non-Interactive Zero-Knowledge from LPN and MQ

We give the first construction of non-interactive zero-knowledge (NIZK) arguments from post-quantum assumptions other than Learning with Errors. In particular, we achieve NIZK under the polynomial hardness of the Learning Parity with Noise (LPN) assumption, and the exponential hardness of solving random under-determined multivariate quadratic equations (MQ). We also construct NIZK satisfying statistical zero-knowledge assuming a new variant of LPN, Dense-Sparse LPN, introduced by Dao and Jain (CRYPTO 2024), together with exponentially-hard MQ. 

The main technical ingredient of our construction is an extremely natural (but only in hindsight!) construction of correlation-intractable (CI) hash functions from MQ, for a NIZK-friendly subclass of constant-degree polynomials that we call concatenated constant-degree polynomials. Under exponential security, this hash function also satisfies the stronger notion of approximate CI for concatenated constant-degree polynomials. The NIZK construction then follows from a prior blueprint of Brakerski-Koppula-Mour (CRYPTO 2020). In addition, we show how to construct (approximate) CI hashing for degree-d functions from the (exponential) hardness of solving random degree-d equations, a natural generalization of MQ. To realize NIZK with statistical zero-knowledge, we design a lossy public-key encryption scheme with approximate linear decryption and inverse-polynomial decryption error from Dense-Sparse LPN. These constructions may be of independent interest.

This is joint work with Aayush Jain & Zhengzhong Jin.

Reference Paper

In Person and Zoom Participation.  See announcement.

Event Website:
https://sites.google.com/view/crypto-seminar/home

Add event to Google
Add event to iCal