Paper 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.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published by the IACR in EUROCRYPT 2018
- Keywords
- memorytightnesslower bounduniquenessblack-box reduction
- Contact author(s)
-
wang y ar @ m titech ac jp
t-matsuda @ aist go jp
hanaoka-goichiro @ aist go jp
keisuke @ is titech ac jp - History
- 2018-05-09: revised
- 2018-02-11: received
- See all versions
- Short URL
- https://ia.cr/2018/155
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/155,
author = {Yuyu Wang and Takahiro Matsuda and Goichiro Hanaoka and Keisuke Tanaka},
title = {Memory Lower Bounds of Reductions Revisited},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/155},
year = {2018},
url = {https://eprint.iacr.org/2018/155}
}
