## CryptoDB

Authors: Stefano Tessaro Aishwarya Thiruvengadam DOI: 10.1007/978-3-030-03807-6_1 Search ePrint Search Google TCC 2018 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,
booktitle={Theory of Cryptography},
series={Theory of Cryptography},
publisher={Springer},
volume={11239},
pages={3-32},
doi={10.1007/978-3-030-03807-6_1},