完全凖同型暗号の実装
中村 蓉子1(指導教員: 金子 晃)

はじめに以下, スキーム E に対して凖同型となる回路の集合を CE と記す.

完全凖同型暗号とは, 任意の論理ゲートあるいは環の多項式演算を, 平文に対してと同様に暗号文だけを用いて実行できるという暗号である.
現在, クラウドコンピューティングが普及し, 自分の情報を相手に知られることなく計算だけ行ってもらうという秘密計算の必要性が高まっている. その秘密計算を行うに当たって完全凖同型暗号は有効な手段になるものであると期待されている.
本研究では, 完全凖同型暗号の仕組みを解説し, そして, その実装を試みる.

24

それ自身の復号回路よりもほんの少しだけ大きな回路を計算することができる回路から, あらゆる深さの回路に対する凖同型暗号を構成する.
定義 3.3 (増強された復号回路) E = (KeyGen, Encrypt, Decrypt, Evaluate) を暗号スキームとせよ.
そこでは復号はセキュリティパラメータのみに依存する回路によって, 実行される.
セキュリティパラメータ λ が与えられたとき, 増強された復号回路の集合は二つの回路からなる. どちらも入力として秘密鍵と, 二つの暗号文をとる. 一つ目の回路は, 二つの暗号文を復号し, 得られた平文を mod2 で加算する. もう一つの回路は, 二つの暗号文を復号し, 得られた平文を mod 2 で乗算する. この集合をDE (λ) と記す.

凖同型暗号とは安全性を満足した最もシンプルな暗号スキームの一つとして, 以下の様な共通鍵暗号スキームが挙げられる.

KeyGen: 鍵 は, η に つ い て 予 め 設 定 さ れ た 区 間[2η−1 , 2η ] からランダムに選ばれた奇数整数 p である.
Encrypt(p, m): ビット m ∈ {0, 1} を暗号化する. 暗号文 c を p の剰余が平文と同じ偶奇性を持つ整数とする. すなわち, c = pq + 2r + m とする. そこでは, 整数 q, r は他の予め設定された区間の中からランダムに選び, 2r が絶対値 p/2 より小さいようにする.
Decrypt(p, c): (c mod p) mod 2 を出力する.

定義 3.4 (ブートストラップ可能な暗号化) E = (KeyGen, Encrypt, Decrypt, Evaluate) を凖同型暗号スキームとせよ. そして, 各セキュリティパラメータ λに対して, CE (λ) を E が適切な回路の集合とせよ.
どんな λ に対しても, DE (λ) ⊆ CE (λ) が成り立つとき, E は “ブートストラップ可能” であるという.

このシンプルなスキームは, 加算と乗算の両方, あるいは, それらを少数組み合わせたゲートで準同型となる. (すなわち, “いくらか凖同型” 性を持つ. ) しかし,深いゲートに対しては, ノイズ（r の累積）が p を超えてしまうため正しく復号できず, 凖同型性が崩れてしまう. すなわち, “完全凖同型” とはなっていない.
また, p を相手に渡すのは実用的ではない. つまり,公開鍵暗号化が望まれる.
Gentry[1] は “いくらか凖同型な暗号” を “完全凖同型暗号” に変換する仕組みを発見し, さらに, Martenvan Dijk, Craig Gentry, Shai Halevi, Vinod Vaikuntanathan[2] が, 完全凖同型性を持つ整数環上の具体的な公開暗号系を提案した.

3

ブートストラップ可能な暗号化定理 3.5 ブートストラップ可能なスキーム E や, パラメータ d = d(λ) が与えられたとき, 次のような別の暗号スキーム E (d) を出力する変換が存在する.

1. E (d) は, コンパクトである. (特に, E (d) の復号回路は, E の復号回路に等しい)
2. E (d) は, d までの深さの全ての回路に対して, 凖同型である.
もし, ブートストラップ可能なスキーム E が “circularsecure” ならば, 一つのコンパクトな完全凖同型暗号ス
キーム E ′ に変換できることが知られている.

凖同型暗号の厳密な定義

5暗号スキームの構成

5.1

いくらか凖同型な暗号スキーム【パラメータ】
γ: 公開鍵のビット長, η: 秘密鍵のビット長
ρ: ノイズのビット長, τ : 公開鍵の個数

定義 3.1 (適切な凖同型復号) スキーム E = (KeyGen, Encrypt, Decrypt, Evaluate) が t 個の入力を持つ与えられた回路 C に対して “適切である”とは, KeyGen(λ) によるどんな鍵のペア (sk,pk)の出力や, どんな t 個の平文ビット m1 , . . . , mt や,ci ← EncryptE (pk, mi ) によるどんな暗号文 ~c =hc1 , . . . , ct i に対しても, Decrypt(sk,Evaluate(pk,C,~c)) = C(m1 , . . . , mt ) が成り立つことである.

正当性の条件から, パラメータの制限がつく. 例えば, 以下のように設定すれば, 条件は満たされる.
ρ = λ, ρ′ = 2 ∗ λ, η = Õ(λ2 ), γ = Õ(λ5 ), τ = γ + λη-bit の正の奇数整数 p から, γ-bit 整数を生成するために次の分布を使う.
RDγ,ρ (p) = {choose q ←− Z ∩ [0, 2γ /p),

定義 3.2 (凖同型暗号) C をある回路のクラスとする.
スキーム E = (KeyGen, Encrypt, Decrypt, Evaluate) は, C ∈ C となる全ての回路で適切であるとき,C に対して “凖同型” であるという. さらに, 全てのboolean 回路に対して適切であるならば, E は “完全凖同型” であるという.

Rr ←− Z∩(−2ρ , 2ρ ) : output x = pq + r}

【構成】
RKeyGen(λ). 秘密鍵は η-bit の奇数整数: p ← (2Z +1) ∩ [2η−1 , 2η ). 公開鍵を生成するために, i = 0, . . . , τRに対して, xi ← Dγ,ρ (p) を行う. そして, x0 が最も大55

きくなるように並べ替える. x0 が奇数で, x0 の p の剰余が偶数にならないならば, やり直す.
公開鍵は pk=hx0 , x1 , . . . , xτ i である.
Encrypt(pk, m ∈ {0, 1}). ランダムな部分集合 S ⊆′′{1, 2, . . . , τ } と, (−2ρ , 2ρ ) 間のランダムな整数 r を選Pぶ. そして, c ← [m + 2r + 2 i∈S xi ]x0 を出力する.
ただし, [a]b = a mod b である.
Evaluate(pk, C, c1 , . . . , ct ). t 個の入力と t 個の暗号
文 ci で, (二進数の) 回路 C ∈ CE が与えられたとき, 暗号文に対して C の加算と乗算ゲートを適用し, 結果の整数を返す.
Decrypt(sk, c). m′ ←(c mod p) mod 2 を出力する.

度が κ ビットとなる 2 以下の正の整数となる. また,P−κ) となる.
i∈S yi = (1/p) − ∆p (|∆p | < 2
秘密鍵 sk=(sk*, ~s) と, 公開鍵 pk=(pk*, ~y) を出力する.
Encrypt and Evaluate. 暗号文 c*を以前と同様に生成する. i ∈ {1, . . . , Θ} に対して, zi ← [c∗ · yi ]とする. それぞれの zi に対して, 2 進の小数点以下の精度の n=⌈log θ⌉ + 3 ビットだけを保存する. c*と~z = hz1 , . . . , zΘ i を出力する.
PDecrypt. m′ ← [c∗ − ⌊ i si zi ⌉]2 を出力する.
定理 4.2.1 E を上記のスキームとせよ. さらに, DE を増強され squash された復号回路の集合とせよ.
その時, DE ⊂ C(PE ) となる.

【正当性】
補題 4.1.1 (sk,pk) を KeyGen(λ) による出力とし, c言い換えると, E は “ブートストラップ可能” である.
定理 3.5 から, どんな深さの回路に対しても凖同型となる暗号スキームを得る.

R←− Encrypt(pk, m) for m ∈ {0, 1} とせよ. そのとき, |2b + m| ≤ τ 2ρ+3 (<< p) となるある整数 a, b に対して, c = a · p + (2b + m) となる.

6

補題 4.1.2 (sk,pk) を KeyGen による出力とし, C ∈CE を t 入力, 1 出力の回路とせよ. また, i ∈ {1,. . . ,gmp(GNU 任意精度計算ライブラリ) を用いた C 言語で実装した. 回路 C は, 最初の演算が乗算で, 残りが加算の回路を用いた. 平文の個数は t=4 とした.

Rt}, mi ∈ {0, 1} のとき, ci ←− Encrypt (pk, mi ) とせよ. さらに, m ← C (m1 , . . . , mt ), c ← Evaluate(pk, C, c1 , . . . , ct ) とせよ. そのとき, |2b + m| < p/8となるある整数 a, b に関して, c = a · p + (2b + m) となる.

【開発環境】以下の二つで実験した.
(1)diamond:Opteron2431 2.4GHz 6 core×2,メモリー 32GB, OS:CentOS 5.3(2)tornado2:AMD Phenom 9950 2.6GHz 4 core,メモリー 8GB, OS:Ubuntu10.04
メモリの減量化に努めた結果, 実行可能な λ の最大値と実行時間 (秒) は以下の様になった.

補題 4.1.3 上のスキームは CE に対して適切である.
補題 4.1.1 と 4.1.2 から補題 4.1.3 が直ちに得られる.
つまり, CE のどんな回路や, その回路への入力のどんな暗号化に対しても, Evaluate による整数の出力は,2b + m ≤ p/8 で c = a · p + (2b + m) の形をしている.
(m は, c に暗号化されると思われる平文であるh i . ) 従って, [c]p = 2b + m となり, ゆえに m = [c]p5.2

完全凖同型暗号スキーム

2

実装とその結果

6.1

いくらか凖同型な暗号スキーム (diamond)【パラメータ】λ = 14 【メモリ使用量】32GB【公開鍵のビット長】537824 【公開鍵の個数】537838【実行時間】[Key]290.99621820,[Enc]2711.85526084,[Eval] 0.00911092,[Dec] 0.00003719

である.

定義 3.4 に従って, “いくらか凖同型な暗号スキーム”からブートストラップ可能な “完全凖同型暗号スキーム” を作る. 復号アルゴリズムを計算することは, “いくらか凖同型な暗号スキーム” が扱えるよりも深いboolean 回路が要求されるからである. 従って, “復号回路の squashing” という変換を用いる. この変換では, 公開鍵に秘密鍵に関するいくつかの付加情報を加える. そして, その付加情報を暗号文の “後処理” のために用いる. 後処理された暗号文は, 元の暗号文よりも効率的に復号できる. こうして, ブートストラップ可能なスキームを作る.

6.2

完全凖同型暗号スキーム (tornado2)配列をディスクに書き出して行った.
【パラメータ】λ = 9 【メモリ使用量】1.6GB【公開鍵】59049bit→59058 個, 531442bit→583846 個【実行時間】[Key]3528.56734800,[Dec]0.13150716[Enc&Eval]5335.13199997

7

まとめと今後の課題“いくらか凖同型な暗号スキーム” を実装し, それを修正して “完全凖同型暗号スキーム” を実装した. 暗号化した結果を相手に渡し, 戻ってきた結果を復号すると, 正しい計算値になることがわかった. しかし, 現時点では λ の値が小さく, 実用的ではない.
今後の課題は, スキームの効率性を改善することである. 実用化されれば, クラウドコンピューティングなどで大きな応用が期待される.

【パラメータ】κ = γη/ρ′ , θ = λ, Θ = ω(κ · log λ)【構成】
KeyGen. sk*=p と pk*を以前と同様に生成する.
xp ← ⌊2κ /p⌉ とする. ただし, ⌊ ⌉ は四捨五入を表す. そして, ハミング重みが θ となるようなランダムな Θ-bitのベクトル ~s = hs1 , . . . , sΘ i を選ぶ. S = {i : si = 1}とする.
i = 1, . . . , Θ に対して、ランダムな整数 ui ∈ Z ∩P
[0, 2κ+1 ) を選ぶ. ただし, i∈S ui = xp (mod2κ+1 ) という条件に従う. yi = ui /2κ , ~y = {y1 , . . . , yΘ } とする. それ故, それぞれの yi は, 二進の小数点以下の精

参考文献[1] Craig Gentry:“Fully Homomorphic Encryption
Using Ideal Lattices”,(June.2009).
[2] Marten van Dijk,Craig Gentry,Shai Halevi
and Vinod Vaikuntanathan:“Fully Homomorphic Encryption over the Integers”,(June.2010).
56