### Memory-Tight Reductions

Benedikt Auerbach, David Cash, Manuel Fersch, and Eike Kiltz

##### Abstract

Cryptographic reductions typically aim to be tight by transforming an adversary A into an algorithm that uses essentially the same resources as A. In this work we initiate the study of memory efficiency in reductions. We argue that the amount of working memory used (relative to the initial adversary) is a relevant parameter in reductions, and that reductions that are inefficient with memory will sometimes yield less meaningful security guarantees. We then point to several common techniques in reductions that are memory-inefficient and give a toolbox for reducing memory usage. We review common cryptographic assumptions and their sensitivity to memory usage. Finally, we prove an impossibility result showing that reductions between some assumptions must unavoidably be either memory- or time-inefficient. This last result follows from a connection to data streaming algorithms for which unconditional memory lower bounds are known.

Available format(s)
Publication info
Keywords
memorytightnessprovable securityreduction
Contact author(s)
manuel fersch @ rub de
History
2018-04-12: revised
See all versions
Short URL
https://ia.cr/2017/675

CC BY

BibTeX

@misc{cryptoeprint:2017/675,
author = {Benedikt Auerbach and David Cash and Manuel Fersch and Eike Kiltz},
title = {Memory-Tight Reductions},
howpublished = {Cryptology ePrint Archive, Paper 2017/675},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/675}},
url = {https://eprint.iacr.org/2017/675}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.