Fast Fourier orthogonalization

DOI10.1145/2930889.2930923MaRDI QIDQ2985827zbMATH OpenOpenAlexFDO

Authors Léo Ducas, Thomas Prest

Publication date 10 May 2017

Published in Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://ir.cwi.nl/pub/24688

zbMATH Keywords

circulant matricescomplexitycryptographyfast Fourier transformGram-Schmidt decompositionGram-Schmidt orthogonalizationlattice algorithmsmatrix factorizationnearest plane algorithmorthogonalizationperformances

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Orthogonalization in numerical linear algebra (65F25) Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20) Cryptography (94A60)

Recommendations

• Towards faster polynomial-time lattice reduction
• Quadratic time, linear space algorithms for Gram-Schmidt orthogonalization and Gaussian sampling in structured lattices
• Fast Fourier Orthogonalization over NTRU Lattices
• Fast LLL-type lattice reduction
• FFT program generation for ring LWE-based cryptography

Cited in

(34)

• Faster Gaussian sampling for trapdoor lattices with arbitrary modulus
• Key recovery from Gram-Schmidt norm leakage in hash-and-sign signatures over NTRU lattices
• Implementation of lattice trapdoors on modules and applications
• Integral matrix Gram root and lattice Gaussian sampling without floats
• Gadget-based iNTRU lattice trapdoors
• \textsc{Mitaka}: a simpler, parallelizable, maskable variant of \textsc{Falcon}
• scientific article; zbMATH DE number 3850444 (Why is no real title available?)
• Fast Fourier Transform Accelerated Fast Multipole Algorithm
• Compact privacy protocols from post-quantum and timed classical assumptions
• Towards a simpler lattice gadget toolkit
• Fast algorithms using orthogonal polynomials
• Improved power analysis attacks on Falcon
• Shorter hash-and-sign lattice-based signatures
• \textsc{Hawk}: module LIP makes lattice signatures fast, compact and simple
• BLOOM: bimodal lattice one-out-of-many proofs and applications
• Compact lattice gadget and its applications to hash-and-sign signatures
• Fast Fourier Orthogonalization over NTRU Lattices
• \textsc{Antrag}: annular NTRU trapdoor generation. Making \textsc{Mitaka} as secure as FALCON
• On Gaussian sampling, smoothing parameter and application to signatures
• Towards compact identity-based encryption on ideal lattices
• Crowhammer: full key recovery attack on \textsc{Falcon} with a single Rowhammer bit flip
• Do not disturb a sleeping Falcon. Floating-point error sensitivity of the Falcon sampler and its consequences
• Fast Fourier transform and Gaussian sampling instructions designed for FALCON digital signature
• Post-quantum online/offline signatures
• Thorough power analysis on Falcon Gaussian samplers and practical countermeasure
• Current paradigms for construction of lattice-based digital signature schemes
• Predicting module-lattice reduction
• GPV preimage sampling with weak smoothness and its applications to lattice signatures
• A closer look at \textsc{Falcon}
• Lattice EPID with efficient revocation
• A survey of polynomial multiplications for lattice-based cryptosystems
• Generating \textsc{Falcon} trapdoors via Gibbs sampler
• Refined modelling of the primal attack, and variants against Module-LWE
• A comparison of unified multiplier designs for the \textsc{Falcon} post-quantum digital signature. A case study of baseline, Tiling, Comba and Karatsuba approaches for FPGA and ASIC

This page was built for publication: Fast Fourier orthogonalization

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