Cryptology ePrint Archive: Report 2017/675

Memory-Tight Reductions

Benedikt Auerbach and David Cash and 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.

Category / Keywords: memory, tightness, provable security, reduction

Original Publication (in the same form): IACR-CRYPTO-2017

Date: received 7 Jun 2017, last revised 11 Jul 2017

Contact author: david cash at cs rutgers edu, eike kiltz@rub de, benedikt auerbach@rub de, manuel fersch@rub de

Available format(s): PDF | BibTeX Citation

Version: 20170711:105853 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]