Paillier暗号（加法準同型暗号）の解説

はじめに

Paillier(パイエ)暗号とは，1998年にPascal Paillierが発表した公開鍵暗号方式です．
暗号化したまま復号することなく平文の加算が行えるという特徴をもつ暗号方式の一種です．
このような性質をもつ暗号系を加法準同型暗号と呼びます．

目次

1. 鍵生成
2. 暗号化
3. 復号
4. 加法準同型性
5. 参考文献

鍵生成

アルゴリズム

暗号化に用いる公開鍵と復号に用いる秘密鍵のペアを以下の様に生成します.

• 同じビット長の大きな素数$p \neq q$をランダムに生成します.
• $N := p \cdot q$を公開鍵とします.
• $p-1$と$q-1$の最小公倍数$\mu$を秘密鍵とします.

秘密鍵$\mu = \mathrm{lcm}(p-1,q-1)$は, $N=pq$と互いに素であること, すなわち$\mu \in(\mathbb{Z}/N\mathbb{Z})^\times$であることが確かめられます.
$(p-1)(q-1)$と$pq$が互いに素であることを示せば十分なので, そうでないと仮定します.
すると, $(p-1)(q-1)$は$p$かまたは, $q$を素因数に持ちます.
今, $p | (p-1)(q-1)$とすると, $\gcd(p,p-1)=1$なので, $p|(q-1)$となります.
しかし, $p$と$q$のビット長が同じことから, $q-1 < 2p$であり, $p \neq q-1$なので, $q-1$は$p$の倍数ではありえません.
同様に$q|(p-1)(q-1)$としても矛盾が生じるので, $(p-1)(q-1)$と$pq$は互いに素です.
よって, 秘密鍵$\mu = \mathrm{lcm}(p-1,q-1)$も公開鍵$N=pq$と互いに素になります.

実装例

鍵生成のSageMathを用いた実装は以下の様になります.

鍵生成

def key_gen(bit_length):
    upper_bound = 2^(bit_length)
    lowwer_bound = upper_bound/2
    while True:
        p = random_prime(upper_bound,False,lowwer_bound)
        q = random_prime(upper_bound,False,lowwer_bound)
        if p != q:
            break
    pk = p*q
    sk = lcm(p-1,q-1)
    return pk,sk

素数$p,q$のビット長を引数として, $N=pq, \mu=\mathrm{lcm}(p-1,q-1)$を返します.

暗号化

アルゴリズム

平文$m \in \mathbb{Z}/N\mathbb{Z}$を以下の手順で暗号化します.

• ランダムに, $r \in (\mathbb{Z}/N\mathbb{Z})^\times$を生成します.
• 暗号文$c := (1+N)^m r^N \bmod{N^2}$を計算します.

ここで, $c \in (\mathbb{Z}/N^2\mathbb{Z})^\times$であることが確かめられます.
まず, $(1+N)$について, 二項定理より,

    (1 + N)^N = 1 + N\cdot N + {N \choose 2}N^2 + \cdots + \equiv 1 \pmod{N^2}

よって, $(1 + N) \in (\mathbb{Z}/N^2\mathbb{Z})^\times$となり, $(1 + N)^m \in (\mathbb{Z}/N^2\mathbb{Z})^\times$が分かります.
次に, 乱数$r$について, $r \in (\mathbb{Z}/N\mathbb{Z})^\times$なので, $\bmod N$の逆元$r'$によって, $r r' \equiv 1 \pmod{N}$と出来ます.
よって, 整数$k$によって$rr' = 1 + kN$と書けるので, 再び二項定理より,

    (rr')^N = (1+kN)^N = 1 + N \cdot kN + {N \choose 2}N^2 \equiv 1 \pmod{N^2}

よって, $r \in (\mathbb{Z}/N^2\mathbb{Z})^\times$となります.
以上から, 暗号文$c$は$(\mathbb{Z}/N^2\mathbb{Z})^\times$の元であることが分かります.

実装例

暗号化のSageMathを用いた実装は以下の様になります.

暗号化

def enc(pk,m):
    r = IntegerModRing(pk).random_element()
    while gcd(ZZ(r),pk) != 1:
            r = IntegerModRing(pk).random_element()
    return Mod((1+pk)^m * ZZ(r)^pk, pk^2)

公開鍵$pk=N$と平文$m$を引数として, 暗号文$c$を返します.

復号

アルゴリズム

暗号文$c \in (\mathbb{Z}/N^2\mathbb{Z})^\times $を以下の手順で復号します.

• $c^\mu - 1 \equiv N u \pmod{N^2}$となるような整数$u$を計算します.
• $m' := \mu^{-1} u \bmod{N}$を計算します.

正当性

$c^\mu$の計算によって,

    c^\mu \equiv (1+N)^{m\mu} r^{N\mu} \pmod{N^2}

となります. 実は$r^{N\mu} \equiv 1 \pmod{N^2}$であることが分かります.
$p^2,q^2$は互いに素なので, 中国剰余定理から環の同型$\mathbb{Z}/N^2\mathbb{Z} \simeq \mathbb{Z}/p^2\mathbb{Z} \times \mathbb{Z}/q^2\mathbb{Z}$が得られます.
よって, 単元群についての群同型

    (\mathbb{Z}/N^2\mathbb{Z})^\times \simeq (\mathbb{Z}/p^2\mathbb{Z})^\times \times (\mathbb{Z}/q^2\mathbb{Z})^\times

が成立します.
ここで, 乱数$r \in (\mathbb{Z}/N^2\mathbb{Z})^\times$の同型での移り先を$(r_p,r_q)$とすると, $\phi(p^2) = p^2 - p = p(p-1) $なので, $r_p^{p(p-1)} \equiv 1 \pmod{p^2}$です（ここで, $\phi$はオイラーのトーシェント関数です）.
同様に, $r_q^{q(q-1)} \equiv 1 \pmod{q^2}$となることがわかるので, $(r_p,r_q)^{N\mu} = (1,1)$です.
よって, $r^{N\mu}$となり, $c^\mu \equiv (1+N)^{m\mu} \pmod{N^2} $となります.
二項定理より,

    (1+N)^{m\mu} = 1 + m \mu N + {m \mu \choose 2} N^2 + \cdots + \equiv 1 + m \mu N \pmod{N^2}

となるので, $c^{\mu} -1 \equiv m \mu N \pmod{N^2}$となります.
よって, $u := \frac{c^{\mu} -1}{N} \equiv m \mu \pmod{N}$です.
秘密鍵$\mu$は, $\bmod{N}$で可逆であったので, $u$に$\mu^{-1} \bmod{N}$を掛けると,

    u \mu^{-1} \equiv m \pmod{N}

となり, 平文$m$が復元できます.

実装例

復号のSageMathを用いた実装例です.

復号

def dec(sk,pk,c):
    u = (ZZ(c^sk-1) % pk^2) / pk
    return Mod(u,pk) * Mod(sk,pk)^(-1)

整数としての演算と法$N$での演算を混同しないように実装する必要があります.

鍵生成，暗号化，復号の観察

以下のSageMathコードで鍵生成，暗号化，復号の一連の流れを観察してみましょう.

観察

def test(bit_length):
    pk,sk = key_gen(bit_length)
    print("N = ", pk, ", μ = ", sk)
    m = Integers(pk).random_element()
    print("m = ", m)
    c = enc(pk,m)
    print("c = ", c)
    d = dec(sk,pk,c)
    print("dec(c) = ", d)
    if m == d:
        print("復号成功")

このコードを例えば, ビット長を$10$として実行してみると,

出力

sage: test(10)                                    
N =  558329 , μ =  69600
m =  396019
c =  291312972197
dec(c) =  396019
復号成功

加法準同型性

パイエ暗号の特筆すべき特徴として，暗号化したままデータの加算処理が行えるという性質があります（加法準同型性）．
$c_1,c_2$をそれぞれ平文$m_1,m_2$を公開鍵$N$による暗号文とします.
すなわち,

    c_1 \equiv (1+N)^{m_1} r_1^N \pmod{N^2}, \\
    c_2 \equiv (1+N)^{m_2} r_2^N \pmod{N^2}

この2つの暗号文の積をとってみましょう.

    c_1 c_2 \equiv (1+N)^{m_1+m_2} (r_1 r_2)^N \pmod{N^2}, \\

これは, 平文の和 $m_1 + m_2$ の暗号文とみなせます. 実際, $c_1 c_2$を復号すると, $m_1 + m_2 $となります.
「暗号文の乗算」によって, 「平文の加算」が引き起こされていることに注意しましょう
（ついでに乱数成分$r$は元の暗号文の乱数成分の積になっています）.

以下のコードでパイエ暗号の加法準同型性を確かめてみましょう.

加法準同型性

def test_add(bit_length):
    pk,sk = key_gen(bit_length)
    print("N = ", pk, ", μ = ", sk)
    m1 = Integers(pk).random_element()
    m2 = Integers(pk).random_element()
    print("m1 = ", m1)
    print("m2 = ", m2)
    print("m1+m2 mod N = ", m1+m2)
    c1 = enc(pk,m1); c2 = enc(pk,m2)
    print("c1 = ", c1)
    print("c2 = ", c2)
    c_mult = c1 * c2
    print("c1*c2 mod N^2 = ", c_mult)
    d = dec(sk,pk,c_mult)
    print("dec(c1*c2) = ", d)
    if m1+m2 == d:
        print("復号成功")

$p,q$のビット長を$10$として実行してみると,

出力

sage: test_add(10)                            
N =  491077 , μ =  244838
m1 =  226633
m2 =  388589
m1+m2 mod N =  124145
c1 =  47830091459
c2 =  87749341674
c1*c2 mod N^2 =  174509641559
dec(c1*c2) =  124145
復号成功

暗号文同士の積によって, 平文の加算が引き起こされていることが分かります.

まとめ

• パイエ暗号とその正当性を解説しました．
• SageMathを用いて実装を行いました．
• 加法準同型性について解説しました．

整数の初等的な性質が巧みに用いられていて面白いですね．

参考文献

• Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
• 耐量子計算機暗号，縫田光司[著]