CryptoDB
Provable Time-Memory Trade-Offs: Symmetric Cryptography Against Memory-Bounded Adversaries
| Authors: | |
|---|---|
| Download: | |
| 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
}