Paper 2017/675

Memory-Tight Reductions

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


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
Published by the IACR in CRYPTO 2017
memorytightnessprovable securityreduction
Contact author(s)
manuel fersch @ rub de
2018-04-12: revised
2017-07-11: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.