Practical, Predictable Lattice Basis Reduction

No abstract is available for this paper.

• Publication year

  2016

• Venue

  International Conference on the Theory and Application of Cryptographic Techniques

• Publication date

  2016-05-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-662-49890-3_31
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Bounding basis reduction properties

  2016cited by this paper
• On the concrete hardness of Learning with Errors

  2015cited by this paper
• Fast Lattice Point Enumeration with Minimal Overhead

  2015cited by this paper
• Lattice Point Enumeration on Block Reduced Bases

  2015cited by this paper
• Approximating the densest sublattice from Rankin's inequality

  2014cited by this paper
• Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe

  2013cited by this paper
• Estimating Key Sizes for High Dimensional Lattice-Based Systems

  2013cited by this paper
• Algorithms for the Densest Sub-Lattice Problem

  2013cited by this paper
• SLIDE REDUCTION, SUCCESSIVE MINIMA AND SEVERAL APPLICATIONS

  2013cited by this paper
• Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction

  2012cited by this paper
• BKZ 2.0: Better Lattice Security Estimates

  2011cited by this paper
• Better Key Sizes (and Attacks) for LWE-Based Encryption

  2011cited by this paper
• Lattice Reduction Algorithms: Theory and Practice

  2011cited by this paper
• Terminating BKZ

  2011influential reference
• Analyzing Blockwise Lattice Algorithms Using Dynamical Systems

  2011influential reference
• Probabilistic Analyses of Lattice Reduction Algorithms

  2010cited by this paper
• Segment LLL Reduction of Lattice Bases Using Modular Arithmetic

  2010cited by this paper
• Lattice Enumeration Using Extreme Pruning

  2010influential reference
• Hermite's Constant and Lattice Algorithms

  2010influential reference
• Recursive Lattice Reduction

  2010cited by this paper
• Progress on LLL and Lattice Reduction

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

  2009cited by this paper
• Public-key cryptosystems from the worst-case shortest vector problem: extended abstract

  2009cited by this paper
• On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem

  2009cited by this paper
• The LLL Algorithm - Survey and Applications

  2009cited by this paper
• Speeding-up lattice reduction with random projections

  2008cited by this paper
• Finding short lattice vectors within mordell's inequality

  2008influential reference
• Speeding-Up Lattice Reduction with Random Projections (Extended Abstract)

  2008cited by this paper
• Predicting Lattice Reduction

  2008influential reference
• Improved Analysis of Kannan's Shortest Lattice Vector Algorithm

  2007influential reference
• A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU

  2007cited by this paper
• All of Nonparametric Statistics

  2007cited by this paper
• Symplectic Lattice Reduction and NTRU

  2006cited by this paper
• LLL on the Average

  2006cited by this paper
• Rankin's Constant and Blockwise Lattice Reduction

  2006cited by this paper
• All of Nonparametric Statistics (Springer Texts in Statistics)

  2006cited by this paper
• Fast LLL-type lattice reduction

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

  2005cited by this paper
• Low-dimensional lattice basis reduction revisited

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

  2004cited by this paper
• Hardness of approximating the shortest vector problem in lattices

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

  2004cited by this paper
• New lattice based cryptographic constructions

  2003cited by this paper
• The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces

  2003cited by this paper
• Lattice Reduction by Random Sampling and Birthday Methods

  2003cited by this paper
• On the equidistribution of Hecke points

  2003cited by this paper
• Segment LLL-Reduction of Lattice Bases

  2001cited by this paper
• The Two Faces of Lattices in Cryptology

  2001cited by this paper
• Lattice Reduction in Cryptology: An Update

  2000cited by this paper
• Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto '97

  1999cited by this paper
• The Eeectiveness of Lattice Attacks against Low-exponent Rsa

  1999cited by this paper
• The Effectiveness of Lattice Attacks Against Low-Exponent RSA

  1999cited by this paper
• Cryptanalysis of the Ajtai-Dwork Cryptosystem

  1998cited by this paper
• Factoring Polynomials with Rational Coeecients

  1998cited by this paper
• Lattice Reduction: A Toolbox for the Cryptanalyst

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

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

  1996cited by this paper
• Faster algorithms for integer lattice basis reduction

  1996cited by this paper
• Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction

  1995cited by this paper
• Block Reduced Lattice Bases and Successive Minima

  1994cited by this paper
• Simultaneous reduction of a lattice basis and its reciprocal basis

  1993cited by this paper
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems

  1991cited by this paper
• How to Break Okamoto's Cryptosystem by Reducing Lattice Bases

  1988cited by this paper
• A More Efficient Algorithm for Lattice Basis Reduction

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

  1987influential reference
• A Modification of the LLL Reduction Algorithm

  1987cited by this paper
• Algorithms to Construct Minkowski Reduced an Hermite Reduced Lattice Bases

  1985cited by this paper
• Improved methods for calculating vectors of short length in a lattice

  1985cited by this paper
• Improved algorithms for integer programming and related lattice problems

  1983cited by this paper
• Factoring polynomials with rational coefficients

  1982influential reference

• Generating Falcon Trapdoors via Gibbs Sampler

  2026cites this paper
• On a lattice-based post-quantum ring signature scheme

  2026cites this paper
• A Quasi-polynomial Time Algorithm for the Extrapolated Dihedral Coset Problem over Power-of-Two Moduli

  2025cites this paper
• Provable Speedups for SVP Approximation Under Random Local Blocks

  2025cites this paper
• Constructing Efficient Identity‐Based Signatures on Lattices

  2025cites this paper
• Predicting Module-Lattice Reduction

  2025cites this paper
• FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism

  2025cites this paper
• The More the Merrier! On Total Coding and Lattice Problems and the Complexity of Finding Multicollisions

  2025cites this paper
• Highly Scalable Searchable Symmetric Encryption for Boolean Queries from NTRU Lattice Trapdoors

  2025cites this paper
• Lattice basis reduction techniques

  2024cites this paper
• More Basis Reduction for Linear Codes: Backward Reduction, BKZ, Slide Reduction, and More

  2024cites this paper
• Revisiting PACD-based Attacks on RSA-CRT

  2024cites this paper
• A Complete Analysis of the BKZ Lattice Reduction Algorithm

  2024influential citation
• Analyzing Pump and jump BKZ algorithm using dynamical systems

  2024cites this paper
• Heuristic Number Geometry Method for Finding Low-Weight Codeword in Linear Block Codes

  2024cites this paper
• Improved Provable Reduction of NTRU and Hypercubic Lattices

  2024cites this paper
• The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices

  2024cites this paper
• Towards Compact Identity-based Encryption on Ideal Lattices

  2024cites this paper
• Phoenix: Hash-and-Sign with Aborts from Lattice Gadgets

  2024cites this paper
• Concrete Analysis of Quantum Lattice Enumeration

  2023cites this paper
• Antrag: Annular NTRU Trapdoor Generation

  2023cites this paper
• The Complexity of the Shortest Vector Problem

  2023cites this paper
• HAWK Specification Document

  2023cites this paper
• Individual discrete logarithm with sublattice reduction

  2023cites this paper
• Antrag: Annular NTRU Trapdoor Generation - Making Mitaka as Secure as Falcon

  2023cites this paper
• Generalized attack on ECDSA: known bits in arbitrary positions

  2023cites this paper
• A New Sieving Approach for Solving the HNP with One Bit of Nonce by Using Built-in Modulo Arithmetic

  2023cites this paper
• Compact Lattice Gadget and Its Applications to Hash-and-Sign Signatures

  2023cites this paper
• Improving Convergence and Practicality of Slide-type Reductions

  2023influential citation
• Recursive lattice reduction - A framework for finding short lattice vectors

  2023influential citation
• AKAME: A post-quantum authenticated key-agreement and message encryption scheme based on ring-LWE

  2022cites this paper
• Hawk: Module LIP makes Lattice Signatures Fast, Compact and Simple

  2022cites this paper
• Predicting BKZ Z-Shapes on q-ary Lattices

  2022cites this paper
• Shorter Hash-and-Sign Lattice-Based Signatures

  2022cites this paper
• Sharper bounds on four lattice constants

  2022cites this paper
• HybridPKE: A forward-secure non-interactive quantum-safe hybrid key exchange scheme

  2022cites this paper
• Improved Lattice Enumeration Algorithms by Primal and Dual Reordering Methods

  2022cites this paper
• Dual lattice attacks for closest vector problems (with preprocessing)

  2021cites this paper
• A Lattice Reduction Algorithm Based on Sublattice BKZ

  2021cites this paper
• Non-randomness of S-unit lattices

  2021cites this paper
• Dynamic self-dual DeepBKZ lattice reduction with free dimensions and its implementation

  2021cites this paper
• Towards Faster Polynomial-Time Lattice Reduction

  2021cites this paper
• Fast Factoring Integers by SVP Algorithms

  2021cites this paper
• Lattice Attacks on NTRU and LWE: A History of Refinements

  2021cites this paper
• On the Cryptographic Hardness of Learning Single Periodic Neurons

  2021cites this paper
• On the Smallest Ratio Problem of Lattice Bases

  2021cites this paper
• Encryption and Decryption of Images using GGH Algorithm: Proposed

  2021cites this paper
• Advanced Lattice Sieving on GPUs, with Tensor Cores

  2021cites this paper
• The nearest-colattice algorithm

  2020cites this paper
• Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP

  2020cites this paper
• Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes

  2020cites this paper
• On a hybrid approach to solve binary-LWE

  2020cites this paper
• LUSA: the HPC library for lattice-based cryptanalysis

  2020cites this paper
• On a Dual/Hybrid Approach to Small Secret LWE - A Dual/Enumeration Technique for Learning with Errors and Application to Security Estimates of FHE Schemes

  2020cites this paper
• The nearest-colattice algorithm

  2020cites this paper
• Analysis of DeepBKZ reduction for finding short lattice vectors

  2020cites this paper
• Self-dual DeepBKZ for finding short lattice vectors

  2020influential citation
• Faster Enumeration-based Lattice Reduction: Root Hermite Factor k^(1/(2k)) in Time k^(k/8 + o(k))

  2020cites this paper
• A 2n/2-Time Algorithm for √n-SVP and √n-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP

  2020cites this paper
• Fast Reduction of Algebraic Lattices over Cyclotomic Fields

  2020cites this paper
• Lattice Reduction with Approximate Enumeration Oracles: Practical Algorithms and Concrete Performance

  2020cites this paper
• On the Success Probability of Solving Unique SVP via BKZ

  2020cites this paper
• A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge

  2020cites this paper
• The Convergence of Slide-type Reductions

  2020cites this paper
• Cryptoanalysis of a Post-quantum Cryptography Algorithm

  2020influential citation
• On Bounded Distance Decoding with Predicate: Breaking the "Lattice Barrier" for the Hidden Number Problem

  2020cites this paper
• Dynamic Self-dual DeepBKZ Lattice Reduction with Free Dimensions

  2020cites this paper
• Algorithm Speci(cid:28)cations And Supporting Documentation

  2020cites this paper
• Achieving secure and efficient lattice-based public-key encryption: the impact of the secret-key distribution

  2019cites this paper
• Revisiting TFHE security against hybrid lattice attacks

  2019cites this paper
• A detailed analysis of the hybrid lattice-reduction and meet-in-the-middle attack

  2019cites this paper
• Sampling the Integers with Low Relative Error

  2019cites this paper
• Slide Reduction, Revisited - Filling the Gaps in SVP Approximation

  2019influential citation
• Solving Ring-LWE over Algebraic Integer Rings

  2019cites this paper
• Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU

  2019cites this paper
• Algorithm Speci(cid:28)cations And Supporting Documentation

  2019cites this paper
• Explicit Relation between Low-Dimensional LLL-Reduced Bases and Shortest Vectors

  2019cites this paper
• TFHE: Fast Fully Homomorphic Encryption Over the Torus

  2019cites this paper
• Fully Homomorphic Encryption with k-bit Arithmetic Operations

  2019cites this paper
• Solving Algebraically Structured LWE in Arbitrary Number Fields

  2019cites this paper
• Development of a Dual Version of DeepBKZ and Its Application to Solving the LWE Challenge

  2018cites this paper
• Towards Efficient Arithmetic for Ring-LWE based Homomorphic Encryption. (Vers une arithmétique efficace pour le chiffrement homomorphe basé sur le Ring-LWE)

  2018cites this paper
• A journey towards practical fully homomorphic encryption

  2018cites this paper
• Lattice-based digital signature and discrete gaussian sampling. (Signature électronique basée sur les réseaux euclidiens et échantillonnage selon une loi normale discrète)

  2018cites this paper
• Vers l'efficacité et la sécurité du chiffrement homomorphe et du cloud computing

  2018cites this paper
• Round 5 : Compact and Fast Post-Quantum Public-Key Encryption Draft Friday 30 th November , 2018

  2018cites this paper
• Fiat-Shamir From Simpler Assumptions

  2018cites this paper
• On the complexity of class group computations for large degree number fields

  2018influential citation
• On the Security of Lattice-Based Cryptography Against Lattice Reduction and Hybrid Attacks

  2018cites this paper
• A Novel Lattice Reduction Algorithm

  2018cites this paper
• Orthogonalized lattice enumeration for solving SVP

  2018cites this paper
• Shortest Vector from Lattice Sieving: a Few Dimensions for Free

  2018cites this paper
• Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem

  2018cites this paper
• Class Group Computations in Number Fields and Applications to Cryptology. (Calcul de Groupes de Classes d'un Corps de Nombres et Applications à la Cryptologie)

  2017cites this paper
• Second Order Statistical Behavior of LLL and BKZ

  2017cites this paper
• Revisiting Lattice Attacks on Overstretched NTRU Parameters

  2017cites this paper
• Revisiting the Expected Cost of Solving uSVP and Applications to LWE

  2017cites this paper
• Computing Generator in Cyclotomic Integer Rings - A Subfield Algorithm for the Principal Ideal Problem in L|Δ𝕂|(½) and Application to the Cryptanalysis of a FHE Scheme

  2017influential citation
• Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)

  2017cites this paper
• A Practical View of the State-of-the-Art of Lattice-Based Cryptanalysis

  2017cites this paper