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

DOI10.4086/CJTCS.2018.006zbMATH Open1472.94051arXiv1607.01842OpenAlexW4237007951MaRDI QIDQ4615809FDOQ4615809

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)

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

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

zbMATH Keywords

complete algorithmfunctions on finite abelian groupsignificant Fourier coefficients

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• On sets of large Fourier transform under changes in domain
• 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)