論文

査読有り
2018年

Memory lower bounds of reductions revisited

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
  • Yuyu Wang
  • ,
  • Takahiro Matsuda
  • ,
  • Goichiro Hanaoka
  • ,
  • Keisuke Tanaka

10820
開始ページ
61
終了ページ
90
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.1007/978-3-319-78381-9_3
出版者・発行元
Springer Verlag

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.

リンク情報
DOI
https://doi.org/10.1007/978-3-319-78381-9_3
URL
http://dblp.uni-trier.de/db/conf/eurocrypt/eurocrypt2018-1.html#conf/eurocrypt/Wang0HT18

エクスポート
BibTeX RIS