## IACR paper details

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

Booktitle | Theory of Cryptography |
---|

Volume | 11239 |
---|

Pages | 3-32 |
---|

Year | 2018 |
---|

URL | Search for the paper |
---|

DOI | 10.1007/978-3-030-03807-6_1 (link) |
---|

Author | Stefano Tessaro |
---|

Author | Aishwarya Thiruvengadam |
---|

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. |
---|

@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
}

Download a complete BibTeX file.