# 前文

採点は加点式, かつ部分点が存在します. 原則的に文字数制限はありません. ただし, 意味的に同一の内容であればより短いものを高得点とする場合があります. 長過ぎることによる減点はありません. 
フォームの文字数制限を超える場合はフォームに記載した情報が閲覧のための必要十分条件となるような手段であればどのような手段で提出しても構いません. (URLを知っている人間だけが閲覧できる手段でURLをフォームに記載するなど, GitHub Gistや個人のホームページやGoogle Docsなどの事例が有りました)
最低限解くべき課題は調査課題1問(課題1), プログラミング課題1問(課題2.1・課題2.2・課題2.3のいずれか)の構成です. 問題文が長いですが, 誤解がないように可能な限りの注意を払ったこと, 最小限の回答をする際に不必要な苦労をすることがないように配慮したことが要因と考えており, 必ずしも回答の難易度とは相関しません. 
もし誤記や不明瞭な部分がある場合, 事務局に連絡, 講師のTwitter等に連絡をして修正を求めることの他, どのような解釈をしたかを付記してそれに基づいた回答を行うことを認めます.

# 課題１

準同型暗号は未だ発展途上の分野であり, まとまった文献が少ないのが現状です. そのため, 全体像を把握するためには様々な断片的情報をつなぎ合わせる必要があります. この課題はあなたの意欲と調査力を問う課題です. 
準同型暗号につい, てあなたの知るところを述べなさい. ただし, その際に以下の指示を満たしなさい. 

・Garbled Circuit, 秘密分散を用いたもの(Secure Multi Party Computation), TEE(Trusted Execution Environment), 差分プライバシー(Differential Privacy), 分散学習(Fedearted Learning)など(ここでいう"など"は具体的に上げていないものでも良いことを明示的に示す)の１つ以上のセキュアに計算処理を実行する準同型暗号以外の仕組み(一般に秘密計算, 秘匿計算, Secure Computation, Privacy-Preserving Computationなどと呼ばれるますが, その定義に厳密にそう必要はありません)に比べて, 準同型暗号が持つメリットとデメリットを述べなさい. 
・準同型暗号を用いた具体的なアプリケーションとして考えられるものにはどのようなものが考えられますか. 1つ以上上げてください. また, 上の項目で比較した対象では同様のアプリケーションは実現可能かどうか, 可能であるなら有利不利を比較してください. 既存のものを調べても良いですし自分の独自のものを検討しても構いません. ここであげるアプリケーションの実用性は評価の上では重要な項目ではなく, 調査能力と検討能力を主な対象とします.

完全な回答でない場合でも採点において考慮することがあります. また, 上記の指示を満たす限りあなたの興味のままに調べた内容を書いてください. 興味が在るが理解できなかったことはその旨を記述するだけでも結構です. 余計なことを書いて減点されることはありません. 引用は可能な限り明記してください. もし数式の記述や引用の上でそれが望ましい場合LaTeXの標準的な記法を用いることを認めます. 

調査する取っ掛かりになるであろうワード, 文献や実装を以下に並べます. あくまで参考であり, これらの全ての文献やワードについて説明ないし触れる必要はなく, またこれらの文献を全く引かなくても問題ありません. 
加法準同型暗号(Additively Homomoephic Encryption), 乗法準同型暗号(Multiplicatively Homomorphic Encryption), 部分準同型暗号(Partial Homomorphic Encryption), LHE(Leveled Homomorphic Encryption), 完全準同型暗号(Fully Homomorphic Encryption), Paillier暗号, RSA暗号, ElGamal暗号, BFV(Brakerski/Fan-Vercauteren), BGV(Brakerski-Gentry-Vaikuntanathan), CKKS(Cheon-Kim-Kim-Song), GSW(Gentry-Sahai-Waters), TFHE(Torus Fully Homomorphic Encryption), 格子暗号(lattice encryption), LWE(Learning With Error), LWR(Learning With Rounding), NTRU, SVP(Short Vector Problem)
Intel SGX, AMD SEV, Intel TME, ARM Trustzone, RISC-V Keystone, Hopper Confidential Computing
クラウドを支えるこれからの暗号技術　第１３章　光成滋生・著　秀和システム・出版(https://herumi.github.io/ango/)
耐量子計算機暗号 3.3章 格子を用いた高機能暗号 (GSW方式の簡易な解説) 縫田 光司・著 森北出版(https://www.morikita.co.jp/books/mid/087211)
https://eprint.iacr.org/2018/421
https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf
https://eprint.iacr.org/2011/277
https://github.com/shaih/HElib
https://github.com/Microsoft/SEAL
https://github.com/tuneinsight/lattigo
https://github.com/virtualsecureplatform/kvsp
https://github.com/CEA-LIST/Cingulata
https://tfhe.github.io/tfhe/
https://github.com/zama-ai/concrete
https://github.com/zama-ai/tfhe-rs
https://qiita.com/kenmaro/items/416657efca2ff296169b
https://qiita.com/Cliffford/items/2f155f40a1c3eec288cf
https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions
https://www.slideshare.net/suzaki/3teeintel-sgx-arm-trustzone-riscv-keystone
https://eprint.iacr.org/2022/074
http://qliphoth.io/seccamp/
https://web.eecs.umich.edu/~cpeikert/pubs/lattice-survey.pdf

# 課題２

この課題はあなたの基礎的なプログラミング能力を見るためのものです. 採点基準は以下の4点です. 一言で言うと, 理解度,  計算量, 課題の正答数の順で評価します. 
・コードやコメントから背景となるアルゴリズム及びプログラミング全般に対する理解度が読み取れるものはそうでないものよりも高い得点をつけます.コード自体がコピーであったとしても, 出典が明記されており, かつそのアルゴリズムを理解していることがコメントから読み取れる場合は, 同等の理解度で同じアルゴリズムを独自実装した場合に準ずる評価とします. すなわち, コメントが適切であれば独自コードとコピーしてきたコードが同一評価である場合が存在します. 
・アルゴリズムへの理解度が同等な場合は, 原則的に, 計算量が少ない実装に対して高い得点をつけます. ここでいうアルゴリズムへの理解度は講師の考える最適なアルゴリズムにどれだけ近いかということではなく, 実際に提出したアルゴリズムを説明することができるかということです. つまり, 何処からか引っ張ってきた内容を理解していない実装よりも, 低速でも説明のしっかりとしたものに高い点をつける場合があります. 
・実装がどれだけナイーブなものであっても求める要件をたしているものを正答とみなします. すなわち, 動く実装が正答です. その定義のもと正答数を高評価とします.講師の意図としては複数応募等の場合を想定して負荷を下げるために1つ以上で良いという要件を過去設けていましたが, 加点方式をとっている以上課題の回答数が最終評価に対する相関が強く見られるためこれを今年度は明示することとします. 

例年独自実装か否か, ということを評価基準に入れていましたが, 理解度を見れれば独自コードでなくて良い, という明記以上の意味がなかったため理解度の項目にマージしました. 

以下の３つの課題（課題2.1・課題2.2・課題2.3）のうち, 1つ以上に回答しなさい. 
いずれの課題もTFHEの実装に必要な要素を切り出したものであり, 課題のための課題ではないことを明記しておきます. 
課題2.1はTFHEの実装上最も計算量的チューニングの効果が大きい部分を切り出しています.
課題2.2は講師が最初に実装した際も過去の受講生もつまり気味だったところを切り出して簡易にしたものです.
課題2.3は例年は講義の一番最初に教える内容を切り出したものです.

提出するプログラムは以下の条件を満たすようにしてください. 
・原則的には別途提供されるコードの該当コメント部分を書き換えて製作すること. ただし, 該当コメント部分以外の部分の同じファイル内に該当コメント部分で使用する関数を定義することやincludeやimport文を追加するなどは認められる. 
・言語はC,C++,Rust,Pythonのいずれかであることを想定するが, その他のものでもよい. ただし, 課題2.1,2.2に関しては標準入出力から見て同様の挙動をすること. 
・ライブラリはネットで無償で入手可能または添付によってこちらに提出できるものであれば好きなものを用いて構いません. 
・課題2.1,2.2のチェック用の入力と出力の組及びテスト用のシェルスクリプトはコードとともに別途提供します. 
・少なくとも１ヶ月後の自分が理解するのに十分と考える程度のコメントをつけること. 
・計算量やコード量の削減などで特別な工夫を施した場合はそのことがわかるようにコメントをつけてください. ただし, 数式を書きたい場合など必要な場合はコメントではなく別ファイルで記述しても構いません. その場合はどの部分について述べているか対応がわかるようにしてください. 
・プログラムが完成しなかった場合は, その場所にどのような処理を書けばいいか, あるいはプログラムのどの行が誤っていると思われるかをコメントで書くと採点で考慮することがあります. 
・こちらでも実行可能になるように配慮してください. 
・ChatGPTやClaude 3などのLLMを使用しても構いません. ただし, 使用したLLMの名前(ChatGPT 4など)と生成に使用したプロンプトもコードの一部とみなして記載してください. プロンプトに関しては本人の理解度を見るための情報でありLLMの出力結果の再現性は求めません. 

## 課題2.1

この課題では, 整数係数多項式の剰余環上での乗算を実装してもらいます. 剰余演算とは, 割った余りを求める操作のことです. ただし, 法, つまり割る側となる多項式はnを自然数としてXⁿ+1のかたちに限られるものとします. 
具体例として以下の式を与えます. 
(3X-1)⋅(-X+1) = -3X²+4X-1 ≡ 4X-2 mod X²+1
(2X³+5X²-3X+1)⋅(8X³-6X²+X-4) = 16X⁶+28X⁵-52X⁴+23X³-29X²+13X-4 ≡ 23X³-45X²-15X+48 mod X⁴+1

今, n=1024とし, 入力として多項式の係数をn要素の32bit符号付き整数(int32_t)配列として表現したものが2つ与えられるものとします. 配列のi番目の要素は多項式のi次の係数です. 出力となる多項式をn要素の64bit符号付き整数の配列として返す関数を実装しなさい. ただし, 出力となる多項式の係数がオーバーフローを起こさないように入力の係数の大きさが制限されていることは保証されているものとします. 

下記のものはヒントです. 
・法となる多項式がXⁿ+1のかたちに限られていることを利用した最適化を施すことができます. 
・想定回答(最小計算量というわけではない)は数行に収まる程度のものです. 
・知る限り最も少ない計算量を達成できるのは高速フーリエ変換(FFT)か数論変換(NTT)を用いたものです. 参考としてそのような実装を提出する応募者は例年見られること, 及びそのような実装をしていることが最低要件ではない(あくまで理解度が優先)ことを明記します. 
・余談ともいえますが, この課題で挙げた例でX=10にしてみると, 実は整数の剰余は多項式の剰余の特殊な場合と考えることもできます. 

## 課題2.2

この課題では, Pを法とする剰余環上の符号なし整数を, 複数桁のPより小さい基数p(簡単のためpはPを割り切るとします)の符号付き整数に分解する操作(Decomposition)を実装してもらいます. この分解をもう少し詳しく述べると, 分解元の数は[0,P)の範囲の整数で, 分解結果はP/p桁(個)の[-p/2,p/2)の範囲に値を取る符号付きの数です. 簡単のために, この課題ではこれ以降, ある0でない非負整数lを用いて, P=2⁴ˡ, p=16と限定します. 変換先の各桁は[-16/2,16/2)つまり, {-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7}のいずれかの値を取るものとします. 
具体例を考えます. l=1の場合を考えると分解元の法はP=2⁴=16でこれは単に剰余環上の符号の取り直しなので, →で分解を表すとすると, 
15→-1
3→3
となります. 
l=2の場合は, 分解元の法はP=256となり, 1桁目が最初の要素, 2桁目が2つ目の要素となるような組で分解後の各桁が表されるとして, 
232→(-8,-1)
31→(-1,2)
となります. 232の例では, -8-1*16= -24 ≡ 232(mod 256)であり, 31の例では-1+2*16=31となっているので正しい結果となっています. 

今, l=4とし, 入力として16bitの符号なし整数(uint16_t)が入力として与えられるものとします. 今説明したような変換の出力を, 1桁目が最初の要素, 2桁目が2つ目の要素となるような4要素の8bit符号付き整数(int8_t)の配列として返す関数を実装しなさい. 

下記のものはヒントです. 
・分解先の桁の範囲で8を含まず-8を含むのは2の補数表現ではこちらが扱いやすいためです. 
・ナイーブには一番上の桁から決めるのが簡単でしょう. 
・16進数への基数変換をして, それから符号付きに直すというアプローチもあります. 
・講師の知る限り最も効率的な実装ではbitmaskが出てきます. 
・配列の要素の順番を指定しています. 順番は逆になっていたりしませんか. 
・デバッグとしては分解した結果がちゃんと元に戻せるかチェックしてみるのもよいでしょう. 

## 課題2.3

**この課題は例年上の課題で甲乙つけ難い場合があり, 課題3を考慮に入れるケースが想定以上に多かったために新設した課題です. 回答が講師の期待する受講生に求めるレベルを上回る可能性が有ります. ** 
また, 課題2.3だけ回答するケースより課題2.1,2.2の両方を回答している場合のほうが採点基準に基づくと高い評価になりやすいと出題時点では想定しています. 

この課題では実際に格子暗号の一つであるLearning With Errors (LWE)を実装し, その加法準同型性を確認してもらいます. 
この課題ではテンプレートは提供されません. 与えられた仕様を満たしているかのテストを書くことも含め評価の対象とします. 採点の容易性の確保のために可能な限り一つのファイルに記述してください. 
LWEについてはこの課題中で定義し, 必ずしも一般のものをサポートすることは要求しないものとします.

### セキュリティパラメータ

セキュリティパラメータとはその暗号文の安全性を決める値であり,理論上は文字で表現されますが実装においては具体的な数値を決める必要があるものです.
この課題では n=512,q=2¹⁶,η=40 を定義します. 

### 使用する確率分布の定義

この課題で扱うLWEでは離散一様分布とCentered Binomial Distribution (CBD)の２つを利用します. 
離散一様分布とは与えられた区間の整数値(あるいは整数値と同等とみなせる離散的な対象)から等確率に値を選んで返す場合の分布です. 
Binomial Distributionは日本語で言えば二項分布であり, 確率pで表が出るコインをη回投げた時表が出た回数を返すような分布です. すなわち, aᵢをi回目のコイン投げで表が出た時1,裏が出た時0となる値とし, iは0からη-1までの値を取るとすると二項分布は∑aᵢと表現できます. 
CBDは二項分布の減算を行うことで平均値を0に(Centered)した分布です. すなわち同じ確率pで表が出るコインをもう一枚用意して各試行では２枚のコインを同時に投げることとします.１枚目のコインが表の時1,裏の時0になる値をaᵢ,２枚めのコインが表の時1, 裏の時0になる値をbᵢとします. 
CBDは∑(aᵢ-bᵢ)と表現できます. 
この課題ではp=0.5に固定するため, 0または1の一様分布から2η回サンプルすることでCBDからのサンプルを計算できます.

### LWEの定義
ℤ_qは整数全体をℤとしてℤ mod qによって定義される剰余環上の値の集合です.
𝔹は0または1,つまりバイナリの集合です
𝐚∈(ℤ_q)ⁿはnonce(暗号文ごとに異なる使い捨ての値)であり, n個の0からq-1までの閉区間上の一様分布からサンプルされた整数値を係数とするn次元ベクトルとします. 
𝐬∈𝔹ⁿは秘密鍵であり, n個の0または1の一様分布からサンプルされたn次元ベクトルとします.これは複数の暗号文の間で共通です.
e∈ℤ_qはエラーであり, ηをパラメータとするCBDからサンプルされます.
m∈𝔹は平文であり, これは暗号化への入力として任意に決めるものとします.

#### LWEの暗号化

暗号化は平文m, セキュリティパラメータn,q,ηと秘密鍵𝐬を受け取ります.
b∈ℤ_qであり, b = 𝐚⋅𝐬 + e + m⋅(q/2) mod q とする. 
(𝐚,b)が暗号文であり, これを返します.

#### LWEの復号

(𝐚,b)と秘密鍵𝐬を受け取ります.
b - 𝐚⋅𝐬 mod q = e + m⋅(q/2)
を計算します. eは-ηからηの値しか取らないため, 最上位bitを抜き出すことによってmを復元することができます.
復元されたmを返します.

#### LWEの加法準同型性

同じ秘密鍵𝐬を用いて異なる平文m₁,m₂を暗号化した暗号文(𝐚₁,b₁),(𝐚₂,b₂)に対して(𝐚₃,b₃) = (𝐚₁+𝐚₂,b₁+b₂)を計算します.
(𝐚₃,b₃)を復号するとm₁とm₂をXOR(法2の上での加算)した値を得ることができます. 
エラーも加算されますが今回のηの大きさでは2つ足した程度では最上位bitの値は変わりません.

### 実装として求めるもの

- 暗号化, 復号, 暗号化した暗号文が正しく復号できることを確認するテストを実装しそのテストを通ること.
- 自分の実装で暗号化した暗号文同士を加算した後復号し, 実際にXORが計算できることを確認するテストを実装しそのテストを通ること. 

ただし, 最初に述べたように適切に引用・解説されたコピー実装は独自実装に準ずることを再度明記する.

### ヒントやコメント
- 一般に実用に供されるプログラミング言語では一様分布は標準ライブラリとして提供されています.
- もし本当に特殊な言語を使っている場合Linuxの/dev/urandomなどの一様分布からのサンプルを提供するためのOSが提供する仕組みが利用すると良いでしょう. 
- Binomial Distribtuionは実装がないかもしれませんが一様分布があれば実装は容易です.
- mod qとしていますが, Cやnumpyのuint16_tのような型であればoverflowとして自動的に捨てられるのでmod演算をせずに済みます. 
- 一様分布からのサンプルを生成する際は適切なシード値を利用したCryptographically Secure Pseudo Random Number Generatorを利用するとより良いです. ただし加点式のためメルセンヌ・ツイスタなどを用いても減点はされません. 
- メルセンヌ・ツイスタを使うよりは遅くともすべて/dev/urandomからサンプルするほうが高い評価をつけます.これは乱数の質はセキュリティに影響を与えるためです.
- 余談ですが一般にはCBD以外にDiscrete Gaussian Distribution, Rounded Gaussian Distribution, 一様分布などをエラーに使う場合も有ります.

# 課題３

あなたが書き足りなかったことや, 過去に自分で作ったものや本ゼミに関連しそうな知識や経験などのアピールしたいことを自由に記述しなさい. 特にない場合は未回答でも構いませんが, 課題1及び課題2では差がつかない場合この項目によって合否が決まることがあることを明記します. 
また, おそらくないとは思いますが, 講師との個人的な親交などの利益相反を原則的に防ぐために課題1及び課題2より課題3の評価が優先されることはありません.