Algebraic attacks against random local functions and their countermeasures
From MaRDI portal
Publication:4600698
DOI10.1137/16M1085942zbMATH Open1417.94039MaRDI QIDQ4600698FDOQ4600698
Authors: Benny Applebaum, Shachar Lovett 
Publication date: 12 January 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
Cites Work
- Relations between average case complexity and approximation complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- A new efficient algorithm for computing Gröbner bases \((F_4)\)
- Proof verification and the hardness of approximation problems
- Communication Theory of Secrecy Systems*
- Probabilistic checking of proofs
- Title not available (Why is that?)
- The complexity of theorem-proving procedures
- A new proof of Szemerédi's theorem
- Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
- Efficient algorithms for solving overdefined systems of multivariate polynomial equations
- Title not available (Why is that?)
- Advanced Encryption Standard – AES
- Advances in Cryptology - CRYPTO 2003
- Efficient noise-tolerant learning from statistical queries
- Public-key cryptography from different assumptions
- Candidate one-way functions based on expander graphs
- Cryptography with constant computational overhead
- Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
- On the security of Goldreich's one-way function
- Title not available (Why is that?)
- Pseudorandom generators with long stretch and low locality from random local one-way functions
- Cryptography in $NC^0$
- On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the one-way function candidate proposed by Goldreich
- A dichotomy for local small-bias generators
- On the complexity of random satisfiability problems with planted solutions (extended abstract)
- On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
- Input locality and hardness amplification
- Cryptographic hardness of random local functions. Survey
- Statistical algorithms and a lower bound for detecting planted cliques
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Title not available (Why is that?)
- Lower bounds for polynomial calculus in the case of nonbinomial ideals.
- The Computational Benefit of Correlated Instances
- Towards an understanding of polynomial calculus: new separations and lower bounds (extended abstract)
Cited In (16)
- Expander-Based Cryptography Meets Natural Proofs
- Worst-case subexponential attacks on PRGs of constant degree or constant locality
- Public-key encryption, local pseudorandom generators, and the low-degree method
- Progress in Cryptology - INDOCRYPT 2004
- Expander-based cryptography meets natural proofs
- Algebraic attacks against random local functions and their countermeasures
- Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
- The replica symmetric phase of random constraint satisfaction problems
- A dichotomy for local small-bias generators
- A dichotomy for local small-bias generators
- Cryptographic hardness of random local functions. Survey
- Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error
- On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator
- Boolean functions for homomorphic-friendly stream ciphers
- On the fast algebraic immunity of threshold functions
- Local Randomness in Polynomial Random Number and Random Function Generators
This page was built for publication: Algebraic attacks against random local functions and their countermeasures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4600698)
