Somewhat準同型暗号上の行列ベクトル積の為の効率的なパッキング手法

SCIS 2015
The 32nd Symposium on
Cryptography and Information Security
Kokura, Japan, Jan. 20 - 23, 2015
The Institute of Electronics,
Information and Communication Engineers
c
Copyright ⃝2015
The Institute of Electronics,
Information and Communication Engineers
Somewhat 準同型暗号上の行列ベクトル積のための効率的なパッキング手法
Eﬃcient Packing Technique for Secure Matrix-vector Multiplication
via Somewaht Homomorphic Encryption
陸文杰 ∗
Wenjie Lu
佐久間淳 †
Jun Sakuma
あらまし完全準同型暗号は暗号上での任意の演算が可能な新しい暗号スキームである. 特にクラウド
サービスにおける委託計算への応用は重要な課題であり暗号文上の演算を効率化することは重要な課題
である. 本稿では完全準同型暗号によって暗号化された行列とベクトルの積を効率的に評価するための新
しいパッキング手法を提案する. d × d の行列について Naive な手法と Halevi らのパッキング手法はそれ
ぞれ O(d2 ) と O(d) の時間計算量が必要である. 提案法ではこれをある条件下においては O(1) に改善す
る. また条件を満たさないサイズの大きな行列に対しては k 2 個の小さな行列に分解して計算する. この
場合の時間計算量は O(k 2 ) である. 我々の手法は 16 × 16 と 64 × 64 の行列とベクトルの積の計算時間は
それぞれ 0.01s と 0.03s であり Halevi らの手法と比較すると約 150 倍高速であることを示した.
キーワード準同型暗号パッキング, 行列ベクトル積, クラウド
1
はじめに
データ解析等の大規模な計算を実用的な時間で処理する
ためには現状での FHE は実用的な計算速度を達成して
近年データ保管をクラウドストレージに保管委託し,
いるとはいえない. FHE の構成要素である Somewhat
その処理をアウトソースする, クラウドベースサービス
Homomorphic Encryption(SwHE) は暗号化されたデー
タにおいて可能な演算の回数はあらかじめ定められた値
が急速に普及した. 個人情報や機密情報を含む情報を入
力とする計算タスクを外部にアウトソースする際には個
に制限されるがその計算速度はより短くデータ解析等の
人や企業のプライバシ保護が重要な課題である. クラウ
大規模な計算を実用的な時間で処理するためには, SwHE
ドサーバが信頼できる第三者とみなせない場合にはデー
の利用が現状では現実的である [10].
タを暗号化した上で保管委託を行うことで, プライバシ
行列とベクトルの積は様々なデータ解析において広く
保護を実現することができる. しかし, これと引き換え
用いられている基本的な演算の 1 つである. 例えば各種
にクラウド上のデータ処理が制限されることとなり, 実
統計量の評価, 固有値計算, 文字列パターン照合などの
用性に問題が生じる.
計算は行列とベクトルの積のみで評価できる. SwHE は
Gentry [5] による完全準同型暗号 (fully homomorphic
encryption FHE) におけるブレークスルーおよびこれに
続く一連の FHE を実現するスキームの発展 [1, 3, 14] に
あらかじめ与えられた回数の暗号文の演算 (加算および
乗算) を許すが乗算の回数が大きくなった場合, その計
算コストが増加することが知られている [7]. 入力デー
より, このプライバシ保護と実用性のジレンマが解決さ
タが大規模である場合その計算コストは無視できないこ
れることが期待されている. これらのスキームは暗号
とから, 効率化が必要である. 我々は SwHE で暗号化さ
化されたデータに対し復号なしで加算と乗算を可能に
れた行列とベクトルの積を効率的に評価する手法を考案
することから任意の演算を可能にする [6], これにより
する. 具体的には行列やベクトルの要素ごとに暗号化し,
ユーザはクラウドに暗号化したデータを保管委託した後
そのそれぞれついて行列ベクトル積に必要な演算を行う
に一切の通信なしで, 任意の計算処理が委託可能になる.
∗
†
代わりに行列やベクトルをそれぞれ単一の暗号文として
パッキングし, 行列ベクトル積を SwHE 上の一回の演算
筑波大学〒 305-8577 茨城県つくば市天王台 1-1-1. University of
Tsukuba 1-1-1 Tennodai, Tsukuba, Ibaraki, 305-8577, Japan.
[email protected]
筑波大学〒 305-8577 茨城県つくば市天王台 1-1-1. University of
Tsukuba 1-1-1 Tennodai, Tsukuba, Ibaraki, 305-8577, Japan.
[email protected]
として処理する手法を提案する.
1
表 1: 準同型暗号における行列ベクトル積の手法の時間・空間計算量の比較 (L: 行列ベクトル積の乗算回数. d: 行列
サイズ. n: 格子次元)
複雑度
Naive 手法
Halevi らの手法 [8]
時間
O(Ld2 )
O(d2 )
O(Ld)
O(d)
空間
1.1
関連研究
dL+1 ≤ n
O(L)
O(1)
1.2
提案法
dL+1 > n
O(L⌈ log d n ⌉2 )
L+1
d
⌉2 )
O(⌈ logL+1
n
貢献
2009 年 Gentry [5] が初めてイデアル格子に基づいた
我々は SwHE に基づく新しい ring-LWE 上のパッキ
FHE を提案し, その後様々な FHE スキームが提案され
てきた. 現時点では主に整数に基づくスキーム [4, 14],
イデアル格子に基づくスキーム [12], NTRU に基づくス
ング手法と, このパッキング手法を用いた, 複数ラウン
ドの行列ベクトル積を安全に計算することのできる効率
的なアルゴリズムを提案する.
キーム [9], learning with errors(LWE) に基づくスキー
表 1 の最後の列に我々の提案手法の計算量を示す. こ
ム [1–3] の 4 つの種類のスキームが存在する. これらす
こで整数 n は SwHE における円分多項式の次数である
べてのスキームは Gentry の提案に倣って設計されてお
(詳細については後述する). 提案手法では, 行列とベクト
ルはそれぞれ一つの暗号文にエンコーディングされ, こ
れら二つの暗号文同士の積のみで行列ベクトル積の計算
り, はじめに SwHE のスキームを設計した後にブートス
トラップによって FHE を達成している.
LWE 暗号に属する ring-LWE [1, 3] に基づく暗号ス
キームは暗号文や平文を多項式環の元で表現することか
が可能である. 表 1 から分かるように, 積のラウンドが
ら, 情報を多項式にエンコーディングする方法が複数提
案手法が既存手法よりも優れている. 後にに示す実験結
比較的小さい場合には, 空間計算量, 時間計算量共に提
案されている. Naehrig ら [10] は SwHE において効率
果では, AES 80bit の安全性において, SwHE により暗
的に算術演算を行うためのメッセージエンコーディング
号化された 16 × 16 64 × 64 の行列ベクトル積を評価し
を提案した. 彼らのアイデアは整数 M を n ビットの二
たところ, 案手法の計算時間はそれぞれ 0.01s 0.03s で
進数 (M , · · · , M
) で表現し, これを係数に持つ
∑n−1 (j) j
多項式 j=0 M x で表現することである. Smart と
あり, Halevi らの diagonal packing order による手法よ
(0)
(n−1)
りも 150 倍以上高速であることを示す.
Vercauteren [13] は polynomial-CRT(Chinese Remaider
Theorem) に基づきベクトルの要素ごとの準同型和と準
1.3
ノーテーション
同型積が計算できるパッキング手法を提案した. Yasuda
本稿ではすべてのインデックスは 0 から始める. R
ら [15] は Naehrig のスキームと同様に多項式を利用し
が分布, または集合であるとき, x ← R は x が R から
たパターン照合のためのパッキング手法を提案した.
一様分布に従って抽出されたことを意味する. 係数が Z
表 1 に安全に行列とベクトルの積を計算する手法の比
の要素である多項式の集合を Z[x] で表す. 行列を太字の
較を示す. ここで A は d × d の行列であり, v は長さが d
大文字 (e.g., A) で表し, クトルを太字の小文字 (e.g., v)
L
のベクトルである. 表 1 の計算量は, A v を安全に計算
で表す. Ai,j は, 行列 A の i–行 j–列の要素を表し, v i
するための時間計算量および空間計算量である. L は乗
はベクトル v の i 番目の要素を表す. d × d 行列 A の行
算回数である. 1 列目 (Naive) は A, v の要素を 1 つずつ
方向のベクトル化を Vec(A) と書く. つまり, Vec(A) :=
暗号化し, SwHE の暗号文上の加算・乗算によって計算
(A0,0 , · · · , A0,d−1 , · · · Ad−1,0 , · · · , Ad−1,d−1 ) である. 長
さ ℓ のベクトル u := (u0 , · · · , uℓ−1 ) に対し, m 番目の
した場合の計算量であり, 時間・空間計算量はそれぞれ
O(Ld2 ) である. 2 列目は Halevi らの手法 [8] の計算量
である. 彼らの手法は Smart らの手法を用いて, 暗号化
されたベクトルの要素和と要素積の計算を実現している.
長さ h の部分ベクトルを u(h,m) := (uh , · · · , uh+m−1 )
Halevi らの手法では row order, column order, diagonal
order の 3 つのパッキングについて言及しているが, 表
応する復号を Dsk (Epk (a)) と書く.
とする. 平文 a を 2 章で導入する SwHE スキームに基
づき公開鍵 pk で暗号化した暗号文を Epk (a) とし, 対
2
には行列ベクトル積の計算に最も適した diagonal order
を用いた場合を示している. 彼らの手法の時間・空間計
Ring-LWE による準同型暗号
準同型暗号は加算と乗算において, 暗号文同士の演算
算量はともに O(Ld) である.
の結果を復号した値が, 平文同士の演算の結果と一致す
る性質を持つ暗号方式である. ring learning with errors
(ring-LWE) 仮定に基づく暗号方式である Somewhat 準
2
同型暗号 [10] の標準的な構成を以下に示し, この暗号方
パッキング手法
3
式における演算について簡単に紹介する. 暗号方式の構
ドメイン D の要素を平文空間 Rt に写像するパッキン
築のためには, 以下に示すパラメータが必要となる.
グ関数を以下のように与える.
n は円分多項式 xn + 1 を定める 2 のべき乗の整数であ
り, 以下の多項式環 R = Z[x]/ ⟨xn + 1⟩．t は暗号方式に
ϕ (z) : D 7→ Rt .
おける平文空間を定義する素数であり, 平文空間を表す多
項式環 Rt := R/tR = Zt [x]/ ⟨xn + 1⟩ を与える．多項式
ここで D は整数, ベクトル, 行列など準同型演算の対象
の係数は Zt の元である．q は t ≪ q なる整数であり, 暗
となる情報の空間を表す. 本章では, これまでに提案さ
号文空間を表す多項式環 Rq := R/qR = Zq [x]/ ⟨xn + 1⟩
れたパッキング関数 ϕew (·), ϕf w (·), ϕbw (·) について議
を与える．その多項式の係数は Zq の元である．σ は離
論する. ドメイン D とこれらのパックされた値 (Rt 内
散ガウス分布 χ = DZn ,σ の標準偏差である. ここで, 離
の要素) に対応する操作は表 2 に示されている. 最後の
散ガウス分布の確率密度関数は
行のパッキング関数は次章で議論する我々の提案パッキ
ング関数である. また, パックされた値をリカバーする
e−π∥ε∥/σ
∀ε ∈ Z : Pr [ε ← DZn ,σ ] = ∑
−π∥ε∥/σ 2
ε∈Zn e
2
n
アンパッキング関数 υew (·), υsp (·) についても議論する.
3.1
で定義される. D は Zn 上の分布であり, 以降では χ か
要素ごとの演算のためのパッキング関数
多項式 xn + 1 は次数が n/r の r 個の既約な相異なる
ら多項式 ε(x) ∈ R がサンプリングされるものとする. D
多項式
および A は, それぞれ準同型積および準同型和が正しく
計算できる最大回数である．
xn + 1 =
r−1
∏
Fj (x) mod t.
j=0
2.1
SwHE Scheme
に分解できる. Smart と Vervauteren は, この事実を用
以下に, SwHE の構成とその演算について示す.
いたパッキング手法を提案している. Fj (x) の根をそれぞ
鍵生成 KeyGen(1κ ): まず, χ からサンプリングさ
れ γj とする. パッキング対象であるベクトル v を v ∈ Zrt
れた環の要素 sk ← χ を秘密鍵とする. 次に, Rq か
とし, 以下のパッキング関数 ϕew (·) を考える:
ら一様ランダムにサンプリングした環の要素 a1 ← Rq
と, χ からサンプリングした e ← χ を用いて, 公開鍵
ϕew (v) =
pk := (a0 = −(a1 sk + te), a1 ) を計算する.
n−1
∑
αi xi ∈ Rt , where
i=0
暗号化 Epk (m): 公開鍵 pk と平文 m ∈ Rt について,
∀j, 0 ≤ j < r,
χ から要素 u, f, g ← χ を抽出し, 暗号文 ct = (c0 , c1 ) :=
r−1
∑
αi γji = v j
mod t.
i=0
(a0 u + tg + m, a1 u + tf ) ∈ (Rq )2 を計算する.
復号 Dsk (ct): 暗号文は二つの Rq の多項式で与え
られるが, 以下に示す準同型和や準同型積は, 一つの暗
e(x). e′ (x) ∈ Rt の入力を γj とすると, 以下の様な性質
を持つ.
号文が含む多項式の数を増加させるため, 暗号文が含む
e(γj ) + e′ (γj ) = (e + e′ )(γj ),
多項式の数を ℓ + 1 とする．与えられた秘密鍵 sk と
e(γj ) · e′ (γj ) = (e × e′ )(γj ).
暗号文 ct = (c0 , · · · , cℓ ) ∈ (Rq )ℓ+1 について, 復号は
∑ℓ
m̃ = i=0 ci sk i ∈ Rq を計算し, m̃ mod t を出力する.
ϕew (·) の定義と上記の性質から, ベクトル v 1 , v 2 , ∈ Zrt
を ϕew (·) でパッキングして得た Rt 上の多項式 ϕew (v 1 ),
Epk (m1 ) ∈ (Rq )η , Epk (m2 ) ∈ (Rq )ξ は [1] の方式で
暗号化された暗号文であるとする. このとき準同型和 ⊕
ϕew (v 2 ) の加算と乗算は, ベクトル v 1 , v 2 の要素同士の
加算と乗算を与える.
と準同型積 ⊗ は以下で与えられる.
パックされたベクトル ϕew (v) が与えられたとき, v を
Epk (m1 ) ⊕ Epk (m2 ) = Epk (m1 + m2 ) ∈ (Rq )max(η,ξ) ,
復元する関数 υew (·) は以下のように与えられる.
Epk (m1 ) ⊗ Epk (m2 ) = Epk (m1 × m2 ) ∈ (Rq )η+ξ+1 .
υew (ϕew (v)) :=
ここで, ⊕, ⊗ は (Rq )∗ 上で定義された演算であり, +,
n−1
∑
× は Rt 上の演算である. 準同型和 ⊕ と準同型積 ⊗ の
(
具体的な方法については [10] を参照されたい.
i=0
3
αi γ0i
mod t, · · · ,
n−1
∑
i=0
i
αi γr−1
mod t) = v.
文献
[10]
[13]
[15]
Ours
3.2
D
Z
Zdt
Zdt 1 , Zdt 2
Zd×d
, Zdt
t
表 2: パッキング関数とその操作
ϕ (·)
ϕbits (·)
ϕew (·)
ϕf w (·), ϕbw (·)
ϕmat (·) , ϕvec (·)
+
Z 上の加算
要素ごとの加算
Rt 上の加算
Rt 上の加算
内積演算のためのパッキング関数
×
Z 上の乗算
要素ごとの乗算
内積
行列ベクトル積
前章で示したパッキング手法の重要な特性は, 複数の
Yasuda ら [15] は [10] に基づいた効率的な内積計算の
ためのパッキング手法を提案した. u を長さ ℓ の二値ベ
値の加算やベクトルの内積といった複数の値に関する演
クトル, v を長さ m(m ≤ ℓ < n) の二値ベクトルとする.
では, 行列ベクトル積を効率的に計算するためのパッキ
このとき, 以下の 2 つのパッキング関数を考える:
ング関数 ϕmat (·) , ϕvec (·) と, これに対応するアンパッ
ϕf w (u) :=
ℓ−1
∑
算を一回の準同型演算で評価できることである. この章
キング関数 υM atV ecP rod (·) を導入する. A を d × d の行
列, v を長さ d のベクトルとする. このとき, 次のような
ui x ∈ Rt ,
i
性質を持つパッキング関数とアンパッキング関数を実現
i=0
ϕbw (v) := −
m−1
∑
v j xn−j ∈ Rt .
することがこの章の目的である.
(1)
j=0
e(A) := Epk (ϕmat (A; s)) ,
ϕf w (·) は Naehrig ら [10] のメッセージエンコーディン
e(v) := Epk (ϕvec (v; s)) ,
グと同様である. このとき ϕf w (u) と ϕbw (v) の準同型
υM atV ecP rod (Dsk (e(A) ⊗ e(v))) = Av.
積は以下を与える
ここで s はステップパラメータである (後に詳述). 簡単
ScalarProd :=Epk (ϕf w (u)) ⊗ Epk (ϕbw (v))


ℓ−1
m−1
∑
∑
=Epk 
ui xi × −
vj xn−j 
i=0
のために, ここでは正方行列についてのみ述べるが, 我々
の手法は任意のサイズの行列に対して適用できる.
j=0
)
(ℓ−m
⟩
∑⟨
u(h,m) , v xh + U .
=Epk
4.1
後に導入するアルゴリズムのために, 行列ベクトル積
(2)
に関連する二つの事実を導く.
h=0
記号 e· はベクトルの要素の順序の逆転を表す. 行列の
ここで, U は次数が ℓ − m より大きい部分多項式を示
場合は各行ベクトルの要素順序の逆転を表す. 例えば,
A を d × d の行列, v を長さ d のベクトルとすると, 逆転
e および v
e は, それぞれ次のように表される.
A
す. 以降では, これらを unconcerned terms と記述する.
式 2 の内積を復元するための関数 υsp (·) は unconcerned
terms を取り除く関数である.
υsp (Dsk (ScalarProd)) =
⟨
⟩ ⟨
⟩
⟨
⟩
( u(0,m) , v , u(1,m) , v , · · · , u(ℓ−m,m) , v ).
準備
(3)
e i,j := Ai,−1−j
A
0 ≤ i, j < d,
ei := v d−1−i
v
0 ≤ i < d.
行列 A とベクトル v, u の逆転について, 以下の二つ
このパッキング関数は xn = −1 となる R の環の構造
の性質が成り立つ.
を利用している. 復元においては, 多項式同士の準同型
積の結果から, 意味のある項だけを抽出して利用する点
e⟩ ,
⟨u, v⟩ ≡ ⟨e
u, v
に特徴がある. 式 3 の評価は, 複数の内積値が一回の準
e v.
Av ≡Ae
(4)
同型積で得られるという点において, 常に効率的である.
また, A を d × d の行列, v を長さ d のベクトルとす
4
行列ベクトル積のためのパッキング手法の
提案
る. このとき, 以下が成り立つ.
⟨
⟩
(Av)h = Vec(A)(dh,d) , v ∀h, 0 ≤ h < d,
この章では, 準同型暗号において行列ベクトル積を効
ここで Vec(A) は, 行ごとの A ベクトル化である.
率よく計算するための新しいパッキング関数とアンパッ
キング関数を提案する.
4
(5)
4.2
行列・ベクトルパッキング
Algorithm 1 Matrix-vector multiplication
Require: L > 0, A ∈ Zd×d
, v ∈ Zd×1
t
t
1: e(e
u(0) ) = Epk (ϕvec (e
v ; 1))
2: for i = 1 to L(do
(
))
e = Epk ϕmat Vec(A);
e di−1
3:
e(A)
この小節では, 行列・ベクトル積のためのパッキング
関数とアンパッキング関数を提案し, 暗号化された状態
での行列とベクトルの乗算を実現法を示す. まず, パッ
キング関数の構成要素を定義する.
e
e(u(i) ) = e(e
u(i−1) ) ⊗ e(A)
4:
Definition 1. u を長さ ℓ のベクトル, s ∈ Z+ をステッ
if i + 1 ≤ L then
i+1
e(e
u(i) ) = e(u(i) ) × −xn−(d−1)d
end if
5:
プパラメータとする. 二つのパッキング関数を次のよう
6:
に定義する.
7:
−
→
ρ (u; s) :=
ℓ−1
∑
ui xs·i
8:
mod (xn + 1, t) ∈ Rt ,
9:
i=0
←
−
ρ (u; s) := −
ℓ−1
∑
mod (xn + 1, t) ∈ Rt .
uj xn−s·j
Proof.
j=0
))
(
(
e s ⊗ Epk (ϕvec (e
Epk ϕmat A;
v ; s))



 2
d∑
−1
d−1
∑
e i xs·i  ⊗ Epk −
ej xn−s·j 
v
=Epk 
Vec(A)
n, t は SwHE スキームのパラメータである.
上式は, [15] で提案された式 1 の一般化であり, ステッ
プパラメータ s = 1 において, 上式は式 1 と等価である.
−
→
−
ρ (·) と ←
ρ (·) は簡単な操作によって交換可能である.
具体的には, u ∈
Zℓt
end for
return e(u(L) )

=Epk 
とすると, 以下を得る.
←
−
→
ρ (e
u; s) = −
ρ (u; s) × −xn−(ℓ−1)s .

=Epk 
この性質は以下のように確かめられる.
−
→
ρ (u; s) × −xn−(ℓ−1)s =
ℓ−1
∑

s·i
ui x
=Epk 
× −x
n−(ℓ−1)s
i=0
=−
ℓ−1
∑
ui xn−s(ℓ−1−i) = −
i=0
ℓ−1
∑
i=0
j=0
d∑
−1
2
e i xs·i × −
Vec(A)
i=0
j=0
2
d∑
−1 ∑
d−1
=Epk
j=0

ej xn−s·j 
v
(7)

e iv
ej xs·(i−j) 
Vec(A)
(8)
i=0 j=0
d−1
∑



d−1
∑
e dh+j v

ej  x(sd)h + U 
Vec(A)
j=0
h=0
−
e j xn−s·j = ←
u
ρ (e
u; s)
d−1
∑
(d−1
∑⟨
(dh,d)
Vec(A)
⟩
,v x
(9)
)
(sd)h
+U
(10)
h=0
→
=Epk (−
ρ (u; sd) + U)
(6)
(11)
A を整数行列, v を整数ベクトルとしたとき, 提案す
るパッキング関数は次の式で定義される.
式 6 より,
−
ϕmat (A; s) := →
ρ (Vec(A); s),
−
ϕ (v; s) := ←
ρ (v; s).
→
Epk (−
ρ (u; sd) + U) × −xn−(d−1)sd
−
=E (←
ρ (e
u; sd) + U)
vec
pk
以下の定理は, ϕmat (·) と ϕvec (·) の乗算が, ϕvec (·) を
=Epk (ϕvec (e
u; sd) + U)
与えることを示す.
Theorem 1. A ∈ Zd×d
, v ∈ Zd×1
, u = Av とする,
t
t
このとき
(
(
))
e s ⊗
Epk (ϕvec (e
u; sd) + U) = Epk ϕmat A;
式 7 から式 8 は, 多項式環 R の特性である xn = −1
を用いている. 式 8 から式 9 は, Av からなる項につ
∑d−1
e
ej =
いてのみに焦点を当てている.
j=0 Vec(A)dh+j v
⟨
⟩
e (dh,d) , v
e を考慮すると, 式 4 より, 式 9 から
Vec(A)
→
式 10 を得る. 式 5 と −
ρ (·) の定義より, 式 10 から式 11
Epk (ϕvec (e
v ; s)) × −xn−(d−1)sd
が成り立つ. ただし, U (unconcerned terms) は集合
を得る. 以上より, ϕmat (·) と ϕvec (·) が準同型演算上で
{0, sd, 2sd, · · · , (d − 1)sd} 以外の次数を持つ項の和で
ある.
行列ベクトル積を与えることをが示された.
L を自然数としたときに, AL v を評価する手順を Algorithm 1 に示す. ただし, u(i) := Ai v であり, 無視
5
すべき項は省いている. 4 行目から 7 行目までは The(L)
orem 1 から得られる. ここで, e(u
実験
5
) のステップパ
本章では, 行列ベクトル積における提案パッキング法
ラメータは dL である. このとき, 以下に示すアンパッ
の性能を比較するために, ナイーブな手法, Halevi らの
キング関数 υM atV ecP rod (·) は, ステップサイズ dL ゆえ,
手法 [8], 提案手法の計算時間を比較する.
{0, dL , 2dL , · · · , (d−1)dL } の次数を持つ項を取り出せば
(
) ∑n−1
良い. Dsk e(u(L) ) = i=0 αi xi とし, υM atV ecP rod (·)
は次ように定義する.
(
(
))
υM atV ecP rod Dsk e(u(L) )
対象問題は次元数 d = 4, 8, 16, 64 の行列 A とベクトル
v の積である. 両者を SwHE で暗号化し, L = 1, · · · , 5
について, AL v を評価するために必要な時間を計測する.
5.1
= (α0 , αdL , · · · , α(d−1)dL ) = A v.
実験設定
L
ナイーブな手法は, 単純に行列とベクトルのそれぞれ
の要素を暗号化し, FHE の準同型性を利用することに
Algorithm 1 では, i 番目の乗算の後に, ステップパラ
メータを di−1 から di に更新する. ベクトル Ai v のす
よって暗号化した行列とベクトルの積を評価する. 従っ
て, サイズ d の行列が与えられた時, 行列ベクトル積一
べての要素を Rt にパックする必要があることを考える
回あたりのナイーブな手法の時間計算量と空間計算量は
と, n は di+1 ≤ n を満たす必要がある. 実際には, n は
どちらも明らかに O(d2 ) である.
214 以下であることが多いため, このパッキング手法に
Halevi らの方法では, Smart らにより提案された FHE
おいて扱うことができる行列のサイズ, および乗算のラ
において, 要素ごとの和や積が可能なパッキング手法 [13]
ウンド数はどちらも小さいという問題がある. 例えば,
を利用した行列ベクトル積を実現している. このパッキ
Algorithm 1 において 5 × 5 行列の行列ベクトル積は,
55 < 214 < 56 ゆえ, L = 4 ラウンド以上は正しく実行で
きない. 次の節で, この制約を緩和する方法にっいて議
ング手法では行列の一つの一般化対角成分を一つの暗号
文として暗号化するため, サイズ d の行列ベクトル積を
評価するためには, d 回の準同型積, および準同型和が必
論する.
要である.
4.3
行列の分割による n に関する制約の緩和
提案法のベクトル行列積における時間計算量は, 分割
数 k に依存する. 行列サイズ d および積の回数制約 L が
本節では, 前節でにおいて導いた制約 di+1 ≤ n を, 行
列の分割により回避する. 具体的には, 元の行列 A を,
制約 dL+1 ≤ n を満たす場合には, 行列サイズに関わら
同じ大きさを持つ k 2 個の部分行列に分割し, べクトル
ず必要な準同型演算の回数は 1 回である. これを満たさ
v も, 同じ大きさを持つ k 個の部分ベクトルに分割する.
k = 2 のときには, このようになる.
[
][ ] [
] [
]
A0 |A1 v 0
A1 v 1
A0 v 0
Av =
+
(12)
=
A2 |A3 v 1
A2 v 1
A3 v 1
| {z } | {z }
ない場合には, 分割数 k について k 2 回の準同型演算が
A
必要である.
実験は Intel Core i7 2.3GHz, 6G DDR3 RAM の同一
計算機上で行った. 全手法は HElib とよばれる Halevi
と Shoup [8] によって設計された準同型暗号のオープン
ソースライブラリ [11] の上で実装された. [8] に示された
v
式 12 で示した通り, Av は, A と v の部分行列と部分ベ
行列ベクトル積の実験結果と, 本稿で示す実験結果は大
クトルの積で計算することができる. この分割によって,
きく異なる. これは [8] における実験結果は暗号化ベク
大きいサイズ行列の行列ベクトル積を, k 回の小さいサ
トルと平文の行列における行列ベクトル積の計算時間を
イズの行列の行列ベクトル積に置き換えることができる
評価したものであると考えられるためである 1 . 本稿で
ことから, 制約 dL+1 ≤ n が充足されるために必要な十
示す結果は全て暗号化ベクトルと暗号化行列の積の計算
分小さい分割数 k を設定することで, 制約に関わらず任
時間である点に注意されたい.
2
意のサイズの行列ベクトル積が計算可能である. 一般的
5.2
に, d × d の行列 A と長さ d のベクトル v が与えられた
パラメータ設定
SwHE 暗号は設定パラメータ数が多く, パラメータ間
に依存性がある上に, それぞれのパッキング手法におい
とき, もしも行列が各ステップで k 個に分割されていれ
ば, L 回目の乗算の後では, 制約式は次のようになる.
て必要な条件が異なる. そこで, 実験では, セキュリティ
⌈(d/k)⌉
L+1
≤n
レベル (AES-80 bits) において, 全ての手法において平
(13)
文空間 (つまり行列, ベクトルの各要素) が t ≃ 240 であ
2
ただし, 行列の分割によって, 準同型演算の回数は k 回
ることを前提とし, それぞれのパッキング手法に適したパ
に増加する点に注意されたい.
1
6
この点は [8] には明記されていないが, [11] にて公開されている実
装から推測した.
数 k が異なることを表しており, 異なる色は行列ベクト
表 3: Halevi らの方法における n = 210 での t の設定例
t ≈ 240
1099511622919
1099511622929
1099511623583
1099511623297
order(t, 2n)
256
128
64
16
ル積の回数 L が異なることを表している. 図 1 に, 提案
#slot
4
8
16
64
法の異なる行列のサイズと乗算回数における提案法の計
算時間を示す. 図では, 分割数 k = 1, 2, · · · , 32 に応じ
て異なる形状のプロット点を用いている. また, 行列ベ
クトル積の回数 L に応じて異なる色の線を用いている.
L = 1 の場合, 次元 d に関わらず分割数は 1 で計算が実
ラメータ設定を選択した. HELib では, ノイズマネジメ
行可能であることから, 計算時間は全て 0.1 秒程度と高
ントに関連するパラメータを, 許容できる準同型乗算の
速であった. 一方で次元 d が大きい場合には, L が大き
回数 D および準同型和算の回数 A の代わりに, トータル
い場合, 分割数を 2 以上に設定する必要があった.
の計算で増加するノイズ量に対応可能な許容量 (levels)
に応じて設定する. このパラメータは, 一般的には必要
5.4
になる準同型乗算の回数 D より大きく設定すればよい.
実験 2
この実験では, 異なる行列サイズ d = 4, 8, 16, 64 にお
これらを考慮し, 提案手法のパラメータは以下のよう
いて, L = 1 ∼ 5 回の行列ベクトル積を実行した. 図 2
に設定した.
に, 提案法とナイーブな手法, Halevi らの手法を用いた
• 平文空間の底 t は 2
40
ときの, 行列ベクトル積の計算時間を示す. パッキング
付近の素数に設定した.
手法によっては, 行列ベクトル積は異なるパラメータの
• 行列ベクトル積の回数 L に対し, levels = 4L と
組み合わせにおいて実現可能である. そのような場合に
した.
は, 最も計算時間が短くなるようなパラメータの組み合
わせを選択した.
• 分割数は, 行列サイズ d と乗算回数 L に応じて
k = 1, 2, 4, 8, 16, 32 から求めた. 実験 1 では式 13
図より, ナイーブな手法は, 行列ベクトルの乗算回数
を満たす全ての値について実験を行った. 実験 2
が少ない場合でも, 多種法に比べ, 明らかに計算効率が
では式 13 を満たす値のうち最小の値について実験
低いことがわかる. 提案法と Halevi らの手法を比べる
を行った.
と, 次元数が比較的低い d = 4, 8, 16 では, 全ての乗算回
数において提案法のほうが高速である. 具体的には, 提
ナイーブな手法のパラメータは, 分割数 k を使わないこ
案法は L ≤ 3 において, Halevi らの手法よりも 8 ∼ 150
とを除いて上記と同一のパラメータを用いた.
倍高速である. 一方で次元数が d = 64 では, 乗算回数
Halevi らの手法におけるパラメータの設定戦略は, 提
案手法とは若干異なる. このパッキング手法では, 一つ
L = 5 の場合には Halevi らの手法のほうが高速である.
これは, 行列をパッキングする際の分割数の設定が原因
であると考えられる.
の暗号文にパッキング可能な値の数は以下の式 14 で定
義されるスロットと呼ばれる値で決定される.
#slots =
ϕ(2n)
.
order(t, 2n)
Halevi らの手法は, 一つの暗号文当たりにパッキング
される行列の要数は常に d 個であることから, d 次元行
(14)
列のパッキングに必要な暗号文の個数は d である. 提案
ここで, ϕ(·) はオイラー関数であり, order(t, 2n) は 2n
法は, 入力する正方行列を複数の正方行列に分割した上
における t の剰余位数である. このパッキング手法を用
でパッキングをする必要があることから, k 分割した場
いた行列ベクトル積においては, このスロット数を次元
合, d 次元行列のパッキングに必要な暗号文の個数は (d
数 d と一致させる必要があるため, #slots = d となるよ
に関わらず)k 2 個である. 分割方法の改善は今後の課題
うな 240 に最も近い t を選択した. t の選択結果を表 3 に
である.
示す. このパッキング手法では, ベクトル行列積の計算
行列ベクトル積計算は, 共分散行列や固有値計算など
において, 準同型積, 準同型和の他に, rotation と呼ばれ
基本的なデータ解析・統計計算を実現するためのプリミ
る演算も利用しており, 適切な levels 設定の見積もりが
ティブとして重要である. 今後は, 具体的なデータ解析
複雑である. 実験では, 正しい計算を返すような最小の
の応用において実用的な計算時間を実現できるように,
levels を経験的に決定し, これを用いた.
手法のさらなる高速化を目指す.
5.3
6
実験 1
謝辞
本研究は, JST CREST「ビッグデータ統合利活用の
ための次世代基盤技術の創出・体系化」および科学研究
費 24680015 の助成を受けた.
実験 1 では提案法の計算時間を詳細に調査する. 図 1
に, 提案法の異なる行列のサイズと乗算回数における提
案法の計算時間を示す. 図において, 異なる記号は分割
7
0.81
0.99
3.04
0.17
0.61
0.14
0.10
0.04
0.04
L
0.01
1
2
3
4
5
PARTITION
0.02
1
2
0.01
1
2
3
4
L: Multi. Round
0.04 L
0.02
0.01
5
0.01
1
(a) Matrix Size d = 4
1.7
34
2.3
0.13
0.1
2
3
4
L: Multi. Round
0.07
L
1
2
3
4
5
0.01
5
1
(b) Matrix Size d = 8
231
27
37
7.7
0.466
1 PARTITION
1
2
2
3
4
4
5
183
17
1.06
Time(s)
0.08
0.47
2.21
0.3
Time(s)
Time(s)
0.10
0.13
133
82
100
5.21
1.00
0.57
15
12
8.5
10.0
1.34
0.37
0.16
3.81
2.18
0.59
Time(s)
1.00
1.96
1
0.91
PARTITION L
PARTITION
1
2
4
8
2
8
16
32
0.03
2
3
4
L: Multi. Round
5
1
(c) Matrix Size d = 16
2
3
4
L: Multi. Round
1
2
3
4
5
5
(d) Matrix Size d = 64
図 1: 提案手法による行列ベクトル積の (multiplication round L = 1 ∼ 5) の計算時間. 左から, 行列次元を
d = 4, 8, 16, 64 とした. 分割数 k は次元に応じて 1 ∼ 32 とした.)
37
6.3
4.6
0.99
Time(s)
0.84
0.23
0.17
148
5.4
3.81
0.04
0.61
0.33
0.01
1
0.1
2
3
4
L: Mult. Round
0.04
(a) Matrix Size d = 4
5
20
31
15
1291
5.2
2.3
1.6
0.01
1
0.1
Method
Halevi’s
Naive
Prop.
1.24
2
3
4
L: Mult. Round
5
1
(b) Matrix Size d = 8
89
100
22
48
21
231
136
37
5.8
1.96
1
Method
0.01
2676
1782 2241
659
0.13
Method
Halevi’s
Naive
Prop.
354
11
10.0
1.3
0.65
288
74
16
0.09
0.1
219
10
10.0
2.11
88
72
18
4
Time(s)
10.0
55
Time(s)
22
18
Time(s)
14
9.2
Method
Halevi’s
Naive
Prop.
2
3
4
L: Mult. Round
5
(c) Matrix Size d = 16
0.03
1
Halevi’s
Naive
Prop.
2
3
4
L: Mult. Round
5
(d) Matrix Size d = 64
図 2: 提案法, ナイーブな手法, Halevi らの手法 (multiplication round L = 1 ∼ 5) による, 行列ベクトル積の計算時
間. 左から, 行列次元 d = 4, 8, 16, 64 をした. 分割数は, 対象する行列を計算可能な最小の分割数を設定した.
参考文献
[10] Michael Naehrig, Kristin Lauter, and Vinod Vaikuntanathan.
Can homomorphic encryption be practical? In Proceedings of
the 3rd ACM CCSW 2011, pages 113–124. ACM, 2011.
[1] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan.
(Leveled) fully homomorphic encryption without bootstrapping.
In Proceedings of the 3rd Innovations in Theoretical Computer
Science Conference, pages 309–325. ACM, 2012.
[11] Victor Shoup Shai Halevi. HELib. http://shaih.github.io/
HElib/index.html. Accessed: 2014-12-10.
[2] Zvika Brakerski and Vinod Vaikuntanathan. Eﬃcient fully homomorphic encryption from (Standard) LWE. In 2013 IEEE
54th Annual FOCS 2011, pages 97–106. IEEE, 2011.
[12] Nigel P Smart and Frederik Vercauteren. Fully homomorphic
encryption with relatively small key and ciphertext sizes. In
Public Key Cryptography–PKC 2010, pages 420–443. Springer,
2010.
[3] Zvika Brakerski and Vinod Vaikuntanathan. Fully homomorphic encryption from ring-lwe and security for key dependent
messages. In Advances in Cryptology–CRYPTO 2011, pages
505–524. Springer, 2011.
[13] Nigel P Smart and Frederik Vercauteren. Fully homomorphic
SIMD operations. Designs, codes and cryptography, 71(1):57–
81, 2014.
[4] Jean-Sébastien Coron, Avradip Mandal, David Naccache, and
Mehdi Tibouchi. Fully homomorphic encryption over the integers with shorter public keys. In Advances in Cryptology–
CRYPTO 2011, pages 487–504. Springer, 2011.
[14] Marten Van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic encryption over the integers.
In Advances in Cryptology–EUROCRYPT 2010, pages 24–43.
Springer, 2010.
[5] Craig Gentry. A fully homomorphic encryption scheme. PhD
thesis, Stanford University, 2009.
[15] Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro
Yokoyama, and Takeshi Koshiba. Secure pattern matching using somewhat homomorphic encryption. In Proceedings of the
2013 ACM CCSW 2013, pages 65–76. ACM, 2013.
[6] Craig Gentry. Computing arbitrary functions of encrypted data.
Communications of the ACM, 53(3):97–105, 2010.
[7] Craig Gentry and Shai Halevi. Implementing gentry ’s fullyhomomorphic encryption scheme. In Advances in Cryptology–
EUROCRYPT 2011, pages 129–148. Springer, 2011.
[8] Shai Halevi and Victor Shoup. Algorithms in helib. In Advances
in Cryptology–CRYPTO 2014, pages 554–571. Springer, 2014.
[9] Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan.
On-the-fly multiparty computation on the cloud via multikey
fully homomorphic encryption. In Proceedings of the fortyfourth annual ACM STOC 2012, pages 1219–1234. ACM, 2012.
8

Download Report