Cryptology ePrint Archive: Report 2018/155
Memory Lower Bounds of Reductions Revisited
Yuyu Wang, Takahiro Matsuda, Goichiro Hanaoka, and Keisuke Tanaka
Abstract: In Crypto 2017, Auerbach et al. initiated the study on memory-tight reductions and proved two negative results on the memory-tightness of restricted black-box reductions from multi-challenge security to single-challenge security for signatures and an artificial hash function. In this paper, we revisit the results by Auerbach et al. and show that for a large class of reductions treating multi-challenge security, it is impossible to avoid loss of memory-tightness unless we sacrifice the efficiency of their running-time. Specifically, we show three lower bound results. Firstly, we show a memory lower bound of natural black-box reductions from the multi-challenge unforgeability of unique signatures to any computational assumption. Then we show a lower bound of restricted reductions from multi-challenge security to single-challenge security for a wide class of cryptographic primitives with unique keys in the multi-user setting. Finally, we extend the lower bound result shown by Auerbach et al. treating a hash function to one treating any hash function with a large domain.
Category / Keywords: memory, tightness, lower bound, uniqueness, black-box reduction
Original Publication (in the same form): IACR-EUROCRYPT-2018
Date: received 8 Feb 2018, last revised 8 May 2018
Contact author: wang y ar at m titech ac jp, t-matsuda@aist go jp, hanaoka-goichiro@aist go jp, keisuke@is titech ac jp
Available format(s): PDF | BibTeX Citation
Version: 20180509:023453 (All versions of this report)
Short URL: ia.cr/2018/155
[ Cryptology ePrint archive ]