scientific article; zbMATH DE number 7758323
From MaRDI portal
Publication:6062142
DOI10.4230/lipics.approx/random.2020.21arXiv2002.07235MaRDI QIDQ6062142
Ran Raz, Pravesh K. Kothari, Sumegha Garg
Publication date: 31 October 2023
Full work available at URL: https://arxiv.org/abs/2002.07235
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
bounded storage cryptographydistinguishing problemsGoldreich's local PRGmemory-sample tradeoffsrefuting CSPs
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A dichotomy for local small-bias generators
- Cryptographic hardness of random local functions. Survey
- Conditionally-perfect secrecy and a provably-secure randomized cipher
- Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries
- Limits on low-degree pseudorandom generators (or: sum-of-squares meets program obfuscation)
- Indistinguishability obfuscation from trilinear maps and block-wise local PRGs
- Limits on the locality of pseudorandom generators and applications to indistinguishability obfuscation
- Randomness is linear in space
- Tight time-memory trade-offs for symmetric encryption
- Simple schemes in the bounded storage model
- Indistinguishability Obfuscation from Constant-Degree Graded Encoding Schemes
- Public-key cryptography from different assumptions
- Sum of Squares Lower Bounds from Pairwise Independence
- Efficient Non-interactive Secure Computation
- Candidate One-Way Functions Based on Expander Graphs
- Relations between average case complexity and approximation complexity
- Pseudorandom Generators in Propositional Proof Complexity
- Everlasting security in the bounded storage model
- Strongly refuting random CSPs below the spectral threshold
- Sum of squares lower bounds for refuting any CSP
- Time-space hardness of learning sparse parities
- Memory-sample tradeoffs for linear regression with small error
- Extractor-based time-space lower bounds for learning
- From average case complexity to improper learning complexity
- Advances in Cryptology - EUROCRYPT 2004
- Complexity theoretic limitations on learning halfspaces
- Algebraic attacks against random local functions and their countermeasures
- Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
- Advances in Cryptology - CRYPTO 2003
- On ε‐biased generators in NC0
This page was built for publication:
