この記事は 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符号を使って，符号ベースでの準同型暗号を構成します

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