Just how hard are rotations of \(\mathbb{Z}^n\)? Algorithms and cryptography with the simplest lattice

DOI10.1007/978-3-031-30589-4_9zbMath1528.94035OpenAlexW3217002692MaRDI QIDQ6083665

Huck Bennett, Atul Ganju, Noah Stephens-Davidowitz, Pura Peetathawatchai

Publication date: 8 December 2023

Published in: Advances in Cryptology – EUROCRYPT 2023 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-30589-4_9

zbMATH Keywords

public-key encryption schemebases for rotations of \(\mathbb{Z}^n\)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)

Related Items (1)

Fast Falcon signature generation and verification using ARMv8 NEON instructions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring polynomials with rational coefficients
• Bonsai trees, or how to delegate a lattice basis
• Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP
• LWE with side information: attacks and concrete security estimation
• Generating cryptographically-strong random lattice bases and recognizing rotations of \(\mathbb{Z}^n\)
• On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography
• Lattices with symmetry
• Revisiting the expected cost of solving uSVP and applications to LWE
• Improved hardness results for unique shortest vector problem
• A Decade of Lattice Cryptography
• Revisiting the Gentry-Szydlo Algorithm
• Approximating the densest sublattice from Rankin’s inequality
• Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
• On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
• Trapdoors for hard lattices and new cryptographic constructions
• Discrete Gaussian Sampling Reduces to CVP and SVP
• Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One
• A reverse Minkowski theorem
• Computing a Lattice Basis Revisited
• Deciding Orthogonality in Construction-A Lattices
• Probability Inequalities for Sums of Bounded Random Variables
• On the Lattice Isomorphism Problem
• Cryptography and Coding
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
• Classical hardness of learning with errors
• \textsc{Hawk}: module LIP makes lattice signatures fast, compact and simple

This page was built for publication: Just how hard are rotations of \(\mathbb{Z}^n\)? Algorithms and cryptography with the simplest lattice