5 papers
Towards Worst-case Hardness for Low-Noise LPN
Divesh Aggarwal, Rishav Gupta, Hai Hoang Nguyen +2
The hardness of the Learning Parity with Noise (LPN) problem is a foundational assumption in cryptography, forming the basis of constructions ranging from symmetric-key primitives…
Weak Zero-Knowledge and One-Way Functions
Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan
We study the implications of the existence of weak Zero-Knowledge (ZK) protocols for worst-case hard languages. These are protocols that have completeness, soundness, and zero-know…
Improved Search-to-Decision Reduction for Random Local Functions
Kel Zin Tan, Prashant Nalini Vasudevan
A random local function defined by a -ary predicate is one where each output bit is computed by applying to randomly chosen bits of its input. These represent natura…
Decoding Balanced Linear Codes With Preprocessing
Andrej Bogdanov, Rohit Chatterjee, Yunqi Li +1
Prange's information set algorithm is a decoding algorithm for arbitrary linear codes. It decodes corrupted codewords of any -linear code of message length up…
Public-Key Encryption from the MinRank Problem
Rohit Chatterjee, Changrui Mu, Prashant Nalini Vasudevan
We construct a public-key encryption scheme from the hardness of the (planted) MinRank problem over uniformly random instances. This corresponds to the hardness of decoding random…