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

DOI10.1007/978-3-031-30545-0_2MaRDI QIDQ6138077zbMATH OpenOpenAlexFDO

Authors Akın Ünal

Publication date 16 January 2024

Published in Advances in Cryptology – EUROCRYPT 2023 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-30545-0_2

zbMATH Keywords

pseudorandomness of algebraic pseudorandom number generators of polynomial stretch

Mathematics Subject Classification ID

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)

Recommendations

• Algebraic attacks against random local functions and their countermeasures
• Algebraic attacks against random local functions and their countermeasures
• On the concrete security of Goldreich's pseudorandom generator
• Expander-based cryptography meets natural proofs
• Pseudorandom generators with long stretch and low locality from random local one-way functions

Cites work

• scientific article; zbMATH DE number 1703931 (Why is no real title available?)
• scientific article; zbMATH DE number 3857249 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• A Pseudorandom Generator from any One-way Function
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Advances in Cryptology - EUROCRYPT 2004
• Algebraic attacks against random local functions and their countermeasures
• All in the XL Family: Theory and Practice
• Candidate one-way functions based on expander graphs
• Comparison Between XL and Gröbner Basis Algorithms
• Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
• Cryptographic hardness of random local functions -- survey
• Cryptography with constant computational overhead
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Indistinguishability obfuscation from LPN over \(\mathbb{F}_p\), DLIN, and PRGs in \(NC^0\)
• Indistinguishability obfuscation from well-founded assumptions
• Last fall degree, HFE, and Weil descent attacks on ECDLP
• Limits on low-degree pseudorandom generators (or: sum-of-squares meets program obfuscation)
• MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy
• On the Security of Goldreich’s One-Way Function
• On the complexity of the \(F_5\) Gröbner basis algorithm
• On the concrete security of Goldreich's pseudorandom generator
• Pseudorandom generators with long stretch and low locality from random local one-way functions
• Secure arithmetic computation with constant computational overhead
• Solving degree and degree of regularity for polynomial systems over a finite field
• Solving degree, last fall degree, and related invariants
• Solving multivariate polynomial systems and an invariant from commutative algebra
• Solving quadratic equations with XL on parallel architectures
• Sum-of-squares meets program obfuscation, revisited
• The XL-Algorithm and a Conjecture from Commutative Algebra
• The degree of regularity of HFE systems

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)