On the streaming indistinguishability of a random permutation and a random function

DOI10.1007/978-3-030-45724-2_15zbMath1492.94090OpenAlexW2970326168MaRDI QIDQ2119020

Itai Dinur

Publication date: 23 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-45724-2_15

zbMATH Keywords

communication complexityprovable securitymode of operationstreaming algorithmswitching lemmatime-memory tradeoff

Mathematics Subject Classification ID

Cryptography (94A60) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (3)

Hiding in plain sight: memory-tight proofs via randomness programming ⋮ Memory-tight multi-challenge security of public-key encryption ⋮ The memory-tightness of authenticated encryption

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An information statistics approach to data stream and communication complexity
• Private vs. common random bits in communication complexity
• On the distributional complexity of disjointness
• Pseudorandom generators for space-bounded computation
• The space complexity of approximating the frequency moments
• Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries
• Information-theoretic indistinguishability via the chi-squared method
• Tight time-memory trade-offs for symmetric encryption
• The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs
• An improved Monte Carlo factorization algorithm
• The Probabilistic Communication Complexity of Set Intersection
• A monte carlo method for factorization
• Communication Complexity
• Elements of Information Theory
• An information complexity approach to extended formulations

This page was built for publication: On the streaming indistinguishability of a random permutation and a random function