1 citations · 1 across the 5 of their papers we have counts for
11 papers
Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli
Andrej Bogdanov, Kel Zin Tan, Prashant Nalini Vasudevan
The Noisy Linear Equations problem involves finding the solution to a random linear system over a finite field given noisy evaluations. This is a generalisation of various learning…
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…
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…
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…
-SUM in the Sparse Regime
Shweta Agrawal, Sagnik Saha, Nikolaj I. Schwartzbach +2
In the average-case -SUM problem, given integers chosen uniformly at random from , the objective is to find a ``solution'' set of numbers that sum to $0…
Control, Confidentiality, and the Right to be Forgotten
Aloni Cohen, Adam Smith, Marika Swanberg +1
Recent digital rights frameworks give users the right to delete their data from systems that store and process their personal information (e.g., the "right to be forgotten" in the…
Deletion Inference, Reconstruction, and Compliance in Machine (Un)Learning
Ji Gao, Sanjam Garg, Mohammad Mahmoody +1
Privacy attacks on machine learning models aim to identify the data that is used to train such models. Such attacks, traditionally, are studied on static models that are trained on…
Formalizing Data Deletion in the Context of the Right to be Forgotten
Sanjam Garg, Shafi Goldwasser, Prashant Nalini Vasudevan
The right of an individual to request the deletion of their personal data by an entity that might be storing it -- referred to as the right to be forgotten -- has been explicitly r…
On the Power of Statistical Zero Knowledge
Adam Bouland, Lijie Chen, Dhiraj Holden +2
We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZ…