Limits on low-degree pseudorandom generators (or: sum-of-squares meets program obfuscation)

DOI10.1007/978-3-319-78375-8_21MaRDI QIDQ1648854zbMATH OpenOpenAlexFDO

Authors Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari

Publication date 9 July 2018

Full work available at URL https://doi.org/10.1007/978-3-319-78375-8_21

Mathematics Subject Classification ID

Cryptography (94A60)

Recommendations

• Limits on the locality of pseudorandom generators and applications to indistinguishability obfuscation
• Sum-of-squares meets program obfuscation, revisited
• Indistinguishability obfuscation from trilinear maps and block-wise local PRGs
• Algebraic attacks against random local functions and their countermeasures
• Indistinguishability obfuscation without multilinear maps: new paradigms via low degree weak pseudorandomness and security amplification

Cited in

(20)

• Pseudorandom functions in \(\text{TC}^0\) and cryptographic limitations to proving lower bounds
• Limits on the locality of pseudorandom generators and applications to indistinguishability obfuscation
• Candidate iO from homomorphic encryption schemes
• Indistinguishability obfuscation without maps: attacks and fixes for noisy linear FE
• Combiners for functional encryption, unconditionally
• Optimal broadcast encryption and CP-ABE from evasive lattice assumptions
• Matrix PRFs: constructions, attacks, and applications to obfuscation
• Sum-of-squares meets program obfuscation, revisited
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Generating random bits from an arbitrary source: fundamental limits
• One-Way Functions and (Im)perfect Obfuscation
• On the complexity of compressing obfuscation
• scientific article; zbMATH DE number 7758323 (Why is no real title available?)
• Candidate iO from homomorphic encryption schemes
• Worst-case subexponential attacks on PRGs of constant degree or constant locality
• Polynomial-time cryptanalysis of the subspace flooding assumption for post-quantum \(i\mathcal{O} \)
• Indistinguishability obfuscation
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Batched \& non-interactive blind signatures from lattices
• Indistinguishability obfuscation from ring key-homomorphic weak PRFs

This page was built for publication: Limits on low-degree pseudorandom generators (or: sum-of-squares meets program obfuscation)

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