Finding significant Fourier coefficients: clarifications, simplifications, applications and limitations

DOI10.4086/CJTCS.2018.006MaRDI QIDQ4615809zbMATH OpenOpenAlexFDO

Authors Steven D. Galbraith, Joel Laity, Barak Shani

Publication date 29 January 2019

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1607.01842

zbMATH Keywords

complete algorithmfunctions on finite abelian groupsignificant Fourier coefficients

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Cryptography (94A60)

Recommendations

• Solving Hidden Number Problem with One Bit Oracle and Advice
• The multivariate hidden number problem
• Public Key Cryptography – PKC 2004
• Security of most significant bits of \(g^{x^{2}}\).
• New lattice-based cryptographic constructions

Cites work

• scientific article; zbMATH DE number 1588478 (Why is no real title available?)
• scientific article; zbMATH DE number 1942436 (Why is no real title available?)
• scientific article; zbMATH DE number 1839461 (Why is no real title available?)
• scientific article; zbMATH DE number 1852142 (Why is no real title available?)
• scientific article; zbMATH DE number 799789 (Why is no real title available?)
• scientific article; zbMATH DE number 6472645 (Why is no real title available?)
• A hidden number problem in small subgroups
• A quantitative version of the Beurling-Helson theorem
• Absolutely convergent Fourier series. An improvement of the Beurling-Helson theorem
• Classical hardness of learning with errors
• GLV/GLS decomposition, power analysis, and attacks on ECDSA signatures with single-bit nonce bias
• Hard-core predicates for a Diffie-Hellman problem over finite fields
• Hardness of computing individual bits for one-way functions on elliptic curves
• Learning Decision Trees Using the Fourier Spectrum
• Modern cryptography, probabilistic proofs and pseudo-randomness
• On lattices, learning with errors, random linear codes, and cryptography
• On sets of large Fourier transform under changes in domain
• On the modular inversion hidden number problem
• Playing ``hide-and-seek with numbers: the hidden number problem, lattices and exponential sums
• Pseudorandom functions and lattices
• Public Key Cryptography – PKC 2004
• RSA and Rabin Functions: Certain Parts are as Hard as the Whole
• Randomized interpolation and approximation of sparse polynomials stPreliminary version
• Solving Hidden Number Problem with One Bit Oracle and Advice
• Sparse polynomial approximation in finite fields
• The insecurity of the digital signature algorithm with partially known nonces
• The multivariate hidden number problem

Cited in

(7)

• On sets of large Fourier transform under changes in domain
• On Fourier analysis of sparse Boolean functions over certain abelian groups
• An Application of Fourier Series to the Most Significant Digit Problem
• Connecting leakage-resilient secret sharing to practice: scaling trends and physical dependencies of prime field masking
• Solving Hidden Number Problem with One Bit Oracle and Advice
• The security of all private-key bits in isogeny-based schemes
• Solving the learning parity with noise problem using quantum algorithms

This page was built for publication: Finding significant Fourier coefficients: clarifications, simplifications, applications and limitations

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