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

Over the past few decades, we have seen a proliferation of advanced cryptographic primitives with lossy or homomorphic properties built from various assumptions such as Quadratic Residuosity, Decisional Diffie-Hellman, and Learning with Errors. These primitives imply hard problems in the complexity class SZK (statistical zero-knowledge); as a consequence, they can only be based on assumptions that are broken in BPPSZK. This poses a barrier for building advanced primitives from code-based assumptions, as the only known such assumption is Learning Parity with Noise (LPN) with an extremely low noise rate log2(n)/n, which is broken in quasi=polynomial time. 

In this work, we propose a new code-based assumption: Dense-Sparse LPN, that falls in the complexity class BPPSZK and is conjectured to be secure against subexponential time adversaries. Our assumption is a variant of LPN that is inspired by McEliece’s cryptosystem and random k-XOR in average-case complexity. Roughly, the assumption states that (T⋅M, s⋅T⋅M + e) is indistinguishable from (T⋅M, u), for a random (dense) matrix T, random sparse matrix M, and sparse noise vector e drawn from the Bernoulli distribution with inverse polynomial noise probability. We leverage our assumption to build lossy trapdoor functions (Peikert-Waters STOC 08). This gives the first post-quantum alternative to the lattice-based construction in the original paper. Lossy trapdoor functions, being a fundamental cryptographic tool, are known to enable a broad spectrum of both lossy and non-lossy cryptographic primitives; our construction thus implies these primitives in a generic manner. In particular, we achieve collision-resistant hash functions with plausible subexponential security, improving over a prior construction from LPN with noise rate log2(n)/n that is only quasi-polynomially secure. 

This is joint work with Aayush Jain. 

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