セキュリティ・キャンプ全国大会2023
開発コースL2【暗号のまま計算しようゼミ】応募課題


# 前文

採点は加点式、かつ部分点が存在します。原則的に文字数制限はありません。ただし、意味的に同一の内容であればより短いものを高得点とする場合があります。長過ぎることによる減点はありません。
フォームの文字数制限を超える場合は、フォームに記載した情報が閲覧のための必要十分条件となるような手段であればどのような手段で提出しても構いません。(URLを知っている人間だけが閲覧できる手段でURLをフォームに記載するなど)
最低限解くべき課題は調査課題1問(課題1)、プログラミング課題1問(課題2.1・課題2.2のいずれか)の構成です。問題文が長いように見えますが、誤解がないように可能な限りの注意を払ったのと、最小限の回答をする際に不必要な苦労をすることがないように配慮したことが要因と考えています。

# 課題１

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

・Garbled Circuit、秘密分散を用いたもの、TEE(Trusted Execution Environment)、差分プライバシー、分散学習など(ここでいう"など"は具体的に上げていないものでも良いことを明示的に示す)の１つ以上のセキュアに計算処理を実行する準同型暗号以外の仕組み(一般に秘密計算、秘匿計算、Secure Computationなどと呼ばれるますが、その定義に厳密にそう必要はありません)に比べて、準同型暗号が持つメリットとデメリットを述べなさい。

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

調査する取っ掛かりになるであろうワード、文献や実装を以下に並べます。あくまで参考であり、これらの全ての文献やワードについて説明ないし触れる必要はなく、またこれらの文献を全く引かなくても問題ありません。
加法準同型暗号(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/)
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://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

# 課題２

この課題はあなたの基礎的なプログラミング能力を見るためのものです。採点基準は以下の３点です。一言で言うと、理解度、計算量の順で評価します。
・コードやコメントから理解度が読み取れるものはそうでないものよりも高い得点をつけます。
・アルゴリズムへの理解度が同等な場合は、原則的に、計算量が少ない実装に対して高い得点をつけます。ここでいうアルゴリズムへの理解度は講師の考える最適なアルゴリズムにどれだけ近いかということではなく、実際に提出したアルゴリズムを説明することができるかということです。つまり、何処からか引っ張ってきた内容を理解していない実装よりも、低速でも説明のしっかりとしたものに高い点をつける場合があります。
・ChatGPTなどのLLMを使用しても構いません。ただし、使用したLLMの名前と生成に使用したプロンプトもコードの一部とみなして記載してください。プロンプトに関しては本人の理解度を見るための情報でありLLMの出力結果の再現性は求めません。

以下の２つの課題（課題2.1・課題2.2）のうち、いずれかまたは両方に回答しなさい。
いずれの課題もTFHEの実装に必要な要素を切り出したものであり、課題のための課題ではないことを明記しておきます。

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

## 課題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進数への基数変換をして、それから符号付きに直すというアプローチもあります。
・配列の要素の順番を指定しています。順番は逆になっていたりしませんか。
・デバッグとしては分解した結果がちゃんと元に戻せるかチェックしてみるのもよいでしょう。

# 課題３

あなたが書き足りなかったことや、過去に自分で作ったものや本ゼミに関連しそうな知識や経験などのアピールしたいことを自由に記述しなさい。特にない場合は未回答でも構いません。