All reports by Author Chris Peikert:

__
TR11-165
| 8th December 2011
__

Elena Grigorescu, Chris Peikert#### List Decoding Barnes-Wall Lattices

Revisions: 2

__
TR08-100
| 14th November 2008
__

Chris Peikert#### Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem

__
TR07-133
| 20th November 2007
__

Craig Gentry, Chris Peikert, Vinod Vaikuntanathan#### Trapdoors for Hard Lattices and New Cryptographic Constructions

__
TR07-080
| 7th August 2007
__

Chris Peikert, Brent Waters#### Lossy Trapdoor Functions and Their Applications

__
TR06-148
| 4th December 2006
__

Chris Peikert#### Limits on the Hardness of Lattice Problems in $\ell_p$ Norms

Revisions: 1

__
TR06-147
| 27th November 2006
__

Chris Peikert, Alon Rosen#### Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors

Revisions: 1

__
TR05-158
| 12th December 2005
__

Chris Peikert, Alon Rosen#### Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices

Elena Grigorescu, Chris Peikert

The question of list decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete structure of linear codes and point lattices in $R^{N}$, and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the ... more >>>

Chris Peikert

We construct public-key cryptosystems that are secure assuming the

\emph{worst-case} hardness of approximating the length of a shortest

nonzero vector in an $n$-dimensional lattice to within a small

$\poly(n)$ factor. Prior cryptosystems with worst-case connections

were based either on the shortest vector problem for a \emph{special

class} of lattices ...
more >>>

Craig Gentry, Chris Peikert, Vinod Vaikuntanathan

We show how to construct a variety of ``trapdoor'' cryptographic tools

assuming the worst-case hardness of standard lattice problems (such as

approximating the shortest nonzero vector to within small factors).

The applications include trapdoor functions with \emph{preimage

sampling}, simple and efficient ``hash-and-sign'' digital signature

schemes, universally composable oblivious transfer, ...
more >>>

Chris Peikert, Brent Waters

We propose a new general primitive called lossy trapdoor

functions (lossy TDFs), and realize it under a variety of different

number theoretic assumptions, including hardness of the decisional

Diffie-Hellman (DDH) problem and the worst-case hardness of

standard lattice problems.

Using lossy TDFs, we develop a new approach for constructing ... more >>>

Chris Peikert

We show that for any $p \geq 2$, lattice problems in the $\ell_p$

norm are subject to all the same limits on hardness as are known

for the $\ell_2$ norm. In particular, for lattices of dimension

$n$:

* Approximating the shortest and closest vector in ... more >>>

Chris Peikert, Alon Rosen

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

Chris Peikert, Alon Rosen

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