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 ... 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 ... 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 ... 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 ... 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 >>>