Worst-case subexponential attacks on PRGs of constant degree or constant locality

Data encryption (aspects in computer science) (68P25) Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Cites Work

Title not available (Why is that?)
A new efficient algorithm for computing Gröbner bases \((F_4)\)
Fast Probabilistic Algorithms for Verification of Polynomial Identities
A Pseudorandom Generator from any One-way Function
Title not available (Why is that?)
Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
Title not available (Why is that?)
Title not available (Why is that?)
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Title not available (Why is that?)
Candidate One-Way Functions Based on Expander Graphs
Title not available (Why is that?)
Advances in Cryptology - EUROCRYPT 2004
The Degree of Regularity of HFE Systems
Solving degree, last fall degree, and related invariants
MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy
The XL-Algorithm and a Conjecture from Commutative Algebra
Comparison Between XL and Gröbner Basis Algorithms
On the Security of Goldreich’s One-Way Function
Pseudorandom generators with long stretch and low locality from random local one-way functions
On the complexity of the \(F_5\) Gröbner basis algorithm
Limits on low-degree pseudorandom generators (or: sum-of-squares meets program obfuscation)
Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields
Last Fall Degree, HFE, and Weil Descent Attacks on ECDLP
All in the XL Family: Theory and Practice
Secure arithmetic computation with constant computational overhead
Cryptographic Hardness of Random Local Functions–Survey
Indistinguishability obfuscation from LPN over \(\mathbb{F}_p\), DLIN, and PRGs in \(NC^0\)
On the concrete security of Goldreich's pseudorandom generator
Solving multivariate polynomial systems and an invariant from commutative algebra
Sum-of-squares meets program obfuscation, revisited
Algebraic attacks against random local functions and their countermeasures
Solving Quadratic Equations with XL on Parallel Architectures
Indistinguishability obfuscation from well-founded assumptions

Cited In (2)

Lower bounds for lattice-based compact functional encryption
Fast public-key silent OT and more from constrained Naor-Reingold

This page was built for publication: Worst-case subexponential attacks on PRGs of constant degree or constant locality

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