Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures

DOI10.1007/s00145-008-9031-0zbMath1159.94369OpenAlexW1992226551MaRDI QIDQ1015359

Oded Regev, Phong Q. Nguyen

Publication date: 8 May 2009

Published in: Journal of Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00145-008-9031-0

zbMATH Keywords

momentlatticesgradient descentpublic-key cryptanalysisGGHNTRUSign

Mathematics Subject Classification ID

Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Related Items

On statistical learning of simplices: unmixing problem revisited ⋮ A Ring-LWE-based digital signature inspired by Lindner-Peikert scheme ⋮ \textsc{Mitaka}: a simpler, parallelizable, maskable variant of \textsc{Falcon} ⋮ Efficient Nyberg-Rueppel type of NTRU digital signature algorithm ⋮ A signature scheme from the finite field isomorphism problem ⋮ \textsc{Hawk}: module LIP makes lattice signatures fast, compact and simple ⋮ Loop-abort faults on lattice-based Fiat-Shamir and hash-and-sign signatures ⋮ Eigenvectors of Orthogonally Decomposable Functions ⋮ Generating shorter bases for hard random lattices ⋮ Modular lattice signatures, revisited ⋮ Lattice-based revocable certificateless signature ⋮ A spectral algorithm for latent Dirichlet allocation

Uses Software

• NTL
• McEliece
• FastICA
• NTRU
• NTRUSign

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Lovász' lattice reduction and the nearest lattice point problem
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Trapdoors for hard lattices and new cryptographic constructions
• Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures
• Lattice-based Cryptography
• Cryptographic Functions from Worst-Case Complexity Assumptions
• Advances in Cryptology - CRYPTO 2003
• Asymptotically Efficient Lattice-Based Digital Signatures
• Lattice-Based Cryptography