Chris Peikert

STOC Conference 2017 Conference Paper

Pseudorandomness of ring-LWE for any ring and modulus

• Chris Peikert
• Oded Regev 0001
• Noah Stephens-Davidowitz

We give a polynomial-time quantum reduction from worst-case (ideal) lattice problems directly to decision (Ring-)LWE. This extends to decision all the worst-case hardness results that were previously known for the search version, for the same or even better parameters and with no algebraic restrictions on the modulus or number field. Indeed, our reduction is the first that works for decision Ring-LWE with any number field and any modulus.

STOC Conference 2013 Conference Paper

Classical hardness of learning with errors

• Zvika Brakerski
• Adeline Langlois
• Chris Peikert
• Oded Regev 0001
• Damien Stehlé

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.

FOCS Conference 2011 Conference Paper

Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings

• Daniel Dadush
• Chris Peikert
• Santosh S. Vempala

We give a novel algorithm for enumerating lattice points in any convex body, and give applications to several classic lattice problems, including the Shortest and Closest Vector Problems (SVP and CVP, respectively) and Integer Programming (IP). Our enumeration technique relies on a classical concept from asymptotic convex geometry known as the M-ellipsoid, and uses as a crucial subroutine the recent algorithm of Micciancio and Voulgaris (STOC 2010)for lattice problems in the ℓ 2 norm. As a main technical contribution, which may be of independent interest, we build on the techniques of Klartag (Geometric and Functional Analysis, 2006) to give an expected 2 O(n) -time algorithm for computing an M-ellipsoid for any n-dimensional convex body. As applications, we give deterministic 2 O(n) -time and -space algorithms for solving exact SVP, and exact CVP when the target point is sufficiently close to the lattice, on n-dimensional lattices in any (semi-)norm given an M-ellipsoid of the unit ball. In many norms of interest, including all ℓ p norms, an M-ellipsoid is computable in deterministic poly(n) time, in which case these algorithms are fully deterministic. Here our approach may be seen as a derandomization of the "AKS sieve" for exact SVP and CVP (Ajtai, Kumar, and Siva Kumar, STOC2001 and CCC 2002). As a further application of our SVP algorithm, we derive an expected O(f*(n)) n -time algorithm for Integer Programming, where f*(n) denotes the optimal bound in the so-called "flatnesstheorem, " which satisfies f*(n) = O(n 4/3 polylog(n))and is conjectured to be f*(n) = O(n). Our runtime improves upon the previous best of O(n 2 ) n by Hildebrand and Koppe (2010).

STOC Conference 2009 Conference Paper

Public-key cryptosystems from the worst-case shortest vector problem: extended abstract

• Chris Peikert

We construct public-key cryptosystems that are secure assuming the worst-case hardness of approximating the minimum distance on n-dimensional lattices to within small Poly(n) factors. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. As an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-case approximation factor than prior schemes.

STOC Conference 2008 Conference Paper

Lossy trapdoor functions and their applications

• 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 lattice problems. Using lossy TDFs, we develop a new approach for constructing several important cryptographic primitives, including (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure cryptosystems. All of the constructions are simple, efficient, and black-box. These results resolve some long-standing open problems in cryptography. They give the first known injective trapdoor functions based on problems not directly related to integer factorization, and provide the first known CCA-secure cryptosystem based solely on the worst-case complexity of lattice problems.

STOC Conference 2008 Conference Paper

Trapdoors for hard lattices and new cryptographic constructions

• 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 length of the shortest nonzero vector to within certain polynomial factors). Our contributions include a new notion of trapdoor function with preimage sampling , simple and efficient "hash-and-sign" digital signature schemes, and identity-based encryption. A core technical component of our constructions is an efficient algorithm that, given a basis of an arbitrary lattice, samples lattice points from a discrete Gaussian probability distribution whose standard deviation is essentially the length of the longest Gram-Schmidt vector of the basis. A crucial security property is that the output distribution of the algorithm is oblivious to the particular geometry of the given basis.

STOC Conference 2007 Conference Paper

Lattices that admit logarithmic worst-case to average-case connection factors

• Chris Peikert
• Alon Rosen

SODA Conference 2003 Conference Paper

Lower bounds for collusion-secure fingerprinting

• Chris Peikert
• Abhi Shelat
• Adam Smith 0006