International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Provable Time-Memory Trade-Offs: Symmetric Cryptography Against Memory-Bounded Adversaries

Authors:
Stefano Tessaro
Aishwarya Thiruvengadam
Download:
DOI: 10.1007/978-3-030-03807-6_1
Search ePrint
Search Google
Conference: TCC 2018
Abstract: We initiate the study of symmetric encryption in a regime where the memory of the adversary is bounded. For a block cipher with n-bit blocks, we present modes of operation for encryption and authentication that guarantee security beyond$$2^n$$ encrypted/authenticated messages, as long as (1) the adversary’s memory is restricted to be less than $$2^n$$ bits, and (2) the key of the block cipher is long enough to mitigate memory-less key-search attacks. This is the first proposal of a setting which allows to bypass the $$2^n$$ barrier under a reasonable assumption on the adversarial resources.Motivated by the above, we also discuss the problem of stretching the key of a block cipher in the setting where the memory of the adversary is bounded. We show a tight equivalence between the security of double encryption in the ideal-cipher model and the hardness of a special case of the element distinctness problem, which we call the list-disjointness problem. Our result in particular implies a conditional lower bound on time-memory trade-offs to break PRP security of double encryption, assuming optimality of the worst-case complexity of existing algorithms for list disjointness.
BibTeX
@inproceedings{tcc-2018-28986,
  title={Provable Time-Memory Trade-Offs: Symmetric Cryptography Against Memory-Bounded Adversaries},
  booktitle={Theory of Cryptography},
  series={Theory of Cryptography},
  publisher={Springer},
  volume={11239},
  pages={3-32},
  doi={10.1007/978-3-030-03807-6_1},
  author={Stefano Tessaro and Aishwarya Thiruvengadam},
  year=2018
}