Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes

DOI10.1016/J.DAM.2019.09.017MaRDI QIDQ2306599zbMATH OpenOpenAlexWikidataFDO

Authors Noboru Kunihiro, Atsushi Takayasu

Publication date 23 March 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2019.09.017

zbMATH Keywords

BKZ reductionenumerationlatticesshortest vector problemslide reduction

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of block designs (05B05) Lattices and convex bodies (number-theoretic aspects) (11H06) Cryptography (94A60)

Recommendations

• Lattice Point Enumeration on Block Reduced Bases
• Improving convergence and practicality of slide-type reductions
• Analyzing blockwise lattice algorithms using dynamical systems
• Slide reduction, successive minima and several~applications
• The convergence of slide-type reductions

Cites work

• A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
• A hierarchy of polynomial time lattice basis reduction algorithms
• A sieve algorithm for the shortest lattice vector problem
• Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
• Analyzing blockwise lattice algorithms using dynamical systems
• BKZ 2.0: Better lattice security estimates
• Block Reduced Lattice Bases and Successive Minima
• Factoring polynomials with rational coefficients
• Fast lattice point enumeration with minimal overhead
• Faster exponential time algorithms for the shortest vector problem
• Finding short lattice vectors within Mordell's inequality
• Fully homomorphic encryption using ideal lattices
• G6K
• Hermite’s Constant and Lattice Algorithms
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• scientific article; zbMATH DE number 1852142 (Why is no real title available?)
• Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Lattice Point Enumeration on Block Reduced Bases
• Observation on the Minimum of a Positive Quadratic Form in Eight Variables
• On lattices, learning with errors, random linear codes, and cryptography
• Practical, Predictable Lattice Basis Reduction
• Progressive lattice sieving
• Rankin’s Constant and Blockwise Lattice Reduction
• Shortest vector from lattice sieving: a few dimensions for free
• Sieve algorithms for the shortest vector problem are practical
• Slide reduction, successive minima and several~applications
• The general sieve kernel and new records in lattice reduction
• Trapdoors for hard lattices and new cryptographic constructions
• Trapdoors for lattices: simpler, tighter, faster, smaller

Cited in

(3)

• Optimal Design of Sandwich Plates with a Rigid Obstacle
• BS: Blockwise Sieve Algorithm for Finding Short Vectors from Sublattices
• A complete analysis of the BKZ lattice reduction algorithm

Describes a project that uses

Uses Software

• G6K
• BKZ

This page was built for publication: Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2306599)