狠狠撸

Self Introduction
陸文杰 (Wen-jie Lu)。中国広東出身。
2009 - 2013 中国 JiNan University（広州）情報科学学部卒.
2013 - 2014 言語学校
2014 - 2019 筑波大学博士課程。指導教員：佐久間淳。DC2
研究： secure multi-party computation, homomorphic encryption. 2

FHE In Action
現在の完全準同型暗号 (FHE) について自分の理解
既存の FHE 実装をどう使う my-know-how 3

なぜ準同型暗号を使おうとするのか?
データや情報を秘密したまま何らかの計算を行いたいから 4

なぜ準同型暗号を使おうとするのか?
データや情報を秘密したまま何らかの計算を行いたいから
例：app のユーザは転売屋かどうかを検知する
サーバーから識別器をユーザへに push
ユーザの情報 (i.e., 携帯の物理情報など) はサーバへに収集できない
識別器は reverse engineering される恐れがある
現在はコードの obfuscation ベースでやっているらしい 5

なぜ秘密分散や GC ベースだけならいけないのか
通信 latency や通信量に厳しい
帯域より計算力の方が scalable
e.g. 10 Gbps 帯域においてサーバー一台 v.s. 50 クライアント. 同時に行列積の秘密計算。
OT vs. FHE
6

FHE を使う他の場面
Secure Multi-party Computation
Secure Outsourcing
SMC -> Threshold-FHE + Secure Outsourcing
etc. 7

Fully Homomorphic Encryption
暗号化したまま「足し算」と「掛け算」が可能な暗号方式
『クラウドを支えるこれからの暗号技術』@herumi さん
上 +, x あれば完備なので任意の Boolean 関数を暗号文上で計算できる
The glory of cryptography で呼ばれる理由 (?)
GF (2) ?
9

FHE and Boolean Circuit
一ビット
関数を boolean 回路に変換して評価する。
key: 回路の深さをどれだけ小さくできるのか.
同じ関数でも異なる boolean circuit がある
電子回路と類似、深いほど計算時間がかかる (理由は違うが)
+ mod 2 = XOR?b1 b2 b1 b2
× mod 2 = AND?b1 b2 b1 b2
F
10

FHE and Arithmetic Circuit
平文はビットではなく有限体の元である. for a prime .
を計算する AC
同様、AC の深さは重要なパラメータ
Zt
t
, , , ∈x1 x2 x3 x4 Zt
× × × mod tx1 x2 x3 x4
11

BC vs. AC: Pros and Cons
Boolean circuit (BC) 的な考え方
pros: 任意の関数を評価可能
cons: メモリコストと計算コスト
- ciphertext expansion が悪い. 1 bit を暗号すると数 KB の暗号文.
Arithmetic circuit (AC) 的な考え方
pros:
- 線形計算な関数をより浅いな AC を作れる.
- ciphertext expansion がいい (SIMDを利用する)
cons:
- 非線形関数はそのまま評価できない. e.g., max, mux
どちらも準同型の演算を早くする必要がある.
計算コストを削減するテクニックはいくつがある. (これから紹介する) 12

A Buggy but Informative Construction
13

Gaussian 分布からキーをランプリングする. .
Encryption: . .
Learning with Errors (LWE) に帰着
ここのはまだ定義しない
sk ← χ
n
m ∈ , (e. g. , t = 2)Zt
a ← , e ←Z
n
q
χ
′
ctx = (a, b = m + e ? a ? sk mod q).
?
14

Decryption,
なら正しく復号できる
ctx = (a, b = m + e ? a ? sk).
= b + a ? sk mod q. ?outputs? {m
~ 0?| ? 0| < | ? q/2|m
~
m
~
1?o.w.
|e| < q/4
15

A Buggy but Informative Construction (Cont'd)
とする
Addition :
Multiplication:
四つの特徴
1. noisy な暗号文
2. 計算によって暗号文ノイズが増加。しきい値を上回ったら復号できなくなる。
3. 復号の関数の回路は "浅い"
4. 掛け算によって暗号文のレングスも変化する (e.g., 2から3になる)
ct = ( , ), ct = ( , )x1 a1 b1 x2 a2 b2
ct ⊕ ct = ( + , + )x1 x2 a1 a2 b1 b2
ct ? ct = ( ? , ? + ? , ? )x1 x2 a1 a2 a1 b2 a2 b1 b1 b2
16

ノイズの増やす方
1. 初期のノイズ(の分散)は ( は hamming weight)
2. 準同型足し算
3. 準同型掛け算によってノイズの分散
4. addPlain:
5. multPlain:
平文のはあまり大きくしない
big number な平文が欲しい時、小さいで表現する (e.g., CRT decomposition)
O( + n W )n
2
t
2
W
+var1 var2
× × lengthvar1 var2
var + O(n )t
2
var × O(n )t
2
t
t
17

計算効率がいい FHE へ
18

計算効率がいい FHE への道
Ring-LWE ベースなスキームの方が準同型演算がより効率だ.
FFTにより
例えここのはすべてである
- 次数は以下かつ係数はの多項式の集合
- '' '' は多項式環上の掛け算で定義される
O( ) → O(n log n)n
2
a, b, e ∈ [X]/( + 1)Zq X
n
ctx = (a, b = m + e ? a ? sk mod (q, + 1))X
n
n mod q
? 19

1. 多項式ベースな RLWE スキームは LWE スキームより効率.
2. 暗号文のノイズを抑えるテクニック
Mod-switch [BGV11]
reLinearization [BV11b]
Bit-decomposition [BV11a]
Bootstrapping. 暗号文をさらに暗号化して、復号関数を暗黙的に評価する
2
20

1. 多項式ベースな RLWE スキームは LWE スキームより効率.
2. 暗号文のノイズを抑えるテクニック
Mod-switch [BGV11]
reLinearization [BV11b]
Bit-decomposition [BV11a]
Bootstrapping. 暗号文をさらに暗号化して、復号関数を暗黙的に評価する
3. 実装面の高速化
Packing (SIMD) [SV11]
Residue Number System (RNS)
2
21

Modulus Switching (Mod-Switch)
22

技その１：Mod-Switch
文字通り: の暗号文に変換することによってノイズを削減す
る
暗号文の累積ノイズは準同型演算によって増加してまう。
初期のノイズとする。
1. 一回足し算。
2. 一回掛け算 . 更に掛け算すると .
ノイズなると正しく復号できなくなる
とする。1-st Gen な FHE はの深さの回路しか評価できない
mod q → mod q
′
(q > )q
′
e
|e| < B
| | < 2Be+
| | <e× B
2
| | <e× B
4
|e| > q/4
q ≈ 4B
L
log L
23

技その１：Mod-Switch
初期のノイズをとする。
Mod-Switch: 準同型掛け算した（する）時、暗号文をで割る
1. (実際は少し複雑)
2. ノイズのスケールも削減される
3. 法も小さくになる .
4. 初期の法はなので深さの回路を評価できる
|e| < B
ctx = (a, b) B
= a/B, = b/Ba
′
b
′
| | < → | | < Be× B
2
e×
q q ≈ 4B
L?1
q ≈ 4B
L
L 24

技その１：Mod-Switch (Cont'd)
pros
1. 評価できる回路の深さまで
cons
1. 異なる法に従う号文が同時に存在しうるので暗号文の法をトラックする必要がある.
暗号文に割り算をする idea と近い. invariant なスキーム (e.g., FV スキーム, YASHE スキーム
など)
法は変わらないのでトラックする必要もない
実装面的はシンプル
logL → L
25

初期ノイズのについてO( + n W )n
2
t
2
W
26

技その2：Hamming Weighted Secret Key
秘密鍵はから生成する。かつ where . e.g., とか.
RLWE なスキームで法の円分多項式のを使わないと安全性が問題あり
そうな論文もあったみたい.
e.g.,
sk {0, 1}
n+1
|sk| = W W ? n W = 64
(X)Φm
m = 2
k
+ 1 = (X)X
2
k?1
?
2
k
27

reLinearization (or Key Switching )
28

技その3: reLinearization
掛け算によって暗号文のレングスが増える。
レングスの増加によって、次の準同型演算のコストも増える
そして、掛け算に増加するノイズはこのレングスにも依存する
平文を保持しつつ、レングスを縮む。
レングス 2 の暗号文は canonical form で呼ばれる
ct ( ) ? ct ( ) = ( , , )x1 m1 x2 m2 a
′
b
′
c
′
reLinearization( , , ) → ( , ), ?while?Dec(( , )) →a
′
b
′
c
′
a
′′
b
′′
a
′′
b
′′
m1 m2
29

- レングス 3 の暗号文はどう復号するのか？
main idea: を事前に暗号化して evaluation key に加える
1. Enc( ) = , i.e.,
2. .
3.
ノイズは増加される。
reLinearization( , , ) → ( , ), ?while?Dec(( , )) →a
′
b
′
c
′
a
′′
b
′′
a
′′
b
′′
m1 m2
? + ? sk + ?c
′
b
′
a
′
sk
2
sk
2
sk
2
(α, β) β + α ? sk → sk
2
= + β ? , = + α ?b
′′
c
′
a
′
a
′′
b
′
a
′
+ ? sk = + β ? + ( + α ? ) ? sk = + ? sk + ?b
′′
a
′′
c
′
a
′
b
′
a
′
c
′
b
′
a
′
sk
2
30

計算のステップを見直す
しかしは大きい値 ( ) をとりうるため累積ノイズがかなり増加しまう
bit-decomposition を使う
極端に (i.e., bit-decomposition).
だが時を保存するコストは高すぎ
実装上はなど使う (HElib). あるいは (SEAL)
= + β ? , = + α ?b
′′
c
′
a
′
a
′′
b
′
a
′
α, β Z
n
q
α := , β := , ω ? q∑
k
αkω
k
∑
k
βkω
k
ω = 2
ω = 2 ,αk βk
ω > 2, k = 4 |ω| ≈ 2
16
31

技その3: Key-Switching
暗号文のレングスを 2 に戻るためを暗号化する
もっと一般的な使い方がある. をある鍵での暗号文.
別の鍵の暗号文に変換することができる。
例え
1. (i.e., reLinearization)
2. (i.e., automorphism. homomorphic rotation で使う. まだ議論する)
sk
2
(m)ctxsk
′ sk
′
m
KeySwitch : (m) → (m)ctxsk
′ ctxsk
sk
s =k
′
sk
2
s ( ) = sk(X)k
′
X
j
32

Bootstrapping
復号回路もBCで表示できる。準同型性を使って復号回路を暗号文上で評価する。
from David Wu cs.stanford.edu/~dwu4/papers/XRDSFHE.pdf(https://cs.stanford.edu/~dwu4/papers/XRDSFHE.pdf)
復号鍵を公開鍵を使って暗号化し、boostrapping キーを作る circular security?
33

Bootstrapping 流派
1. RLWE-based なスキーム, e.g., BGV, FV
pros:
bits の平文を暗号化するができる
bootstrapping するまでに -level の回路を評価することができる
cons:
bootstrapping はかなり重い。e.g., 数分単位/一暗号文
2. LWE-based + GSW 方式なスキーム, e.g., TFHE
pros:
1-bit の平文に特化するため bootstrapping は高速. e.g., 0.1sec / 一暗号文
cons:
gate ごとに bootstrapping する必要がある
> 2
L
34

Bootstrapping の困難点
1. 丸めの操作は非線形. 復号関数の深さは厳しい
Cite from "Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits"
2. 法は大きい、e.g., . この暗号文を暗号化するため、もっと大きい FHE パラメー
タが必要
p p ≈ 2
1000
35

Bootstrapping の困難点 (Cont'd)
復号回路を BC 回路で表現する時深さは結構ある
Cite from "Bootstrapping in HElib"
That is, each level multiplication needs one bootstrapping10
36

最速な 1 ビットの bootstrapping (TFHE)
37

Bootstrapping within 0.1sec [TFHE]
メッセジーが二値の LWE 暗号文の bootstrapping
復号回路：
1. 内積はどう計算するのか
2. をどう計算するのか
main idea: GSW方式に経由して高速化
の計算にはの構造をうまく利用する
( , b)a??
|b + | q/4a??
?
s?? >
?
>
?
>
?
+ 1X
n
38

前置き：ベクトル内積と多項式積
length- のベクトル積と法において多項式積は結んでいる
i.e.,
bootstrapping 以外の色々使い道がある
n + 1X
n
= ( × ? )[0] mod + 1a??
?
b
??
∑
n?1
i=0
aiX
i
∑
n?1
j=0
bj X
n?j
X
n
= ?1 mod + 1X
n
X
n
39

もっとも重要なトリック
の定数項 (i.e., )
なら定数項は 0
o.w. 定数項は 1
次はどうを多項式の次数に計算するについて
× (1 + X + ? + ) × × + mod + 1X
β
X
2
X
n?1
X
?n/2
2
?1
2
?1
X
n
??X
0
β > n/2
β = +b
??
a??
?
s?? 40

三種類の暗号文
LWE( ) : (bootstrapping の対象)
RLWE( ): (中間表現役)
GSW( ): (boostrappingキーを暗号化)
m
( , b = m + e ? ), m ∈ {0, 1}? , ∈a?? a??
?
s?? a?? b
??
Z
n?1
q
m
′
( , = + ? )? , , ∈ [X]/( + 1)a
′
b
′
m
′
e
′
a
′
s
′
a
′
s
′
m
′
Zq X
n
m
′
+ H?(H?is a fixed poly matrix?)
?
?
?
?
(0)RLW Es
′
?
(0)RLW Es
′
?
?
?
? m
′
41

TFHE Hack 1: approximate gadget decomposition
多項式ベクトルを分解する.
Decomp: かつ誤差はバンドされる
:= ( , )u?? a
′
b
′
, ∈ [X]/( + 1)a
′
b
′
Zq X
n
? ?s.t.? H ≈u?? v?? v?? u??
43

TFHE Hack 2: External Product
をの LWE 暗号文とする
をの GSW 暗号文とする
Decomp( ) はになる
LW E(m) = ( , b)a?? m ∈ {0, 1}
GSW ( )m
′
∈ [X]/( + 1)m
′
Zt X
n
[0, ]∥ba??
 
多項式と見なす
?GSW ( )m
′
RLW E(m )m
′
44

TFHE Hack 2: External Product
TFHE Hack 3: Extract LWE from RLWE
から定数項をの形で抽出できる。
1. , は秘密鍵
2. 抽出したとする.
3. (次数の逆順と符号 ip).
4. (多項式の定数項)
を復号する時. を計算する
よって
RLW E(m )m
′
LW E(m [0])m
′
RLW E(m ) := ( , = m + ? )m
′
a
′
b
′
m
′
e
′
a
′
s
′
s
′
LW E(m [0]) := ( , d)m
′
c ??
= [? [n ? 1], ? [n ? 2], … , ? [0]]c ?? a
′
a
′
a
′
d = [0]b
′
b
′
( , d)c ?? d + c ??
?
s??
 
( )[0]a
′
s
′
d + = m [0] + [0]c ??
?
s?? m
′
e
′
45

Bootstrapping within 0.1sec
まとめ
1. LWE の秘密鍵をGSWで暗号化. boostrappingキーとする
.
- GSW の鍵は? LWE と異なる鍵を使ったりする（この場合 KeySwitchが必要）
2. boostrapping の対象 LWE の暗号文とする.
2.1 積を計算する。
- 整数を次数に置くこともポイント
- ここではので, の場合
∈ {0, 1s?? }
n?1
bk := {GSW ( )s??i }i
( , b)a?? (|b + | q/4)a??
?
s?? >
?
(H + ? 1) ? GSW ( ) → GSW( )X
a??
i
s??i X
a??
i s ??
i
a??i
∈ {0, 1}s??i
= 1s??i
=X
a??
i
s??i X
a??
i s ??
i 46

まとめ
1. LWE の秘密鍵をGSWで暗号化. boostrappingキー .
2. boostrapping をするLWE の暗号文とする.
2.2 summation を計算する。
Decomp(RLWE ) GSW( ) RLWE( )
- 再帰的に RLWE( ) を計算できる
∈ {0, 1s?? }
n?1
bk := {GSW ( )s??i }i
( , b)a?? (|b + | q/4)a??
?
s?? >
?
(H + ? 1) ? GSW ( ) → GSW( )X
a??
i
s??i X
a??
i s ??
i
∈ {0, 1}s??i
= 1s??i
=X
a??
i
s??i X
a??
i s ??
i
( )X
b
X
a??
i s ??
i
→ X
b+a??
i s ??
i
X
b+a??
?
s ??
47

1. LWE の秘密鍵をGSWで暗号化. boostrappingキー .
- GSW の鍵は?
- LWE と異なる鍵を使ったりする（この場合 KeySwitchが必要）
2. boostrapping をするLWE の暗号文とする.
2.2 summation を計算する。Decomp(RLWE ) GSW( ) RLWE( )
- 再帰的に RLWE( ) を計算できる
2.3 トリック：RLWE(
2.4 定数項を抽出して LWE に戻る
ではなくの rescaling ステップは省略した
ノイズの解析は論文に参考
∈ {0, 1s?? }
n?1
bk := {GSW ( )s??i }i
( , b)a?? (|b + | q/4)a??
?
s?? >
?
(H + ? 1) ? GSW ( ) → GSW( )X
a??
i
s??i X
a??
i s ??
i
∈ {0, 1}s??i
= 1s??i
=X
a??
i
s??i X
a??
i s ??
i
( )X
b
? X
a??
i s ??
i
→ X
b+a??
i s ??
i
X
b+a??
?
s ??
) ? (1 + X + ? + ) ? × +X
b+a??
?
s ??
X
N?1
X
?N/2
2
?1
2
?1
q/4>
?
N/2>
?
48

これから実装っぽいの話です
49

既存のもの
1. HElib by IBM. 最近 Apache 2.0 ライセンスに変わった
- 基本 Shai Halevi さんだけメンテナンスしている. わりと inactive
- 機能はかなりある. mod switch, reLinearization, rotation, boostrapping など
- NTL, GMP などの外部ライブラリーに依存. ビルドはやや大変
2. Simple Encrypted Arithmetic Library (SEAL) by Microsoft. Microsoft のライセンス
- 2-3 人がメンテナンス + インターンを雇っているらしい.
- 機能は上々に増加. rotation -> bootstrapping (まだreleaseされてない)
- 外部の依存なし、out-of-the-box で使える
- 完全openではなくメールを送ってgitの招待をお願いする
3. TFHE
- bootstrapping が一番高速.
- AND, XOR など色々な boolean gate が実装された.
- フランスの大学の学生さん3人がメンテナンス。commentもちょこちょこフランス語
その他：PALISADE by NJIT, Λ ° λ 50

「FHE の計算を早くする」
1. 暗号化した後の optimization
big number の表示
多項式の表示
2. 暗号化する前の optimization
SIMD による平文の前処理
回路的な考え方すると
1 はゲートを早く動かす
2 は良い回路を設計する 51

暗号化した後にやっていること
52

「FHE の計算を早くする」その 1: 大きい法を表現する.
, each
for は co-prime
Residue number system (RNS) でも呼ばれる
Almost parallelizable
[CBHHJLL18] は logistic regression を暗号文上で学習させるためを使った
BigNumber 「できるだけ」使用しない. rounding 操作が必要になる時一回 BigNumber
に戻る.
例え , など
[BEHZ16] は BigNumber に戻らせず rounding を行う方法は SEAL (v2.~) に実装された
(big number free)
q
[X] → [X] × ? × [X]Zq Zq
1
Zq
j
<qj 2
64
i ≠ j? ,qi qj
q ≈ 2
1020
0 < c < q ?c/t?
53

「FHE の計算を早くする」その 2: 多項式掛け算
RLWE-based のスキームでは FFT と NTT を利用して計算を高速化にする
多項式を二つの表現がある
1. シンプルな係数方式 .
SEAL, TFHEなどのライブラリーに採用される
一回掛け算のコスト (Numeric Theoretic Transform)
2. DoubleCRT 方式 (HElibの実装)
の整数行列 ( 回 FFT経由)
掛け算のコストは . (i.e., 行列の要素ごと積)
メモリ使用量は係数方式の倍.
A(X) = ∑ ∈ [X]/( + 1)ai
X
i
Zq
X
n
O(n log n)
A(X) → L × n L
O(Ln)
L
54

暗号する前にやっていること
55

「FHE の計算を早くする」その 3: Single Instruction Multiple Data (SIMD)
によって前処理
SIMD は fan-in が大きいな回路に対する optimization
e.g., お互い独立な batch 処理
暗号化する前にをそれぞれ encode をかける
1. ,
2.
encodeすることによって -fan-in の回路は準同型掛け算は一回で済む
具体的には多項式版の Chinese Remainder Theorem を利用
{ }, { }ak bk
{ } → A → Enc(A)ak
{ } → B → Enc(B)bk
Enc(A) ? Enc(B) → Dec → AB → { ×ak bk }k
k
56

多項式版 CRT
p.s.
A = 8 mod X + 15, A = 5 mod X + 9
A = 16 mod X + 2, A = 9 mod X + 8
→ A = 1 + X + 7 + 12X
2
X
3
[8, 5, 16, 9] ? A ∈ [X]/( + 1)Z17 X
4
+ 1 = (X + 15)(X + 9)(X + 2)(X + 8) mod 17X
4
57

多項式版 CRT
一つの大きい集合を幾つの小さい集合の積集合で合成する
大きい集合において一回の演算(+, x)は同時に個小さい集合に反映する
1.
2.
平文のデータはここのベクトルに想定、暗号化するのは多項式
合成する集合の個数は .
[8, 5, 16, 9] ? A ∈ [X]/( + 1)Z17 X
4
[X]/( + 1) ? ? ? ? (i. e. , ? = 4)Z17 X
4
F1 F2 F?
?
3 × A ? 3 × [8, 5, 16, 9]
? [ , , , ]A
2
8
2
5
2
16
2
9
2
A
? = n/multiplicative order(t, 2n)
58

Deeping in SIMD: rotation
SIMD によって評価するゲート数を削減する
SIMD によって評価するゲート数を削減する
Intersection がある回路は SIMD できない
intersection がある回路は SIMD できない 60

一つの暗号文の中にパッキングされたメッセージを操作したい
1. 例え：extraction.
2. rotation. (2. ができれば、1. はできる)
rotation ができることは SIMD でベクトル内積を計算することができる
Enc([a, b, c]) → Enc([a]), Enc([b]), Enc([c])
Enc([a, b, c]) ? 1 → Enc([b, c, a])
61

ここは automorphism を使う:
例：
1. .
2. ベクトルに戻ると .
- 右方向に2 単位 rotation されたと等価
A(X) → A( ), j ∈X
j
Z
?
n
[8, 5, 16, 9] ?= 1 + X + 7 + 12 ∈ [X]/( + 1)X
2
X
3
Z17 X
4
A( ) = 1 + + 7( + 12( = 1 + 16X + 7 + 5X
5
X
5
X
5
)
2
X
5
)
3
X
2
X
3
1 + 16X + 7 + 5 ? [16, 9, 8, 5]X
2
X
3
[8, 5, 16, 9] ? 2 62

Rotation and KeySwitch
RLWE 暗号文に rotation を適用する
RLWE 暗号文は多項式の tuple
直接多項式を操作することで rotation を行う. .
ほどんとノイズに影響なし
しかし. を復号する時,鍵ではなくを使うべき
よって、異なる o set でrotationされた暗号文間は正しく計算できなさそう
NG:
ctx = (A(X), B(X))
= (A( ), B( ))ctx
′
X
j
X
j
ctx
′
sk(X) sk( )X
j
B(X) + A(X) ? sk(X) = B( ) + A( ) ? sk( )X
j
X
j
X
j
Enc( ) ? 1 ⊕ Enc( ) ? 3M1 M2
63

Rotation and KeySwitch
RLWE 暗号文に rotation を適用する
RLWE 暗号文は多項式の tuple
直接多項式を操作することで rotation を行う. .
ほどんとノイズに影響なし
しかし. を復号する時,鍵ではなくを使うべき
よって、異なる o set でrotationされた暗号文間は正しく計算できなさそう
NG:
を鍵の暗号文と見なし、KeySwitch を使えば, 元鍵の暗号文に
戻れる.
automorphism の後に KeySwitch すれば、異なる o set でrotationされた暗号文間でも
計算可能になる
ctx = (A(X), B(X))
= (A( ), B( ))ctx
′
X
j
X
j
ctx
′
sk(X) sk( )X
j
B(X) + A(X) ? sk(X) = B( ) + A( ) ? sk( )X
j
X
j
X
j
Enc( ) ? 1 ⊕ Enc( ) ? 3M1 M2
ctx
′
(X) := sk( )sk
′
X
j
sk
64

常に一回の automorphism で欲しいな rotation ができることはない
一回の automorphism でどのスロットを動かせるのはから分かる
masking と合わせて任意の rotation はできる
viewing rotation in hybercude
know-how: rotation しやすいのコンビネーションを使う. (コード例あり)
n, t
n, t
65

HElib & SEAL
HElib
- 出身 IBM
- 実装スキーム BGV's leveled homomorphic encryption
SEAL
- 出身 Microsoft
- 実装スキーム FV's somewhat homomorphic encryption
共有点
BigNumber を表現するため RNS を使っている
reLinearization で暗号文のレングスを抑える
相違点
HElib は leveled なスキーム SEAL は invariant なスキーム
HElib は DoubleCRT 方式で多項式を表現する SEAL は係数方式
HElib は一般なをサポートする SEAL は 2のべき乗なのみ
p
?
?
(X)Φm
? m
67

KeyGen/Enc/Dec/ (HElib 篇)
1 FHEcontext context(m, t, /*r =*/1); // Z_t[X]/(Phi_m(X))
2 buildModChain(context, L, /*3*/); // bit-decomposition は 3 桁に分割する
3 FHESecKey sk(context);
4 sk.add
5 sk.GenSecKey(64, /*3*/); // hamming weight = 64, 3乗までのKS matrix が作られる. s^3, s^2 -> s
6 //sk.GenKeySWmatrix(1, j, 0, 0); sk(X^j) -> sk(X) の KS matrix を追加する
7 FHEPubKey pk(sk);
HElib は一般の円分多項式をサポートする. 平文の空間は FHEcontext で定義され
る
buildModChain は Mod-Switch で使う個の modulo を見つける.
1 ZZX plain;
2 Ctxt ctx(pk);
3 pk.Encrypt(ctx, plain); // asymmetric
4
5 Ctxt ctx2(sk);
6 sk.Encrypt(ctx2, plain); // symmetric
7 ZZX plain2;
8 sk.Decrypt(plain2, ctx);
(X)Φm
[X]/( (X))Zt
r Φm
L
68

KeyGen/Enc/Dec/ (SEAL 篇)
1 EncryptionParameters parms;
2 parms.set_poly_modulus("1x^2048 + 1"); // n = 2048
3 parms.set_coeff_modulus(coeff_modulus_128(2048)); // n に応じて kappa = 128-bit のパラメータを探してくれる
4 parms.set_plain_modulus(t); // Z_t[X]/(X^n+1)
5 SEALContext context(parms);
6
7 KeyGenerator keygen(context);
8 PublicKey public_key = keygen.public_key();
9 SecretKey secret_key = keygen.secret_key();
10 EvaluationKeys ev_keys;
11 keygen.generate_evaluation_keys(16, 1, ev_keys); // KS は 16-bit まで分割する. s^2 -> s を作る
12
13 Encryptor encryptor(context, public_key);
14 Evaluator evaluator(context);
15 Decryptor decryptor(context, secret_key);
同じで context を定義する。しかし法はのみ (i.e., は2乗の円分多項式)
操作は Encryptor, Evaluator, Decryptor に経由
1 Plaintext plain;
2 Ciphertext ctx;
3 encryptor.encrypt(plain, ctx);
4 decryptor.decrypt(plain, ctx);
+ 1X
n
m
69

Addition / Multiplication (HElib 篇)
1 void hom_add(Ctxt &c1, Ctxt const& c2) {
2 c1 += c2; // addition
3 // or c1.addCtxt(c2);
4 }
5 void hom_mult(Ctxt &c1, Ctxt const& c2) {
6 c1 *= c2; // multiplication w/o reLinearization,
7 // or c1.multipyBy(c2); // multiplication with reLinearization
8 }
(time costly) reLinearization は何時行うのか調整できる.
1 Ctxt inner_product(std::vector<Ctxt> const& ctx_a,
2 std::vector<Ctxt> const& ctx_b,
3 FHEPubKey const& pk) {
4 Ctxt prod(pk);
5 for (i = 0; i < ctx_a.size(); ++i) {
6 Ctxt tmp(ctx_a[i]);
7 tmp *= ctx_b[i]; // reLinearization なし
8 prod += tmp; // レングス-3の暗号文間の足し算、コストは少し増加
9 }
10
11 prod.reLinearize(); // 最後一回 reLinearize、レングス2に戻れる
12 return prod;
13 }
70

Addition / Multiplication (SEAL 篇)
1 // Ciphertext c1, c2, c3
2 evaluator.add(c1, c2); // c1 = c1 + c2
3 evaluator.multiply(c1, c2); // c1 = c1 * c2
4 evaluator.relinearize(c1, evaluation_key, c3); // c3 = relinearize(c1);
5 evaluator.multiply_plain(c2, plain); // c2 = c2 * plain
掛け算は reLinearization が付いていない. 明確で呼び出し 71

SIMD & Rotation (HElib 篇)
1 const EncryptedArray *ea = context.ea;
2 std::vector<long> vec_a(ea->size()); // ea->size() = ell
3 vec_a[0] = 8; vec_a[1] = 5;
4 vec_a[2] = 16; vec_a[3] = 9; // vec_a = [8, 5, 16, 9]
5 ZZX A;
6 ea->encode(A, vec_a); // A = 1 + X + 7X^2 + 12X^3
7 Ctxt ctx(pk);
8 pk.Encrypt(ctx, A);
9
10 ctx.multiplyBy(ctx);
11 sk.Decrypt(A, ctx);
12 ea->decode(A, vec_a); // vec_a = [64, 25, 196, 81]
Rotation は Automorphism と KeySwitch 両方行う
1 Ctxt tmp1(ctx), tmp2(ctx);
2 ea->rotate(tmp1, 1); // left-rotate
3 ea->rotate(tmp2, -1); // right-rotate
4 tmp1 += tmp2; // 既に Keyswitch 済み
5
6 ctx.automorph(j); // A(X) -> A(X^j)
7 ctx.reLinearize(j); // Keyswitch
8 // tmp1.automorph(j1) += tmp2.automorph(j2) <- NG
72

Good & Bad Parameters for Rotation
のコンビネーションによって rotation の効率が違う
1 // m = 16384, t = 8191
2 FHEcontext context(1683, 8191, 1);
3 ea->size(); // 4096
4 ea->dimension(); // 1
5 ea->rotate(ctx, ?); // 100 rotations took 0.98 sec
6 /*----------------------------------------------*/
7 // m = 16384, t = 40961
8 FHEcontext context(1683, 40961, 1);
9 ea->size(); // 4096
10 ea->numOfGens(); // 2 <-- needs more key-switch and masking
11 ea->rotate(ctx, ?); // 100 rotations took 4.21 sec
試行錯誤で dimension が少ないを探す
m, t
t
73

IO
HElib の暗号文は DoubleCRT フォーマットでのスペースを使う
ネット通信する時、まず係数フォーマットして通信量を削減する.
しかし HElib の IO ルーチンにはこの機能がない。じまいした
1 @https://github.com/fionser/HElib/blob/master/src/DoubleCRT.cpp#L918
2 std::ostream& operator<< (std::ostream &str, const DoubleCRT &d)
3 { ...
4 NTL::ZZX poly;
5 d.toPoly(poly, true); // use iFFT
6 const FHEcontext &context = d.context;
7 double bits = context.logOfProduct(set);
8 bits /= std::log(2.);
9 long bytes = long(std::ceil(bits) + 7) >> 3;
10 long phim = context.zMStar.getPhiM();
11 std::vector<uint8_t> buff(bytes);
12 for (long i = 0; i < phim; i++) {
13 const NTL::ZZ &e = NTL::coeff(poly, i);
14 BytesFromZZ(buff.data(), e, bytes);
15 str.write(reinterpret_cast<char *>(buff.data()), bytes);
16 }
17 ...
18 }
O(Ln)
74

Hack into SIMD (CSS'17 の内容)
目的：暗号化されたベクトルの内積をバッチ的に計算したい. 行列積を計算するため
は他のいい感じの分解ができる
の combination によって , e.g.,
すなわち、サイズ 256 のベクトル４個を一つの多項式にencodeすることができる
1 FHEcontext context(1024 * 2, 137, 1); // Phi_{2048}(X) = X^{1024} + 1
2 const EncryptedArray *ea = context.ea;
3 long ell = ea->size(); // 4
4 long d = ea->getDegree(); // 256
5 std::vector<NTL::ZZX> vectors(ell);
6 // ... fill in vectors
7 // e.g. vectors[0] = 1 + 2X + 3X^2 ... + 256X^{255}
8 NTL::ZZX poly;
9 ea->encode(poly, vectors);
→
+ 1 mod tX
n
n, t + 1 = + mod tX
n
∏
j
X
d
βj
+ 1 = ( + 10)( + 41)( + 96)( + 127) mod 137X
1024
X
256
X
256
X
256
X
256
75

の形にする理由: サイズのベクトルの内積、準同型掛け算一回で済む
を例としましょう.
1.
2. の係数 34 はベクトル内積になる
暗号化する前にベクトルを二通りで encoding すると内積の計算は早くできる
→
+ βX
d
d
+ 4X
3
(1 + 2X + 3 ) × (5 + 6X + 7 ) =. . . +34 mod + 4X
2
X
2
X
2
X
3
X
d?1
[1, 2, 3 [7, 6, 5]]
?
76

ベクトル
4 個の内積 , 準同型掛算一回で計算する (結果の暗号文も一つしかない)
1. encoding I:
2. encoding II:
3.
実際 , によってを調整することができる
1. e.g., ならサイズ 64 のベクトルを 64 個�之挙咿zめる
→
{ , }, 1 ≤ i ≤ 4, | | = | | = 256a??i b
??
i a??i b
??
i
a??
?
i
b
??
i
[ , … ] → A(X)a??1 a??4
[ , … ] → B(X)b
??
1 b
??
4
Enc(A(X)) ? Enc(B(X)) → Dec → decode → { }a??
?
i
b
??
i
n ≥ 4096 t d
n = 4096, t = 82561 77

と組み合わせはどう見つけるのか?
は security level に関連なので given とする。は平文のサイズ. e.g, -bit 以上であれ
ば ok. (https://github.com/OpenSMP/SMP)
1 void DoublePacking(long m, long slots) { // slots 数を指定
2 long t = NTL::NextPrime(1 << 16); // 16-bit 以上
3 long n = phi_N(m); // assert(n * 2 == m)
4 while (true) {
5 long d = multOrd(t, m);
6 long s = n / d;
7 if (s == slots) {
8 FHEcontext context(m, t, 1);
9 const std::vector<NTL::ZZX> &ftrs = context.alMod.getFactorsOverZZ();
10 bool ok = true;
11 for (const auto& f : ftrs)
12 ok &= check(f); // check whether X^d + beta
13 if (ok) // all factors follow the form X^d + beta
14 break;
15 }
16 do { // try next prime
17 t = NTL::NextPrime(t + 2);
18 } while (m % t == 0);
19 }
20 }
n t
n t 16
78

SCIS, AsiaCCS'18 の内容
大小比較
TFHE のトリックと類似
からを作るのにのautomorphism を使う
1 sk.GenKeySWmatrix(1, 2n - 1, 0, 0);
2 ctx.smartAutomorph(2n - 1);// X^b --> X^{-b}
よって one-round な決定木とU 検定の秘密計算プロトコルを作った
Enc( ), Enc( ) → Enc(a b)X
a
X
b
>
?
Enc( ) ? Enc( ) × (1 + X + + ? + ) × +X
a
X
?b
X
2
X
n?1
2
?1
2
?1
Enc( )X
b
Enc( )X
?b
j = 2n ? 1
( = = (?1 mod + 1X
b
)
2n?1
X
2nb?b
)
2b
X
?b
X
n
79

少し展望
TFHE の利点は：パラメータはかなり固定。GPU などの最適化に便利
GSW 方式 (so call 3rd gen FHE) もいい選択肢でしょう。
1. reLinearization が要らない. (so called evaluation key free)
2. mod-switch もなし ( atten, un attenでノイズをコントロール)
3. 暗号文は行列だが、0-1の行列なので、最適化の余地はまだあるでしょう.
m, q
80

References
[BV11a] Brakerski et al. Fully Homomorphic Encryption from ring-LWE and security for
key dependent messages.
[BV11b] Brakerski et al. E cient Fully Homomorphic Encryption from (Standard) LWE.
[BGV11] Brakerski et al. Fully Homomorphic Encryption without Bootstrapping.
[GHS12] Gentry et al. Homomorphic Evaluation of the AES Circuit.
[FV12] Fan et al. Somewhat Practical Fully Homomorphic Encryption
[SV11] Smart et al. Fully Homomorphic SIMD Operations
[BEHZ16] Bajard et al. A Full RNS Variant of FV like Somewhat Homomorphic Encryption
Schemes
[CBHHJLL18] Chen et al. Logistic regression over encrypted data from fully homomorphic
encryption 81

Thank you
@rbklwj(http://twitter.com/rbklwj)
riku@mdl.cs.tsukuba.ac.jp(mailto:riku@mdl.cs.tsukuba.ac.jp)

狠狠撸

FHE in Action

More Related Content

FHE in Action