この記事は EAGLYS Advent Calendar 2022 の16日目の記事です
符号理論・符号ベース暗号の基本的なことは↓を参照してください
符号ベース暗号に入門する（前半）
符号ベース暗号に入門する（後半）
今回と次回で前回導入した符号ベース暗号方式に準同型暗号のフレームワークを入れてみます
今回はその準備です
参考文献
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符号の性質, 準同型暗号の定義, 既存方式の紹介
イントロダクション
準同型暗号とは大雑把には，暗号文同士の足し算・掛け算ができる暗号方式のことです
＊「できる」というのは，任意の暗号文の組に対して，という意味ですので，暗号文空間内で，暗号文の足し算・掛け算が閉じている，というのが正確です
ここで，符号ベース暗号に入門する（後半）「McElice暗号」 での暗号文の作り方を思い出すと，符号語にノイズを加えたものを暗号文としていました
すると，この場合の暗号文の足し算，というのは，符号語と符号語の和にそれぞれのノイズの和で構成されます
符号語と符号語の和は符号語（符号語は線型空間の元なので）ですので，ノイズの和が小さい範囲（厳密には，符号の誤り訂正能力以下）であれば，それを復号したものは平文の和になっています
＊今回（と次回）の記事では最小距離とか誤り訂正能力は扱いません
＊その辺りまで期待されている方向けには，いずれガッツリ書きます（媒体はQiitaではないかもですが）
と考えると，実は加法準同型性は自明だったりします（なんなら公開鍵暗号方式でもできる）
では，掛け算はどうするか・・・というと，足し算より簡単な話ではなく，「良い感じの」符号を使う必要があります
その「良い感じ」の符号，というのが今回紹介するReed-Muller符号です
＊先に紹介した Armknecht らの論文では，実はもっと抽象的な議論を進めていて，その具体例として Reed-Muller 符号を用いています
ですから，論文紹介ほどがっつりしたものではなく，雰囲気を感じ取れるような内容にします
Qiitaは理論ゴリゴリの記事を書く場所と思っていないし数式書きづらいので・・・
Reed-Muller 符号の定義
$m$ を正整数，$z \in [0, 2^m - 1]$ として，$\mathrm{bin}(z)$ で長さ $m$ での $z$ の2進展開を表すことにします
例えば，$m = 3$ で $\mathrm{bin}(0) = 000, \mathrm{bin}(2) = 010, \mathrm{bin}(5) = 101$ です
また，多項式 $f \in \mathbb{F}_2[x_1, \cdots, x_m]$ をとります
つまり，$f$ とは，$\mathbb{F}_2[x_1, \cdots, x_m]$ 内の多項式，これは，$x_1, \cdots, x_m$ を変数とする $\mathbb{F}_2$ 上の多項式です
例えば $m = 3$ なら，$x_1 + x_2 + x_3, x_1^3 + x_2, x_1 x_2^2 x_3$ などが $\mathbb{F}_2[x_1, x_2, x_3]$ に含まれます
$i \in [1, m]$ で $p_i$ で $f$ の $x_i$ の次数を表すとき，$f \in \mathbb{F}_2[x_1, \cdots, x_m]$ に対して，$\mathrm{Eval} : [0, 2^m - 1] \times \mathbb{F}_2[x_1, \ldots, x_m] \rightarrow$ {$0, 1$} を
\mathrm{Eval}_z(f) =
\begin{cases}
0 \ \exists j \in [1, m] \ \mathrm{s.t.} \ (p_j = 1 \wedge \mathrm{bin}(z)_j = 0) \\
1 \ \mathrm{o.w.}
\end{cases}
と定めます．ただし，$f = 0$ （零多項式）のときは，$\mathrm{Eval}_z(0) = 0$ とします．
例えば，$f = 1$ のときは，全ての変数の次数が0なので，$\mathrm{Eval}_z(1) = 1$ です．
また，$\mathrm{Eval}(f) = $ { $\mathrm{Eval}_0(f), \mathrm{Eval}_1(f), \ldots, \mathrm{Eval}_{2^m - 1}(f)$ } とします
このとき，Reed-Muller 符号 $\mathrm{RM}(m, r)$ とは，{$f \in \mathbb{F}_2[x_1, \ldots, x_m] \ | \ \mathrm{deg}(f) \leq r$} の基底を {$b_1, \ldots, b_N$} としたとき($N = \sum_{i = 0}^r \binom{m}{i}$)，
\begin{pmatrix}
\mathrm{Eval}(b_1) \\
\vdots \\
\mathrm{Eval}(b_N)
\end{pmatrix}
を生成行列とする符号のことです
＊本当は $N$ は $r$ に依存するので，$N_r$ と書いた方がいいのはわかっているんですが，Qiitaで添字の添字を出すのは一苦労で・・・
ここで，$f \in \mathbb{F}_2[x_1, \ldots, x_m]$ に対して，$\mathrm{deg}(f)$ とは，多項式 $f$ を $\sum x_1^{i_1} \cdots x_m^{i^m}$ のように単項式の和に分解した際の $i_1 + \cdots + i_m$ のmaxのことです（零多項式のみ次数を$- \infty$とします）
例えば，$\mathrm{deg}(1) = 0, \mathrm{deg}(x_1 + 1) = 1, \mathrm{deg}(x_1 x_3 + 1) = 2$ です
Reed-Muller 符号の具体例
RM(3, 0)
まず，$\mathrm{RM}(3, 0)$ です
{$f \in \mathbb{F}_2[x_1, x_2, x_3] \ | \ \mathrm{deg}(f) \leq 1$} の基底として，{$1$} をとります
このとき，任意の $z$ に対して，$\mathrm{Eval}_z(1) = 1$ と定めていたので，
\mathrm{Eval}(1)
= \{ \mathrm{Eval}_0(1), \mathrm{Eval}_1(1), \mathrm{Eval}_2(1), \mathrm{Eval}_3(1), \mathrm{Eval}_4(1), \mathrm{Eval}_5(1), \mathrm{Eval}_6(1), \mathrm{Eval}_7(1) \} = \{ 1, 1, 1, 1, 1, 1, 1, 1 \}
です，よって，$\mathrm{RM}(3, 1)$ の生成行列は，
\begin{pmatrix}
\mathrm{Eval}(1)
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
\end{pmatrix}
です
RM(3, 1)
次に，$\mathrm{RM}(3, 1)$ について考えます
{$f \in \mathbb{F}_2[x_1, x_2, x_3] \ | \ \mathrm{deg}(f) \leq 1$} の基底として，{$1, x_1, x_2, x_3$} をとります
$\mathrm{Eval}_{5}(x_1)$ の値を考えてみると，$\mathrm{bin}(5) = 101$ であり，$x_1$ の次数が1で，$x_2, x_3$ の次数は共に0なので，$p_1 = 1, p_2 = 0, p_3 = 0$ です
$p_j = 1$ なる $j \in [1, 3]$ は $j = 1$ だけで，$\mathrm{bin}(5)_1 = 1$ なので，$\mathrm{Eval}_{5}(x_1) = 1$ です
また，$\mathrm{Eval}_{3}(x_1)$ の値を考えてみると，$\mathrm{bin}(3) = 011$ であり，$j = 1$ のとき $\mathrm{bin}(3)_1 = 0$ なので，$\mathrm{Eval}_{3}(x_1) = 0$ です
つまり
\mathrm{Eval}(x_1)
= \{ \mathrm{Eval}_0(x_1), \mathrm{Eval}_1(x_1), \mathrm{Eval}_2(x_1), \mathrm{Eval}_3(x_1), \mathrm{Eval}_4(x_1), \mathrm{Eval}_5(x_1), \mathrm{Eval}_6(x_1), \mathrm{Eval}_7(x_1) \} = \{ 1, 1, 1, 1, 0, 0, 0, 0 \}
となります
同様に
\mathrm{Eval}(x_2) = \{ 1, 1, 0, 0, 1, 1, 0, 0 \} \\
\mathrm{Eval}(x_3) = \{ 1, 0, 1, 0, 1, 0, 1, 0 \} \\
\mathrm{Eval}(1) = \{ 1, 1, 1, 1, 1, 1, 1, 1 \}
を得ます．よって，$\mathrm{RM}(3, 1)$ の生成行列は，
\begin{pmatrix}
\mathrm{Eval}(1) \\
\mathrm{Eval}(x_1) \\
\mathrm{Eval}(x_2) \\
\mathrm{Eval}(x_3)
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0
\end{pmatrix}
です
RM(3, 2)
次に RM(3, 2) についてです
{$f \in \mathbb{F}_2[x_1, x_2, x_3] \ | \ \mathrm{deg}(f) \leq 2$} の基底として，{$1, x_1, x_2, x_3, x_1 x_2, x_1 x_3, x_2 x_3$} をとります
基底の要素のうち，前４つについては既に Eval を考察したので，後ろ3つについてです
$\mathrm{Eval}_{5}(x_1 x_2)$ の値を考えてみると，$x_1, x_2$ の次数が共に1で，$x_3$ の次数は0なので，$p_1 = 1, p_2 = 1, p_3 = 0$ です
$p_j = 1$ なる $j \in [1, 3]$ は $j = 1, 2$ で，$\mathrm{bin}(5)_1 = 1, \mathrm{bin}(5)_2 = 0$ なので，$\mathrm{Eval}_{5}(x_1 x_2) = 0$ です
また，$\mathrm{Eval}_{6}(x_1 x_2)$ の値を考えてみると，$\mathrm{bin}(6) = 110$ であり，$j = 1, 2$ のとき $\mathrm{bin}(6)_1 = 1, \mathrm{bin}(6)_2 = 1$ なので，$\mathrm{Eval}_{6}(x_1 x_2) = 0$ です
つまり
\mathrm{Eval}(x_1 x_2) = \{ 1, 1, 0, 0, 0, 0, 0, 0 \}
となります
同様に
\mathrm{Eval}(x_1 x_3) = \{ 1, 0, 1, 0, 0, 0, 0, 0 \} \\
\mathrm{Eval}(x_2 x_3) = \{ 1, 0, 0, 0, 1, 0, 0, 0 \} \\
を得ます．よって，$\mathrm{RM}(3, 2)$ の生成行列は，
\begin{pmatrix}
\mathrm{Eval}(1) \\
\mathrm{Eval}(x_1) \\
\mathrm{Eval}(x_2) \\
\mathrm{Eval}(x_3) \\
\mathrm{Eval}(x_1 x_2) \\
\mathrm{Eval}(x_1 x_3) \\
\mathrm{Eval}(x_2 x_3)
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
\end{pmatrix}
です
RM(3, 3)
最後に RM(3, 3) です
{$f \in \mathbb{F}_2[x_1, x_2, x_3] \ | \ \mathrm{deg}(f) \leq 3$} の基底として，{$1, x_1, x_2, x_3, x_1 x_2, x_1 x_3, x_2 x_3, x_1 x_2 x_3$} をとります
$\mathrm{Eval}_{5}(x_1 x_2 x_3)$ の値を考えてみると，$x_1, x_2, x_3$ の次数が1なので，$p_1 = 1, p_2 = 1, p_3 = 1$ です
$p_j = 1$ なる $j \in [1, 3]$ は $j = 1, 2, 3$ で，$\mathrm{bin}(5)_1 = 1, \mathrm{bin}(5)_2 = 0, \mathrm{bin}(5)_3 = 0$ なので，$\mathrm{Eval}_{5}(x_1 x_2 x_3) = 0$ です
また，$\mathrm{Eval}_{7}(x_1 x_2)$ の値を考えてみると，$\mathrm{bin}(7) = 111$ であり，$j = 1, 2, 3$ のとき $\mathrm{bin}(7)_1 = 1, \mathrm{bin}(7)_2 = 1, \mathrm{bin}(7)_3 = 1$ なので，$\mathrm{Eval}_{7}(x_1 x_2 x_3) = 1$ です
つまり
\mathrm{Eval}(x_1 x_2 x_3) = \{ 1, 0, 0, 0, 0, 0, 0, 0 \}
となります
よって，$\mathrm{RM}(3, 3)$ の生成行列は，
\begin{pmatrix}
\mathrm{Eval}(1) \\
\mathrm{Eval}(x_1) \\
\mathrm{Eval}(x_2) \\
\mathrm{Eval}(x_3) \\
\mathrm{Eval}(x_1 x_2) \\
\mathrm{Eval}(x_1 x_3) \\
\mathrm{Eval}(x_2 x_3) \\
\mathrm{Eval}(x_1 x_2 x_3)
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\end{pmatrix}
です
Reed-Muller 符号の実装
$\mathrm{RM}(3, 0), \mathrm{RM}(3, 1), \mathrm{RM}(3, 2), \mathrm{RM}(3, 3)$ の符号語を出力するコードを与えます
以下では，$f \in \mathbb{F}_2[x_1, x_2, x_3]$ としたとき，$f$ は0以外の単項式に限るものとします
このとき，$f$ は $x_1, x_2, x_3$ の次数のみで特徴づけられますから，$f$ と次数を表すベクトル $[p_1, p_2, p_3]$ と一対一対応します
＊$f \in${$1, x_1, x_2, x_3, x_1 x_2, x_1 x_3, x_2 x_3, x_1 x_2 x_3$}
次のステップで実装していくことにします
- $z, f$ を与えたときに $\mathrm{Eval}_z(f)$ を構成する
- $\mathrm{Eval}_z(f)$ を用いて，$z$ を動かして $\mathrm{Eval}(f)$ を構成する
- $r$ を動かして，$\mathrm{RM}(m, r)$ の生成行列を構成する
- 生成行列から，符号語全体を出力する
step 1 : $z, f$ を与えたときに $\mathrm{Eval}_z(f)$ を構成する
def eval_z(m : int, z : int, f : list) -> int:
if f == [0 for _ in range(m)]:
return 1
else:
for index in range(m):
if f[index] == 1 and int(bin(z)[2:].zfill(m)[index]) == 0:
return 0
return 1
出力結果
eval_z(3, 0, [0, 0, 0]) = 1
eval_z(3, 5, [0, 0, 0]) = 1
eval_z(3, 5, [1, 0, 0]) = 1
eval_z(3, 3, [1, 0, 0]) = 0
eval_z(3, 5, [1, 1, 0]) = 0
eval_z(3, 6, [1, 1, 0]) = 1
eval_z(3, 5, [1, 1, 1]) = 0
eval_z(3, 7, [1, 1, 1]) = 1
step 2 : $\mathrm{Eval}_z(f)$ を用いて，$z$ を動かして $\mathrm{Eval}(f)$ を構成する
def eval(m : int, f : list) -> list:
eval_vec = []
for z in reversed(range(pow(2, m))):
eval_vec.append(eval_z(m, z, f))
return eval_vec
出力結果
eval(3, [0, 0, 0]) = [1, 1, 1, 1, 1, 1, 1, 1]
eval(3, [1, 0, 0]) = [1, 1, 1, 1, 0, 0, 0, 0]
eval(3, [0, 1, 0]) = [1, 1, 0, 0, 1, 1, 0, 0]
eval(3, [0, 0, 1]) = [1, 0, 1, 0, 1, 0, 1, 0]
step 3 : $r$ を動かして，$\mathrm{RM}(m, r)$ の生成行列を構成する
def make_RM_code_generator_matrix(m : int, r : int) -> list:
generator_matrix = []
for deg in range(r + 1):
for f_deg_list in list(itertools.combinations([i for i in range(m)], deg)):
f = [0 for _ in range(m)]
for f_deg_index in f_deg_list:
f[f_deg_index] = 1
generator_matrix.append(eval(m, f))
return generator_matrix
出力結果
make_RM_code_generator_matrix(3, 0) = [[1, 1, 1, 1, 1, 1, 1, 1]]
make_RM_code_generator_matrix(3, 1) = [[1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 0, 0, 1, 1, 0, 0], [1, 0, 1, 0, 1, 0, 1, 0]]
make_RM_code_generator_matrix(3, 2) = [[1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 0, 0, 1, 1, 0, 0], [1, 0, 1, 0, 1, 0, 1, 0], [1, 1, 0, 0, 0, 0, 0, 0], [1, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 1, 0, 0, 0]]
make_RM_code_generator_matrix(3, 3) = [[1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 0, 0, 1, 1, 0, 0], [1, 0, 1, 0, 1, 0, 1, 0], [1, 1, 0, 0, 0, 0, 0, 0], [1, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 1, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0]]
step 4 : 生成行列から，符号語全体を出力する
def make_RM_code(m : int, r : int) -> list:
RM_code = []
generator_matrix = make_RM_code_generator_matrix(m, r)
RM_code_dim = len(generator_matrix)
for index in range(pow(2, RM_code_dim)):
codeword = list(np.dot(np.array([int(b) for b in list(bin(index)[2:].zfill(RM_code_dim))]), np.array(generator_matrix)))
for index in range(len(codeword)):
codeword[index] %= 2
RM_code.append(codeword)
return RM_code
まとめ
今回は，Reed-Muller符号の説明で終わってしまいました
次回はいよいよReed-Muller符号を使って，符号ベースでの準同型暗号を構成します
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！