ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > AUTHORS > ALON ROSEN:
All reports by Author Alon Rosen:

TR06-147 | 27th November 2006
Chris Peikert, Alon Rosen

Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors

Revisions: 1

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


TR05-158 | 12th December 2005
Chris Peikert, Alon Rosen

Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices

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


TR03-060 | 7th September 2003
Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen

Completeness in Two-Party Secure Computation - A Computational View

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


TR01-064 | 10th September 2001
Moni Naor, Omer Reingold, Alon Rosen

Pseudo-Random Functions and Factoring

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


TR01-050 | 24th June 2001
Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen

Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

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




ISSN 1433-8092 | Imprint