8 papers
Witness Encryption via Prime-Order Generic Groups
Isaac M Hair, Amit Sahai
For every constant , we unconditionally construct witness encryption for NP in the classical generic cyclic group model with the following properties. For SAT instances of s…
Polynomial-Factor Deterministic NP-Hardness for SVP in Every lp Norm with p > 2
Isaac M Hair, Amit Sahai
For every constant and every constant \[ 0<\varepsilon< \min\left\{\frac{p-2}{4p},\frac18\right\}, \] we show that the -shortest vector problem for lattices of…
Refuting a Conjecture of Umans and Wang on Arithmetic-Progression Divisor Covers
Xinjie He, Amit Sahai
An \emph{-divisor set} is a finite set of positive integers containing a multiple of every integer from through . Umans and Wang proposed, as the arithmetic-progression v…
List Recovery for Random Low-Rate Linear Codes
Isaac M Hair, Amit Sahai
We prove a list recovery guarantee for random low-rate linear codes over sufficiently large prime fields. For fixed dimension , error fraction , and accuracy parameter $\vare…
Public Key Encryption from High-Corruption Constraint Satisfaction Problems
Isaac M Hair, Amit Sahai
We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both of whi…
Deterministic Hardness of Approximation For SVP in all Finite Norms
Isaac M Hair, Amit Sahai
We show that, assuming NP DTIME, the shortest vector problem for lattices of rank in any finite norm is hard to ap…
Quantum Advantage via Solving Multivariate Polynomials
Pierre Briaud, Itai Dinur, Riddhi Ghosal +3
In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case search problem of finding a solution t…
Quantum Advantage via Solving Multivariate Quadratics
Pierre Briaud, Riddhi Ghosal, Aayush Jain +2
In this work, we propose a new way to (non-interactively, verifiably) demonstrate Quantum Advantage by solving the average-case search problem of finding a solution t…