We demonstrate an \emph{average-case} problem which is as hard as finding $\gamma(n)$-approximate shortest vectors in certain $n$-dimensional lattices in the \emph{worst case}, where $\gamma(n) = O(\sqrt{\log n})$. The previously best known factor for any class of lattices was $\gamma(n) = \tilde{O}(n)$. To obtain our results, we focus on families of ... more >>>

The generalized knapsack function is defined as $f_{\a}(\x) = \sum_i a_i \cdot x_i$, where $\a = (a_1, \ldots, a_m)$ consists of $m$ elements from some ring $R$, and $\x = (x_1, \ldots, x_m)$ consists of $m$ coefficients from a specified subset $S \subseteq R$. Micciancio (FOCS 2002) proposed a specific ... more >>>

A Secure Function Evaluation (SFE) of a two-variable function f(.,.) is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither party learns ``more than is necessary". A rich body of work deals with the study of completeness for secure two-party ... more >>>

Factoring integers is the most established problem on which cryptographic primitives are based. This work presents an efficient construction of {\em pseudorandom functions} whose security is based on the intractability of factoring. In particular, we are able to construct efficient length-preserving pseudorandom functions where each evaluation requires only a {\em ... more >>>

We show that any concurrent zero-knowledge protocol for a non-trivial language (i.e., for a language outside $\BPP$), whose security is proven via black-box simulation, must use at least $\tilde\Omega(\log n)$ rounds of interaction. This result achieves a substantial improvement over previous lower bounds, and is the first bound to rule ... more >>>