6 papers · 1 filter
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…