Algebraic Attacks against Random Local Functions and Their Countermeasures

Related Items

On the fast algebraic immunity of threshold functions ⋮ Expander-based cryptography meets natural proofs ⋮ Low-complexity weak pseudorandom functions in $\mathtt{AC}0[\mathtt{MOD}2$] ⋮ 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 ⋮ Expander-Based Cryptography Meets Natural Proofs ⋮ The replica symmetric phase of random constraint satisfaction problems

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Cryptographic hardness of random local functions. Survey
On the security of Goldreich's one-way function
On pseudorandom generators with linear stretch in $\mathrm{NC}^{0}$
A new efficient algorithm for computing Gröbner bases $(F_4)$
Lower bounds for polynomial calculus in the case of nonbinomial ideals.
Lower bounds for the polynomial calculus and the Gröbner basis algorithm
On the One-Way Function Candidate Proposed by Goldreich
Public-key cryptography from different assumptions
A Dichotomy for Local Small-Bias Generators
On the Complexity of Random Satisfiability Problems with Planted Solutions
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
The Computational Benefit of Correlated Instances
Input Locality and Hardness Amplification
Candidate One-Way Functions Based on Expander Graphs
Proof verification and the hardness of approximation problems
Efficient noise-tolerant learning from statistical queries
Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
Relations between average case complexity and approximation complexity
Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
Communication Theory of Secrecy Systems*
Probabilistic checking of proofs
Advanced Encryption Standard – AES
Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
Advances in Cryptology - CRYPTO 2003
Statistical algorithms and a lower bound for detecting planted cliques
The complexity of theorem-proving procedures
Cryptography in $NC^0$
A new proof of Szemerédi's theorem