Tight time-space lower bounds for finding multiple collision pairs and their applications
From MaRDI portal
Publication:2055617
DOI10.1007/978-3-030-45721-1_15zbMath1479.94156OpenAlexW3013357475MaRDI QIDQ2055617
Publication date: 1 December 2021
Full work available at URL: https://doi.org/10.1007/978-3-030-45721-1_15
cryptanalysistime-space tradeoffprovable securityparallel collision searchdouble encryption\(R\)-way branching programcollision search problem
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
