この記事は EAGLYS Advent Calendar 2022 の23日目の記事です

符号理論・符号ベース暗号の基本的なことは↓を参照してください
符号ベース暗号に入門する（前半）
符号ベース暗号に入門する（後半）

前回の続きからです前回
前回紹介した Reed-Muller 符号を使って，符号ベース暗号を用いた準同型暗号を構成します

参考文献
F. Armknecht, D. Augot, L. Perret, A. Sadeghi: ”On constructing homomorphic encryption schemes from coding theory”, In: IMA International Conference on Cryptography and Coding. Springer, Berlin, Heidelberg, pp. 23-40, 2011.
ePrint版

＊今回のテーマは↑以外にほとんど文献を知らない（し↑は今回の原論文）のですが，ご存知の方いらっしゃいますか・・・？

連載記事の構成

今回のアドカレの関連記事（気になるところから読んでください）

符号ベース暗号の概要
２日目（符号ベース暗号に入門する（前半））：符号ベース暗号の概要, 符号理論の概要
９日目（符号ベース暗号に入門する（後半））：シンドローム復号問題, McEliece暗号, Information Set Decoding アルゴリズム

符号ベース暗号を用いた準同型暗号の構成
16日目（符号ベース暗号を用いた準同型暗号の構成（前半））：Reed-Muller符号の定義, 具体例, 実装
23日目（イマココ）（符号ベース暗号を用いた準同型暗号の構成（後半））：Reed-Muller符号の性質, 準同型暗号の定義, 既存方式の紹介

準同型暗号

今回扱うのは，共通鍵暗号ベースの準同型暗号です

つまり，

$M$ : 平文空間（体）
$K$ : 鍵空間
$C$ : 暗号文空間（体）

として，暗号化関数を $\mathrm{Enc} : M \times K \rightarrow C$ とすると，任意の平文 $m, m^{\prime} \in M$ に対して，

\mathrm{Enc}(m + m^{\prime}, k) = \mathrm{Enc}(m, k) + \mathrm{Enc}(m^{\prime}, k) \\
\mathrm{Enc}(m \cdot m^{\prime}, k) = \mathrm{Enc}(m, k) \cdot \mathrm{Enc}(m^{\prime}, k)

が成り立ちます

前回のイントロでも触れたとおりで，符号ベース暗号であれば，加法（足し算の）準同型性が成り立つのはほぼ明らかです

ですが，暗号文の（符号語の）掛け算を行うのが難しい・・・というので，掛け算が成り立つような「良い感じ」の符号ということで，前回はずっとReed-Muller符号を紹介していました

Reed-Muller 符号の性質

まず初めに思い返していただきたいこととして，符号語の和は $\mathbb{F}_2^n$ 上の和として定まるのでした

とすると，符号語の積というのは，$\mathbb{F}_2^n$ 上の積，つまり，$u = (u_1, \cdots, u_m), v = (v_1, \cdots, v_m)$ に対して，$u \cdot v = (u_1 \cdot v_1, \cdots, u_m \cdot v_m)$ と定めるのが自然ではないでしょうか（wedge積などと呼ばれる積）

そして，前回の記事より $\mathrm{Eval}(x_1 \cdot x_2) = \mathrm{Eval}(x_1) \cdot \mathrm{Eval}(x_2)$ でした（$x_1 x_2$ は多項式の積で，右辺の積は↑の意味の積）から，Reed-Muller符号の符号語は↑の性質を満たしていそうな気がします

実際にReed-Muller符号が上記の条件を満たすかを確認すると，「条件付きで」Reed-Muller符号の任意の符号語の組に対して，この性質が成り立っています

条件付きとは，次の２つのいずれかの条件を満たすことです:

$\mathrm{RM}(m, m)$ で考えて，FHE（Fully Homomorphic Encryption）にする
LHE（Leveled Homomorphic Encryption）にして，符号の範囲を徐々に広げる

2の方針が論文中には記載されていますが，１の方がイメージしやすそうなので，1で進めます

提案方式

真面目に定義はしないので，そのあたりは論文をご確認ください

次の5つの多項式時間アルゴリズム (Setup, Enc, Dec, Add, Mult) で構成されます

Setup : セキュリティパラメタを受け取って，$\mathrm{RM}(m, m)$ を返す
Enc : $\mathrm{RM}(m, m)$ を用いて，平文を暗号化
Dec : 暗号文を復号（詳細は略）
Add : 暗号文同士の足し算
Mult : 暗号文同士の掛け算

＊Decをしっかりやらないといけないのはわかっていますが，今回は雰囲気だけ掴むということで省略しています（そもそも今回は最小距離とかを飛ばしましたし，どこかのタイミングで詳しいことは書くつもりですので・・・）

Encのやり方は符号ベース暗号に入門する（後半）と同じ感じです

ちなみに論文中の方式の性能ですが，128 security level だとSetupに1時間19分前後かかる一方で，暗号文や鍵サイズはそこそこですので，結構使い物になりそうな香りがするし，ここを改善するだけで学会で発表できそうですよね()

提案方式の具体例を見たいのですが，↓の理由で飛ばします

提案方式の欠点

$|\mathrm{RM}(m, m)| = 2^{2^m}$ ですので，$m = 4$ でも $|\mathrm{RM}(4, 4)| = 2^{16}$ ですので，めちゃめちゃ大きいです

ちなみに，leveled の方で実現しようとすると，符号の範囲を広げるために，何回演算したのかのcounter（論文でいう $\gamma$）が必要になります

ですので，どちらも一長一短があり，上記を回避できるような手段もありそうなのですが，模索中です

今後の課題とかまとめとか

準同型暗号の一般論として，演算の途中で暗号文内のノイズを取り除ける bootstrapという手法があります
今回の場合は完全にノイズを取り除いてしまうと，符号語がそのまま流れてしまうため，ちょっと改善する必要がありそうですが，bootstrapと似たような手法がこちらでもできるかもしれません

提案方式をもっとがっつり書いてほしかったという方もいらっしゃるかもしれませんが，その気持ちはわかります()
今回の話題はほとんど先行研究がない（~~というか時間的な余裕がなかった~~）ため，軽いお気持ち程度にとどめてしまいました

確かに格子とかと比べると性能が悪そうなのはわかりますが，今回ので興味を持った方は是非ご連絡ください！
詳細な内容もいずれ書きますし，改善できそうなところがたくさんありますので，一緒に研究できたらなと！！！

今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！