Non-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations
Abstract
The power of adaptivity in algorithms has been intensively studied in diverse areas of theoretical computer science. In this paper, we obtain a number of sharp lower bound results which show that adaptivity provides a significant extra power in cryptanalytic time-space tradeoffs with (possibly unlimited) preprocessing time.
Fields of Study & Subjects
Coding theory and cryptography
graph theory and CDMA systems
Cryptography and Data Security
Publication details
- Pages
- 1660–1671
- Publication date
- 9 June 2026
- Language
- EN