最先端の秘密計算技術、格子暗号スタディロードマップを公開！！（エンジニア、リサーチャー必読）

概要

@kenmaroです。
秘密計算、準同型暗号などの記事について投稿しています。

準同型暗号を用いた秘密計算は徐々に注目を集めつつあり、
ITエンジニアの方や、学生の方などで、
準同型暗号、とりわけ格子暗号について興味を持っている人も多いかと思います。

しかしながら、

• 研究としてクリプト（暗号）分野
  であり、論文が非常に難解である。（物理分野出身の筆者からしても読みにくい、、）

• 技術が基盤技術寄り（社会インフラ的な立ち位置）
  であるため、一般に生活している上でどう使われるのか、どう役に立つのかが想像しにくい。

• 日本語での解説が少ない
  ため（これは英語が読めない問題もあるかと思いつつ、）、どこから勉強すれば良いかわからない、また、キャッチアップに速度が出にくい。

というような問題点があります。
正直なところどんな分野であれ研究を進める上で上のような問題は常に存在するとは思いますが。。

そんな中、もし実際に研究にいくばくかの時間を費やした人間が

最適と思われるロードマップを公開していたら非常にありがたいのではないか

と考え、今回この記事を執筆しています。

自分が秘密計算技術に触れ始めた３年前、このような記事があれば非常にありがたかった、、

と思えるようなものになるように書いていきますので、どうぞご一読ください。

この流れに沿えばスムーズに最先端の理論や実装まで理解できる
というような解説記事や論文、Gitレポジトリの
ロードマップを紹介したいと思います。

学習マテリアルへのリンク

まず初めに、教材（解説論文やキータ記事、講義資料、githubへのリンクなど）
を一気に紹介します。

その後、各リンクについて理解するための知識やスキルセットについて、
また、教材の難易度（筆者の独断と偏見で決めています。）
について言及したいと思います。

基本的に上から順に読んでいけば、
１ヶ月もしないうちにある程度キャッチアップできるのではないかと思っています。
（まあ急ぐ必要はないのでゆっくりで問題ないですね。＜＝＝息抜きも大事！！）

以下、題名（著者）となっています。

ロードマップ

上から読んでいくことで、最新の研究まで超スピードで駆け上がれます。
一つ一つの記事について次章でコメントします。

• イデアル格子暗号入門 (情報セキュリティ研究科 教授 有田氏）
• 秘密計算エンジニアを始めて１年が経った (@kenmaro)
• 秘密計算エンジニアを始めて２年半が経った (@kenmaro)
• 格子暗号で新ブレイクスルー！！ プログラマブルブートストラップを解説！！ (@kenmaro)
• Programmable Bootstrapping Enables Efficient
  Homomorphic Inference of Deep Neural Networks (Zama AI)
• 格子暗号実装講義資料 (京都大学　松岡氏）
• TFHEpp Git レポジトリ（からのフォーク、元レポジトリでももちろん良い。）
  link here
• cuFHE Git レポジトリ（からのフォーク、元レポジトリでももちろん良い。）
  link here

オプション

ロードマップマテリアルのオプションとして、以下を追加しています。
オプションとした理由は、ある程度キャッチアップのスピードを確保するために

• クリプトリサーチャー以外だとかなり難解な論文
• 細かい実装の手法を解説したもの
• ロードマップマテリアルと内容が重複してしまうもの

を一旦省きたかったからです。
オプションのものについても、下でコメントします。

一つ目の論文はTFHEと呼ばれる格子暗号形式の原論文でとても素晴らしい論文です。
しかしながら、とても長い＋難解なので、一応オプションとしました。
私個人の意見ですが、この論文を隅々まで理解する必要は実装の面からはないと思っています。

• TFHE: Fast Fully Homomorphic Encryption
  over the Torus (Zama AI を中心としたグループ)
• [(完全)準同型暗号の最前線２（原理編）: TFHEの原理 #1 TLWE] (https://qiita.com/nindanaoto/items/82b63cb5453380c029b1) (@nindanaoto
  さん)
• (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #2 TRLWE & SampleExtarctIndex (@nindanaoto
  さん)
• (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #3 TRGSW & CMUX (@nindanaoto
  さん)
• (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #4 Blind Rotate (@nindanaoto
  さん)
• 素人が最先端のプログラマブルブートストラップを実装してみて分かったこと (@kenmaro)
• cuHE: A Homomorphic Encryption Accelerator Library (Worcester Polytechnic Institute: Weiさん)

ロードマップ詳解

ここでは、先程紹介したロードマップのマテリアルについて、
事前に必要な知識やスキルセット、
個人の独断と偏見による読解難易度やポイントなどについて解説します。

- イデアル格子暗号入門 (情報セキュリティ研究科 教授 有田氏）

コメント

言わずと知れた格子暗号入門に最適の講義資料です。
格子暗号がなぜ暗号化したまま計算できるのか、その数学的バックグラウンドである
イデアル格子暗号を大変わかりやすく解説してあります。
理系でないと少し難しいところがあるかもしれないですが、文系の人でも数学に苦手意識がなければ読み通せると思います。
もし難しければ、まわりの数学に詳しい人に聞いてみたり、私に質問してもらえれば答えれるかもしれません。

格子暗号を勉強し始めるにあたって一番基礎となる理論になるので、数回読み通すことは必須です。
格子を実際にノートの上に書いてみてベクトルを図示してみたり、
練習問題を手で書きながらやってみることで一体何をやっているのか理解できると思います。

必要な知識、スキルなど

代数学の一般知識、というと難しそうですが、
多項式演算や、簡単な複素平面の知識、論文での数学記号への簡単な理解
程度があれば読み進めれます。

難易度、期間

難易度　★★☆☆☆
期間　ある程度数学に苦手意識がなければ２、３日、苦手だと１〜２週間程度？

- 秘密計算エンジニアを始めて１年が経った (@kenmaro)

コメント

初っ端からいきなり難しいなぁ、と思った方も多かったかもしれませんが、
この記事に関しては研究のまとめ点となりますので数学の知識は不必要になります。

この教材の一番の伝えたい事は、研究の実際の技術的な事と言うよりは、

行われている研究全体を俯瞰したときに、どのような研究が近年行われているのかという流れを理解する

ところにあります。

この記事を読むことで、格子暗号における最近の10年の研究動向がわかるかと思います。
したがって、最後のほうに参考文献を大量に書いてはいるものの、それらを実際に読む必要はあまりありません。

1つ目の有田先生の講義資料を読んで難しいと感じた人でも、
このような難しい技術が実際に社会実装をされようとしていると言うようなワクワク感であったり、
それとともにその難しさ、一筋縄ではいかない感じが伝わるのではないかと思っています。

必要な知識、スキルなど

必要なスキルは特になし。

難易度、期間

難易度　★☆☆☆☆
期間　〜１日

- 秘密計算エンジニアを始めて２年半が経った (@kenmaro)

コメント

この記事は、一つ前の秘密計算エンジニアを始めて1年が経った、の続編になります。

この記事は、前回の記事よりもさらに初学者に簡単な内容になっています。

具体的には、

• 秘密計算の解説から始まり準同型暗号がどのようなシチュエーションで使われるのか
• 秘密計算に関連するいろいろなニュース

について解説をしています。

また、最後の方には、格子暗号を実装した実際のライブラリについても言及しており、
どのような研究母体がどのような形式の格子暗号を実用化しようとしているのか、についても一読できます。

必要な知識、スキルなど

必要なスキルは特になし。

難易度、期間

難易度　★☆☆☆☆
期間　〜１日

- 格子暗号で新ブレイクスルー！！ プログラマブルブートストラップを解説！！ (@kenmaro)

コメント

1つ目の記事で、格子暗号の一番基礎となる理論について学び、
2つ目と3つ目の記事で、格子暗号についての近年の研究動向や関連ニュース等について理解しました。

この記事を読むと、最近年の格子暗号研究内容でホットだったプログラマブルブートストラップについて理解できます。

ブートストラップと呼ばれる大変重要な格子暗号上の技術について簡単に解説をした後、
プログラマブルブートストラップの具体的な内容や、 プログラマブルブートストラップによって解決されること、それらを実装したライブラリ等について解説しています。

このプログラムブートストラップについては、2020年後半に発表されたものですので、
非常に最近の研究まで理解できるようになったという感覚が湧いてくると思います。
（実際、ここまでTFHEの理論から始まり理解するのは簡単なことではありません。）

必要な知識、スキルなど

少なくともこれ以前の３つの記事を読んでいること

難易度、期間

難易度　★★☆☆☆
期間　１、２日

- Programmable Bootstrapping Enables Efficient Homomorphic Inference of Deep Neural Networks (Zama AI)

コメント

ひとつ前の記事で紹介した、 プログラマブルブートストラップの元論文になります。
論文をあまり読まない人にとっては、難解に見えるかも知れませんが非常によく書かれた論文で、
腰をすえればきちんと読み解ける論文です。

また、この論文でのエッセンスが実際に口述のライブラリーでは実装されているため、ここでの理解が非常に重要になっています。

特に３、４章の

• 3.1 Encoding/Decoding のセクション
• 3.3 Leveled Operations のセクション
• 4.1 Blind Rotation のセクション
• 4.2 Look-up Table Evaluation のセクション

の理解が重要になってきます。

実際、この論文を読むことができれば、最先端の格子暗号技術を概ね理解したといっても過言ではないと思われます。

必要な知識、スキルなど

格子暗号理論についての基礎的な理解、 コンピューターサイエンスの一般的な知識(あれば良い程度)、英語を読む基礎的な力

難易度、期間

難易度　★★★★☆
期間　慣れていれば　〜１週間、　慣れていなければ〜２週間

- 格子暗号実装講義資料 (京都大学　松岡氏）

コメント

プログラマブルブートストラップに関しては格子暗号で暗号化する実数をトーラス上に記述したものになっています。

その形式のことをCGGI形式と呼びますが、この講義資料はそのCGGI形式の実装のために必要なアルゴリズムについて詳しく説明しています。

暗号理論についての知識と、コーディングについての知識がともに必要になります。
しかしながらこの講義資料をきちんと読むことができれば、
この次のGitHubのレポジトリのソースコードについても同様に理解ができると思います。

この講義資料をしっかりと理解すれば、フルスクラッチでの格子暗号実装も可能です。
自分の知る限り、ここまでよくまとまった実装に役立つ資料は世界に存在していません。

必要な知識、スキルなど

TFHEについての理解（上のZamaからの論文を読めていること）
C++もしくはPythonなどの言語の基礎知識
コンピューターサイエンスのアルゴリズムについての簡単な知識
コンピュータサイエンスにおける変数の型などによる基本的な知識

難易度、期間

難易度　★★★★☆
期間　今までの理解度が高ければ　〜３日、　難しいと感じれば〜２週間

- TFHEpp Git レポジトリ（からのフォーク、元レポジトリでももちろん良い。）link here

コメント

CGGI形式の格子暗号を世界最速レベルで実行できるレポジトリになります。

実装講義資料を見ながらソースコードを読むことによって、実際の実装についての理解がさらに深まると考えられます。
フォークされたレポジトリーを見ることで、プログラマブルブートストラップに必要なエンコーダー等の実際の実装についても理解が深まると思います。

コードなので、読みきると言うわけでは無いですがC++をある程度わかる人にとっても、
基本的に何をやっているのか十分に理解するまで数週間はかかるかと思います。

必要な知識、スキルなど

TFHEについての理解（上のZamaからの論文、実装の講義資料を読めていること）
C++が高いレベルで理解できる必要あり

難易度、期間

難易度　★★★★☆
期間　〜数週間

- cuFHE Git レポジトリ（からのフォーク、元レポジトリでももちろん良い。）link here

コメント

格子暗号の実装に関しては、ハードウェアを用いたアクセラレーション(速度の改善)が最新の研究の一部として行われています。

GPUを用いた高速化についてのレポジトリーがこのレポジトリになります。

実装を細かく追って行くのは非常に難しいですが、TFHEppのレポジトリを追えているのであれば比較的読めると思います。
CUDAはC言語にかなり精通していないと難しい印象です。
これを書いているVSPのメンバーや元となっているWeiさんなどを非常に尊敬しています。

必要な知識、スキルなど

TFHEについての理解（上のZamaからの論文、実装の講義資料を読めていること）
C++が高いレベルで理解できる必要あり
CUDAの知識、GPUについての知識

難易度、期間

難易度　★★★★★
期間　〜数週間

オプション詳解

ロードマップのオプションとして紹介したマテリアルについては、簡単にコメントをしたいと思います。

- TFHE: Fast Fully Homomorphic Encryption over the Torus (Zama AI を中心としたグループ)

コメント

TFHEの元論文。６０ページを超えている超大作の論文です。
たぶん（もし見当違いであればすみません。）学部生であれば、
この論文を理解して実装できればいい卒論が書けるのでは、とまで思うくらいすごい論文です。

かなり長いですが、読むのに必要な情報が全て書かれているセルフコンテインドな論文であるため、
他の論文を読む必要がほとんどありません。
従って参考論文に翻弄されることなく、集中して読むことができます。
もし余裕があれば必ず読んでおきたい論文です。

###- [(完全)準同型暗号の最前線２（原理編）: TFHEの原理 #1 TLWE] (https://qiita.com/nindanaoto/items/82b63cb5453380c029b1) (@nindanaoto
さん)
###- (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #2 TRLWE & SampleExtarctIndex (@nindanaoto
さん)
###- (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #3 TRGSW & CMUX (@nindanaoto
さん)
###- (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #4 Blind Rotate (@nindanaoto
さん)

まとめてコメント

これらの記事を原論文の代わりに（もしくはヘルプマテリアルとして）読むことをお勧めします。

内容としては、TFHEの元論文で紹介されているアルゴリズムを要所要所ごとに解説しています。
これらをきちんと理解する事は、格子暗号実装講義資料を読み解く上で非常に有益です。

###　- 素人が最先端のプログラマブルブートストラップを実装してみて分かったこと (@kenmaro)

コメント

筆者がプログラマブルブートストラップを実装しようとしたときに、 色々と工夫したことを備忘録的にまとめています。
ZAMA AIなどが実装するライブラリーを読み解く時にも有益です。

###　- cuHE: A Homomorphic Encryption Accelerator Library (Worcester Polytechnic Institute: Weiさん)

コメント

GPUを用いた高速化の実装について詳しく解説をしている論文。

実際にGPUがどの部分を高速化しているのかまた実装の詳細についても理解できます。
しかし前提知識としていろいろな演算の高速化手法も知っている必要があるので、 今回はオプションにしました。
この辺を全て理解しようとするとなかなか膨大な量になっていきますので、、。

まとめ

今回は、

ある意味とっつきにくいクリプト分野の技術、

格子暗号による秘密計算について

技術的にキャッチアップするための必要なマテリアルについてまとめてみました。

これに沿えば必ず理解できるというわけでは無いかもしれませんが、
必ず着実な理解が深まるものと思っています。
もし興味のある方がいらっしゃいましたらぜひお試しください。

今回はこの辺で。

kenmaro