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

No abstract is available for this paper.

• Publication year

  2007

• Venue

  Symposium on the Theory of Computing

• Publication date

  2007-06-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1250790.1250860
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Limits on the Hardness of Lattice Problems in ℓp Norms

  2008influential reference
• Limits on the Hardness of Lattice Problems in ell _p Norms

  2007cited by this paper
• Tensor-based hardness of the shortest vector problem to within almost polynomial factors

  2007cited by this paper
• Lattice problems and norm embeddings

  2006influential reference
• On basing one-way functions on NP-hardness

  2006cited by this paper
• New connections between derandomization, worst-case complexity and average-case complexity

  2006cited by this paper
• Generalized Compact Knapsacks Are Collision Resistant

  2006influential reference
• Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices

  2006influential reference
• Fast quantum algorithms for computing the unit group and class group of a number field

  2005cited by this paper
• On lattices, learning with errors, random linear codes, and cryptography

  2005influential reference
• Lattice problems in NP ∩ coNP

  2005cited by this paper
• User Interface, or User Interference?

  2004cited by this paper
• Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor

  2004cited by this paper
• Worst-case to average-case reductions based on Gaussian measures

  2004influential reference
• Hardness of approximating the shortest vector problem in lattices

  2004cited by this paper
• On Polynomial-Factor Approximations to the Shortest Lattice Vector Length

  2003cited by this paper
• Introductory Algebraic Number Theory: Bibliography

  2003cited by this paper
• A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor

  2003influential reference
• New lattice based cryptographic constructions

  2003influential reference
• Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

  2002influential reference
• A panorama in number theory or the view from Baker's garden

  2002cited by this paper
• The inapproximability of lattice and coding problems with preprocessing

  2002cited by this paper
• Constructions of codes from number fields

  2001cited by this paper
• A sieve algorithm for the shortest lattice vector problem

  2001cited by this paper
• The hardness of the closest vector problem with preprocessing

  2001cited by this paper
• On the Limits of Nonapproximability of Lattice Problems

  2000cited by this paper
• Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors

  1999influential reference
• Approximating the SVP to within a Factor (1+1/dimxi) Is NP-Hard under Randomized Reductions

  1999cited by this paper
• Construction de polynômes de petits discriminants

  1999cited by this paper
• The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)

  1998cited by this paper
• The shortest vector in a lattice is hard to approximate to within some constant

  1998cited by this paper
• A Table of Totally Complex Number Fields of Small Discriminants

  1998cited by this paper
• An improved worst-case to average-case connection for lattice problems

  1997cited by this paper
• A public-key cryptosystem with worst-case/average-case equivalence

  1997cited by this paper
• Approximating the SVP to within a factor (1 + 1/dimepsilon) is NP-hard under randomized reductions

  1997cited by this paper
• Generating hard instances of lattice problems (extended abstract)

  1996influential reference
• Collision-Free Hashing from Lattice Problems

  1996cited by this paper
• Inequalities for convex bodies and polar reciprocal lattices inRn

  1995influential reference
• New bounds in some transference theorems in the geometry of numbers

  1993cited by this paper
• A course in computational algebraic number theory

  1993cited by this paper
• Algorithms in algebraic number theory

  1992influential reference
• Sphere Packings, Lattices and Groups

  1990cited by this paper
• The hardness of decoding linear codes with preprocessing

  1990cited by this paper
• A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms

  1987cited by this paper
• Codes from algebraic number fields

  1986cited by this paper
• Factoring polynomials with rational coefficients

  1982cited by this paper
• Relativized cryptography

  1979cited by this paper
• Symmetric Bilinear Forms

  1973cited by this paper
• Proceedings of the fifth annual ACM symposium on Theory of computing

  1973cited by this paper
• Algebraic Number Theory

  1971cited by this paper

• On Tradeoffs in Learning-Augmented Algorithms

  2025cites this paper
• On the radii of Voronoi cells of rings of integers

  2025cites this paper
• Leftover Hash Lemma(s) Over Cyclotomic Rings

  2025cites this paper
• Tschirnhausen bundles of covers of the projective line

  2024cites this paper
• Compact Encryption based on Module-NTRU problems

  2024cites this paper
• Discrete Gaussians Modulo Sub-Lattices: New Leftover Hash Lemmas for Discrete Gaussians

  2024cites this paper
• Discriminants of Number Fields

  2024influential citation
• NTRU in Quaternion Algebras of Bounded Discriminant

  2023cites this paper
• Explicit Approximations to Class Field Towers

  2023influential citation
• Arithmetically equivalent number fields have approximately the same successive minima

  2022cites this paper
• Scrollar invariants, syzygies and representations of the symmetric group

  2022cites this paper
• Scalable CCA-secure public-key authenticated encryption with keyword search from ideal lattices in cloud computing

  2022cites this paper
• Enhancing Ring-LWE Hardness using Dedekind Index Theorem

  2022cites this paper
• The Influence of Public-Key Cryptography on Mathematics

  2022cites this paper
• Bounds on Successive Minima of Orders in Number Fields and Scrollar Invariants of Curves

  2022cites this paper
• The Hardness of LWE and Ring-LWE: A Survey

  2021cites this paper
• An efficient fully dynamic group signature with message dependent opening from lattice

  2021cites this paper
• Towards Classical Hardness of Module-LWE: The Linear Rank Case

  2020cites this paper
• Homomorphic lattice cryptosystems for secure signal processing

  2019cites this paper
• An efficient full dynamic group signature scheme over ring

  2019influential citation
• Order-LWE and the Hardness of Ring-LWE with Entropic Secrets

  2019cites this paper
• Chapter 1 Homomorphic Encryption — Theory and Application

  2019cites this paper
• On the Non-Existence of Short Vectors in Random Module Lattices

  2019cites this paper
• Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs

  2018influential citation
• Asymptotically Efficient Lattice-Based Digital Signatures

  2018influential citation
• Study of Somewhat Homomorphic Encryption Scheme for Image Erosion and Dilation

  2018cites this paper
• On the Ring-LWE and Polynomial-LWE problems

  2018influential citation
• Lattices Over Algebraic Integers With an Application to Compute-and-Forward

  2018cites this paper
• Lattice Index Codes From Algebraic Number Fields

  2017cites this paper
• WHERENCRYPTION NCTON OPERATESTO OBTAN

  2017cites this paper
• Pseudorandomness of ring-LWE for any ring and modulus

  2017cites this paper
• A Framework to Select Parameters for Lattice-Based Cryptography

  2017cites this paper
• Almost Universal Codes for MIMO Wiretap Channels

  2016cites this paper
• Efficient Commitments and Zero-Knowledge Protocols from Ring-SIS with Applications to Lattice-based Threshold Cryptosystems

  2016cites this paper
• Almost universal codes for fading wiretap channels

  2016cites this paper
• Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings

  2016cites this paper
• On Ideal Lattices over the Tensor Product of Number Fields and Ring Learning with Errors over Multivariate Rings

  2016cites this paper
• EEH: AGGH-like public key cryptosystem over the eisenstein integers using polynomial representations

  2016cites this paper
• On Ring Learning with Errors over the Tensor Product of Number Fields

  2016cites this paper
• A Decade of Lattice Cryptography

  2016cites this paper
• Recovering Short Generators of Principal Ideals in Cyclotomic Rings

  2016influential citation
• Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One

  2015cites this paper
• Adaptive compute-and-forward with lattice codes over algebraic integers

  2015cites this paper
• Research project : Almost universal codes achieving the ergodic capacity of multi-antenna fading channels Collaboration between

  2015cites this paper
• Lattice index codes from algebraic number fields

  2015cites this paper
• Candidate Multilinear Maps

  2015cites this paper
• Improved Short Lattice Signatures in the Standard Model

  2014cites this paper
• A quantum algorithm for computing the unit group of an arbitrary degree number field

  2014cites this paper
• Cryptography based on the Hardness of Decoding

  2014cites this paper
• A Local-Global Approach to Solving Ideal Lattice Problems

  2014cites this paper
• Worst-case to average-case reductions for module lattices

  2014cites this paper
• Chris Peikert – Research Statement

  2014cites this paper
• Lattice-Based Cryptography: Security Foundations and Constructions

  2014cites this paper
• A Toolkit for Ring-LWE Cryptography

  2013cites this paper
• Candidate Multilinear Maps from Ideal Lattices

  2013cites this paper
• Computing the unit group, class group, and compact representations in algebraic function fields

  2013cites this paper
• Homomorphic Encryption: Theory & Applications

  2013cites this paper
• Homomorphic Encryption — Theory and Application

  2013cites this paper
• Candidate Multilinear Maps from Ideal Lattices and Applications

  2012cites this paper
• The Geometry of Lattice Cryptography

  2011cites this paper
• Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages

  2011cites this paper
• Implementing Gentry's Fully-Homomorphic Encryption Scheme

  2011cites this paper
• Lattice-based signature schemes with additional features

  2011cites this paper
• Making NTRU as Secure as Worst-Case Problems over Ideal Lattices

  2011cites this paper
• Cryptography with Lattices

  2010cites this paper
• Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness

  2010cites this paper
• Lattice Cryptography: A White Paper

  2010cites this paper
• Short Bases of Lattices over Number Fields

  2010cites this paper
• Implementing Gentry ’ s Fully-Homomorphic Encryption Scheme Preliminary Report

  2010cites this paper
• Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding

  2010cites this paper
• Bonsai Trees, or How to Delegate a Lattice Basis

  2010cites this paper
• Algorithms for ray class groups and Hilbert class fields

  2010cites this paper
• On Ideal Lattices and Learning with Errors over Rings

  2010cites this paper
• Research Statement Chris Peikert 1 New Foundations for Cryptography

  2009cites this paper
• Bonsai Trees (or, Arboriculture in Lattice-Based Cryptography)

  2009cites this paper
• The Linux Kernel

  2009cites this paper
• Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures

  2009cites this paper
• Fully homomorphic encryption using ideal lattices

  2009cites this paper
• Asymptotically Efficient Lattice-Based Digital Signatures

  2008cites this paper
• Swifftx: a Proposal for the Sha-3 Standard

  2008cites this paper
• 1 . 2 Lattice-based cryptography

  2008cites this paper
• Limits on the Hardness of Lattice Problems in ℓp Norms

  2008cites this paper
• SWIFFT: A Modest Proposal for FFT Hashing

  2008cites this paper
• Towards practical lattice-based cryptography

  2008cites this paper
• Trapdoors for hard lattices and new cryptographic constructions

  2008cites this paper
• Limits on the Hardness of Lattice Problems in ell _p Norms

  2007cites this paper
• Lattice-Based Cryptography

  2006cites this paper
• Ring-LWE Hardness Based on Non-invertible Ideals (cid:63)

  year unknowncites this paper