Tight time-space lower bounds for finding multiple collision pairs and their applications
type: Item
instance of: scholarly article
title: Tight time-space lower bounds for finding multiple collision pairs and their applications
zbMATH Open document ID: 1479.94156
DOI: 10.1007/978-3-030-45721-1_15
author: Itai Dinur
publication date: 2021-12-01T00:00:00Z
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 7436926
zbMATH Keywords: collision search problem
zbMATH Keywords: time-space tradeoff
zbMATH Keywords: \(R\)-way branching program
zbMATH Keywords: provable security
zbMATH Keywords: cryptanalysis
zbMATH Keywords: parallel collision search
zbMATH Keywords: double encryption
MaRDI profile type: Publication
full work available at URL: 978-3-030-45721-1 15
OpenAlex ID: W3013357475
cites work: Q4249346
cites work: The space complexity of approximating the frequency moments
cites work: Scrypt Is Maximally Memory-Hard
cites work: High Parallel Complexity Graphs and Memory-Hard Functions
cites work: Memory-tight reductions
cites work: Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs
cites work: A general Sequential Time-Space Tradeoff for Finding Unique Elements
cites work: Time-space trade-off lower bounds for randomized computation of decision problems
cites work: A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
cites work: A time-space tradeoff for sorting on non-oblivious machines
cites work: Q4364559
cites work: Improved low-memory subset sum and LPN algorithms via multiple collisions
cites work: Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
cites work: Concentration of Measure for the Analysis of Randomized Algorithms
cites work: Pebbling and Proofs of Work
cites work: Time-space lower bounds for satisfiability
cites work: A cryptanalytic time-memory trade-off
cites work: Tight time-memory trade-offs for symmetric encryption
cites work: Improved Generic Algorithms for 3-Collisions
cites work: Q5585021
cites work: The computational complexity of universal hashing
cites work: Pseudorandom generators for space-bounded computation
cites work: Advances in Cryptology - CRYPTO 2003
cites work: Space bounds for a game on graphs
cites work: Fast Learning Requires Good Memory
cites work: Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries
cites work: Parallel collision search with cryptanalytic applications
cites work: Q4409125
cites work: Near-Optimal Time-Space Tradeoff for Element Distinctness
cites work: Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
description: scientific article; zbMATH DE number 7436926