Tight time-space lower bounds for finding multiple collision pairs and their applications

DOI10.1007/978-3-030-45721-1_15zbMath1479.94156OpenAlexW3013357475MaRDI QIDQ2055617

Itai Dinur

Publication date: 1 December 2021

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

zbMATH Keywords

cryptanalysistime-space tradeoffprovable securityparallel collision searchdouble encryption\(R\)-way branching programcollision search problem

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items (5)

Hiding in plain sight: memory-tight proofs via randomness programming ⋮ On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing ⋮ Finding many collisions via reusable quantum walks. Application to lattice sieving ⋮ On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing ⋮ Memory-tight multi-challenge security of public-key encryption

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
• A time-space tradeoff for sorting on non-oblivious machines
• Pseudorandom generators for space-bounded computation
• The computational complexity of universal hashing
• Parallel collision search with cryptanalytic applications
• The space complexity of approximating the frequency moments
• Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries
• Memory-tight reductions
• Improved low-memory subset sum and LPN algorithms via multiple collisions
• Tight time-memory trade-offs for symmetric encryption
• Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
• High Parallel Complexity Graphs and Memory-Hard Functions
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• Time-space lower bounds for satisfiability
• Time-space trade-off lower bounds for randomized computation of decision problems
• Improved Generic Algorithms for 3-Collisions
• A cryptanalytic time-memory trade-off
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Space bounds for a game on graphs
• Near-Optimal Time-Space Tradeoff for Element Distinctness
• Fast Learning Requires Good Memory
• Scrypt Is Maximally Memory-Hard
• Advances in Cryptology - CRYPTO 2003
• Pebbling and Proofs of Work
• Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Tight time-space lower bounds for finding multiple collision pairs and their applications