メモリハード機能

暗号学において、メモリハード関数（MHF ）は、効率的に評価するために大量のメモリを必要とする関数である。 ^[1]これは、メモリ遅延によって計算が遅くなるコストが発生するメモリバウンド関数とは異なる。 ^{[2] MHFは、}キーストレッチングやプルーフオブワークで使用されている。これは、メモリ要件の増加により、非MHFと比較して、カスタムハードウェアの汎用ハードウェアに対する計算効率の優位性が大幅に低下するためである。^[3]^[1]

導入

MHF は、並列計算の有効性を減らすために、コンピュータ上で大量のメモリを消費するように設計されています。より少ないメモリを使用して関数を評価すると、かなりの時間ペナルティが発生します。各 MHF 計算には大量のメモリが必要なので、同時に実行できる関数計算の数は、使用可能なメモリの量によって制限されます。これにより、パスワードハッシュの総当たり攻撃や暗号通貨のマイニングなど、大量の入力に対して MHF を計算する際に、並列化を利用する特定用途向け集積回路やグラフィックス処理ユニットなどの専用ハードウェアの効率が低下します。^[1]^[4]

動機と例

ビットコインのプルーフ・オブ・ワークはSHA-256関数の繰り返し評価を使用するが、市販のCPUなどの現代の汎用プロセッサは、固定関数を何度も計算する場合、非効率的である。ビットコインのマイニング用に設計された特定用途向け集積回路（ASIC）などの専用ハードウェアは、ハッシュあたりx86 CPUよりも30,000倍少ないエネルギーで、はるかに高いハッシュレートを実現できる。^[4]これにより、ビットコインやその他の暗号通貨のマイニングの集中化が懸念された。^[4] ASICを使用するマイナーとCPUまたは市販のハードウェアを使用するマイナーの間にこの不平等があったため、後のプルーフ・オブ・ワークシステムの設計者は、CPUよりもはるかに高速にハッシュ関数を評価できるASICを構築するのが困難なハッシュ関数を利用した。^[3]

メモリコストはプラットフォームに依存しないため、^[1] MHFは、ハッシュ関数としてscryptを使用するLitecoinなどの暗号通貨マイニングで使用されています。 ^[3]また、正当なユーザーの計算時間を大幅に増加させることなく、漏洩したハッシュパスワードデータベースに対して多くの可能性のあるパスワードを試すコストを大幅に増加させるため、パスワードハッシュにも役立ちます。^[1]

記憶の硬さの測定

関数のメモリの難しさを測定する方法は様々です。よく見られる測定方法の1つは、累積メモリ複雑度（CMC）です。並列モデルでは、CMCは計算の各時間ステップで関数を計算するために必要なメモリの合計です。^[5]^[6]

その他の実行可能な対策としては、メモリ使用量を時間に対して積分したり、メモリバス上のメモリ帯域幅の消費量を測定することなどが挙げられます。高いメモリ帯域幅を必要とする関数は、「帯域幅が厳しい関数」と呼ばれることもあります。^[7]

バリエーション

MHF は、評価パターンに基づいて、データ依存メモリ困難関数 (dMHF) とデータ非依存メモリ困難関数 (iMHF) の 2 つのグループに分類できます。iMHF とは対照的に、dMHF のメモリアクセスパターンは、キー導出関数に提供されるパスワードなどの関数入力に依存します。^{[8] dMHF の例としては}scryptやArgon2dがあり、iMHF の例としてはArgon2iやcatenaがあります。これらの MHF の多くは、メモリの困難さから、パスワードハッシュ関数として使用するために設計されています。

dMHF の顕著な問題は、キャッシュタイミングなどのサイドチャネル攻撃を受けやすいことです。このため、パスワードをハッシュする際には iMHF が好まれます。しかし、iMHF は dMHF よりもメモリの堅牢性が弱いことが数学的に証明されています。^[9]

参考文献

^ abcde Chen, Binyi (2019). メモリハード関数：理論と実践が出会うとき（論文）。カリフォルニア大学サンタバーバラ校。
^ Dwork, Cynthia; Goldberg, Andrew; Naor, Moni (2003). Boneh, Dan (編). 「スパム対策のためのメモリ結合関数について」.暗号学の進歩 - CRYPTO 2003.コンピュータサイエンスの講義ノート. ベルリン、ハイデルベルク: Springer: 426–444. doi : 10.1007/978-3-540-45146-4_25 . ISBN 978-3-540-45146-4。
^ abc LIU, ALEC (2013-11-29). 「ビットコインを超えて：最も有望な暗号通貨ガイド」. Vice . 2023年9月30日閲覧。
^ abc Biryukov, Alex; Khovratovich, Dmitry (2015). Iwata, Tetsu; Cheon, Jung Hee (eds.). 「メモリ困難な関数のトレードオフ暗号解析」。Advances in Cryptology – ASIACRYPT 2015。Lecture Notes in Computer Science。ベルリン、ハイデルベルク：Springer：633–657。doi ：10.1007 /978-3-662-48800-3_26。ISBN 978-3-662-48800-3。
^ (AS15) Alwen、Serbineko、高並列複雑度グラフとメモリ困難な関数、2015
^ Alwen, Joel; Blocki, Jeremiah; Pietrzak, Krzysztof (2017-07-07). 「持続的な空間複雑性」. arXiv : 1705.05313 [cs.CR].
^ Blocki, Jeremiah; Liu, Peiyuan; Ren, Ling; Zhou, Samson (2022). 「帯域幅困難な関数: 削減と下限値」(PDF)。Cryptology ePrint Archive 。 2023-01-12 にオリジナルからアーカイブ(PDF) 。 2023-01-11に取得。
^ Blocki, Jeremiah; Harsha, Ben; Kang, Siteng; Lee, Seunghoon; Xing, Lu; Zhou, Samson (2019). Boldyreva, Alexandra; Micciancio, Daniele (編). 「データ独立メモリハード関数: 新しい攻撃とより強力な構築」。暗号学の進歩 - CRYPTO 2019。コンピュータサイエンスの講義ノート。 Cham: Springer International Publishing: 573–607. doi :10.1007/978-3-030-26951-7_20. ISBN 978-3-030-26951-7。
^ Alwen, J., Blocki, J. (2016). データに依存しないメモリ困難な関数の効率的な計算。

[:0-1] Chen, Binyi (2019). メモリハード関数：理論と実践が出会うとき（論文）。カリフォルニア大学サンタバーバラ校。

[2] Dwork, Cynthia; Goldberg, Andrew; Naor, Moni (2003). Boneh, Dan (編). 「スパム対策のためのメモリ結合関数について」.暗号学の進歩 - CRYPTO 2003.コンピュータサイエンスの講義ノート. ベルリン、ハイデルベルク: Springer: 426–444. doi : 10.1007/978-3-540-45146-4_25 . ISBN 978-3-540-45146-4。

[:1-3] LIU, ALEC (2013-11-29). 「ビットコインを超えて：最も有望な暗号通貨ガイド」. Vice . 2023年9月30日閲覧。

[:2-4] Biryukov, Alex; Khovratovich, Dmitry (2015). Iwata, Tetsu; Cheon, Jung Hee (eds.). 「メモリ困難な関数のトレードオフ暗号解析」。Advances in Cryptology – ASIACRYPT 2015。Lecture Notes in Computer Science。ベルリン、ハイデルベルク：Springer：633–657。doi ：10.1007 /978-3-662-48800-3_26。ISBN 978-3-662-48800-3。

[5] (AS15) Alwen、Serbineko、高並列複雑度グラフとメモリ困難な関数、2015

[6] Alwen, Joel; Blocki, Jeremiah; Pietrzak, Krzysztof (2017-07-07). 「持続的な空間複雑性」. arXiv : 1705.05313 [cs.CR].

[7] Blocki, Jeremiah; Liu, Peiyuan; Ren, Ling; Zhou, Samson (2022). 「帯域幅困難な関数: 削減と下限値」(PDF)。Cryptology ePrint Archive 。 2023-01-12 にオリジナルからアーカイブ(PDF) 。 2023-01-11に取得。

[8] Blocki, Jeremiah; Harsha, Ben; Kang, Siteng; Lee, Seunghoon; Xing, Lu; Zhou, Samson (2019). Boldyreva, Alexandra; Micciancio, Daniele (編). 「データ独立メモリハード関数: 新しい攻撃とより強力な構築」。暗号学の進歩 - CRYPTO 2019。コンピュータサイエンスの講義ノート。 Cham: Springer International Publishing: 573–607. doi :10.1007/978-3-030-26951-7_20. ISBN 978-3-030-26951-7。

[9] Alwen, J., Blocki, J. (2016). データに依存しないメモリ困難な関数の効率的な計算。