1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

格子暗号ベースの準同型暗号・秘密計算の理解に必要な数学の知識をまとめてみる

Last updated at Posted at 2022-09-09

タイトルにあるとおりで,いくつかの準同型暗号の論文に対して,必要な数学の知識をまとめます.

個人的には,数学科学部2年生レベルの知識(特に「代数学」・「確率・統計」・「計算量理論」の3つ)さえ揃っていれば,大体の暗号理論の論文は読めると思いますが,
実際のところどうなんっていうのが気になったので,今まで読んできた論文などの振り返りも兼ねて,必要だと思われる数学の知識をまとめてみようと思います.

レベル分けとしては,次の3つで分けます:

  • 必須
  • 知っているとよい(より良く議論を理解できる)
  • 知らなくてもよい(背景的な部分)

知っているとよい,は,論文中で導入・言及があるものの,土台を知っていた方がよりスッキリ理解できる部分です.
知らなくてもよい,は,直接議論には関係しないけど,背景にはこういう分野があることを表します.

それぞれの分類

イデアル格子暗号入門

必須

  • 高校数学(複素平面・mod)

知っているとよい

  • 群論(巡回群)
  • 環論(イデアル)
  • 確率・統計(正規分布)

*巡回群,は直接出てきませんが,知っていると円分整数の見通しがかなり良くなるかと

知らなくてもよい

  • 初等整数論・有限体(オイラー関数)
  • Galois理論・円分体(円分多項式・円分整数)

Generalized Compact Knapsacks are Collision Resistant

必須

  • 高校数学(mod)

知っているとよい

  • 線型代数($L_p, L_{\infty}$ ノルム・線型独立・基底)
  • 微積($\varepsilon$-$N$, $\varepsilon$-$\delta$)
  • 環論(イデアル・剰余環・多項式環・既約多項式)
  • 計算量理論(確率的多項式時間アルゴリズム)
  • 確率・統計(正規分布・一様分布・条件付確率)

*($L_p, L_{\infty}$ ノルム)は通常,関数解析の文脈で登場することが多いですが,さすがに一部分すぎるので,線型代数の範囲としました

知らなくてもよい

  • 位相空間(距離空間)
  • 加群

*normとか距離の定義は知っていてもよいかもです

Programmable Bootstrapping Enables Efficient Homomorphic Inference of Deep Neural Networks

必須

  • 高校数学(mod)

知っているとよい

  • 線型代数(Tensor積・$L_{\infty}$ ノルム・基底)
  • 環論(剰余環・多項式環・既約多項式)
  • Galois理論・円分体(円分多項式)
  • 加群(Torus)
  • 確率・統計(正規分布)

*基底については,「2成分の暗号文同士を掛けると,3成分になって・・・」みたいな部分を見通しよく理解するためです

知らなくてもよい

  • 多様体(Torus)

*イデアル格子暗号入門と異なり,「2べきの$N$について,$2N$次の円分多項式の次数は$N$」をクリティカルに使う部分があるので,今回は知っているとよいに入れました

BFV, CKKS, TFHE: Which One is the Best for a Secure Neural Network Evaluation in the Cloud?

必須

  • 高校数学(mod)
  • 環論(剰余環・多項式環・既約多項式)
  • 確率・統計(正規分布)

説明があまりに簡素すぎるので色々と必須枠に入れました

知っているとよい

  • 加群(Torus)

知らなくてもよい

  • 多様体(Torus)

Leveled Multikey FHE with constant-size ciphertexts from RLWE

必須

  • 高校数学(mod)

知っているとよい

  • 線型代数($L_{\infty}$ ノルム・基底)
  • 環論(剰余環・多項式環・既約多項式)
  • 確率・統計(正規分布)

知らなくてもよい
たぶんない???

まとめ

こうしてみると,意外と必要な知識が被っていることが分かります.
確率・統計は案外,正規分布だけでもどうにかなるもんなんですね.あと,$L_{\infty}$ ノルムも割と使う感じっぽいですね.

振り返ってみると,

実装メインなので,理論はそこそこの理解でいい
→高校数学と「代数(群論・環論)」はしっかりやって,あとはポイントごとに「正規分布」・「多項式時間アルゴリズム」・「円分多項式」などを理解(飛ばしてもいい)
*代数の数学書を何冊も読む必要はおそらくなくて,代数学から学ぶ暗号理論暗号から学ぶ代数学あたりで必要な箇所のみを勉強するのも1つの手

安全性の議論などをするため,理論をしっかり理解したい
→数学科学部2年生ぐらいまでの範囲(微積・Jordan標準形・位相など人による部分もある)
*学部3年生までの範囲を理解していたら,なおよいのはそれはそうなんですが,学部3年の範囲は広いので,いきなりやろうとすると大変かと

になりそうです.

ですが,どちらにも共通で一番大事なのは,行間を埋めて誤植を察する能力ですね・・・.

1
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?