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

DOI10.1007/978-3-030-45724-2_15MaRDI QIDQ2119020zbMATH OpenOpenAlexFDO

Authors 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 complexitymode of operationprovable securitystreaming algorithmswitching lemmatime-memory tradeoff

Mathematics Subject Classification ID

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

Recommendations

• Tight time-memory trade-offs for symmetric encryption
• How many queries are needed to distinguish a truncated random permutation from a random function?
• The advantage of truncated permutations
• The iterated random function problem
• Super-linear time-memory trade-offs for symmetric encryption

Cites work

• A monte carlo method for factorization
• An improved Monte Carlo factorization algorithm
• An information complexity approach to extended formulations
• An information statistics approach to data stream and communication complexity
• Communication Complexity
• Communication complexity of set-disjointness for all probabilities
• Elements of Information Theory
• scientific article; zbMATH DE number 3960854 (Why is no real title available?)
• scientific article; zbMATH DE number 1302860 (Why is no real title available?)
• scientific article; zbMATH DE number 1088242 (Why is no real title available?)
• scientific article; zbMATH DE number 7250149 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• scientific article; zbMATH DE number 4185033 (Why is no real title available?)
• Information-theoretic indistinguishability via the chi-squared method
• On the distributional complexity of disjointness
• Private vs. common random bits in communication complexity
• Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries
• Pseudorandom generators for space-bounded computation
• The Probabilistic Communication Complexity of Set Intersection
• The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs
• The space complexity of approximating the frequency moments
• Tight time-memory trade-offs for symmetric encryption

Cited in

(8)

• The iterated random function problem
• How many queries are needed to distinguish a truncated random permutation from a random function?
• The memory-tightness of authenticated encryption
• Super-linear time-memory trade-offs for symmetric encryption
• Hiding in plain sight: memory-tight proofs via randomness programming
• Memory-tight multi-challenge security of public-key encryption
• Succinct PPRFs via memory-tight reductions
• Plinko: single-server PIR with efficient updates via invertible PRFs

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

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