Previous slide
Next slide
Toggle fullscreen
Open presenter view
TFHE実装入門
1.TLWE
松岡 航太郎
説明内容のHomNANDでの位置づけ
lvl1は次回説明するので今回はTLWEといえばlvl0のこと
TLWEとは
Torus Learning With Errorの略
Torus版のLWE暗号という意味
LWEについては簡単に後述
Torusの直感的定義
日本語で言うと円周群のこと。
T
\mathbb{T}
T
とかく。
時計の針の角度をイメージすると良い
具体的な数字としては針の角度を2πで割ったもの
Torusとは
ここでは、
R
m
o
d
1
\mathbb{R} \bmod 1
R
mod
1
を定義とする。つまり、実数の小数部分で、
[
0
,
1
)
[0,1)
[
0
,
1
)
または
[
−
0.5
,
0.5
)
[-0.5,0.5)
[
−
0.5
,
0.5
)
に値をとる
理論を理解する上では
[
−
0.5
,
0.5
)
[-0.5,0.5)
[
−
0.5
,
0.5
)
だけでもよい
[
0
,
1
)
[0,1)
[
0
,
1
)
は実装上効率が良い場合が在る
Torus同士の乗算は定義されないが、加算は定義できる
加算の例:
0.8
+
0.6
=
1.4
≡
0.4
m
o
d
1
,
0.3
−
0.9
=
−
0.6
≡
0.4
m
o
d
1
0.8+0.6=1.4≡0.4 \bmod 1,0.3-0.9=-0.6 ≡ 0.4 \bmod 1
0.8
+
0.6
=
1.4
≡
0.4
mod
1
,
0.3
−
0.9
=
−
0.6
≡
0.4
mod
1
乗算が定義できない。例:
1.2
≡
0.2
m
o
d
1
,
2.4
≡
0.4
m
o
d
1
1.2≡0.2 \bmod 1,2.4≡0.4 \bmod 1
1.2
≡
0.2
mod
1
,
2.4
≡
0.4
mod
1
なので、乗算が定義できるなら
1.2
⋅
2.4
=
2.88
≡
0.2
⋅
0.4
=
0.08
m
o
d
1
1.2⋅ 2.4=2.88≡0.2⋅0.4=0.08\bmod 1
1.2
⋅
2.4
=
2.88
≡
0.2
⋅
0.4
=
0.08
mod
1
だが成立しない。
整数(
Z
\mathbb{Z}
Z
)との乗算は定義できる。例:
3
⋅
0.4
≡
0.2
m
o
d
1
3⋅ 0.4≡ 0.2 \bmod 1
3
⋅
0.4
≡
0.2
mod
1
モジュラー正規分布
TFHEの原論文だとModular Gaussian Distribution。
通常の正規分布のサンプルは実数(
R
\mathbb{R}
R
)に値をとるが、これはTorusに値をとる
離散ガウス分布は整数に丸めるがこれはTorus
正規分布のサンプルを
m
o
d
1
\bmod 1
mod
1
したものがモジュラー正規分布
TLWEの具体的構成(平文がTorusな場合)
B
=
{
0
,
1
}
\mathbb{B}=\{0,1\}
B
=
{
0
,
1
}
で、バイナリの値の集合。
B
⊂
Z
\mathbb{B}⊂ \mathbb{Z}
B
⊂
Z
暗号の安全性を決めるパラメータは２つで
n
∈
Z
+
,
α
∈
R
+
n∈\mathbb{Z}^+,α∈\mathbb{R}^+
n
∈
Z
+
,
α
∈
R
+
U
T
n
U_{\mathbb{T}^n}
U
T
n
を
T
\mathbb{T}
T
から
n
n
n
個の値を独立にとる一様分布とする
D
T
,
α
\mathcal{D}_{\mathbb{T},α}
D
T
,
α
を平均
0
0
0
標準偏差
α
α
α
のモジュラー正規分布とする
a
∈
T
n
,
e
,
b
∈
T
,
s
∈
B
n
,
m
∈
T
\mathbf{a}∈ \mathbb{T}^n, e,b∈ \mathbb{T}, \mathbf{s}∈ \mathbb{B}^n,m∈ \mathbb{T}
a
∈
T
n
,
e
,
b
∈
T
,
s
∈
B
n
,
m
∈
T
とする
m
m
m
が平文、
a
←
U
T
n
\mathbf{a}←U_{\mathbb{T}^n}
a
←
U
T
n
,
e
←
D
T
,
α
e←\mathcal{D}_{\mathbb{T},α}
e
←
D
T
,
α
,
s
←
U
B
n
\mathbf{s}←U_{\mathbb{B}^n}
s
←
U
B
n
とする
暗号文は
b
=
a
⋅
s
+
m
+
e
b=\mathbf{a}⋅ \mathbf{s}+ m +e
b
=
a
⋅
s
+
m
+
e
として、
(
a
,
b
)
(\mathbf{a},b)
(
a
,
b
)
という
n
+
1
n+1
n
+
1
要素のベクトル
b
−
a
⋅
s
=
m
+
e
b-\mathbf{a}⋅\mathbf{s}=m+e
b
−
a
⋅
s
=
m
+
e
なので、
e
e
e
を削除する方法を加えると
m
m
m
がとれ復号できる
n
,
α
n,α
n
,
α
を大きくすればするほど安全(
α
α
α
は大きくしすぎると暗号文が壊れる)
LWEとは
よく使われるのはTorusではなく剰余環に値をとるInteger LWE
これの拡張が耐量子暗号の候補として
NIST Round3
まで生き残っている
名前にあるとおり、Errorが重要な役割を果たす
平文がわかっている暗号文が好きなだけ手に入るとき(IND-CPA)Errorがないと、手に入った暗号文の
a
\mathbf{a}
a
を並べた行列の逆行列を計算すれば秘密鍵がわかってしまう
Errorがあると単純な逆行列の問題からずれ、Errorが大きいほど難しくなる
行列のサイズが大きい程難しいともいえるので
n
n
n
も安全性に寄与する
具体的攻撃法は「格子暗号解読のための数学的基礎」がよい
kurenaifさんが
動画
出してる
Visual Image(暗号化によるノイズ)
平文
ノイズを加えた場合
強調して書いてはいるが、復号が誤る確率は0ではない(実用的には無視できる)
TLWEの加法準同型性
２つの暗号文
(
a
1
,
b
1
)
,
(
a
2
,
b
2
)
(\mathbf{a}_1,b_1),(\mathbf{a}_2,b_2)
(
a
1
,
b
1
)
,
(
a
2
,
b
2
)
を考え、その和を
(
a
1
+
a
2
,
b
1
+
b
2
)
(\mathbf{a}_1+\mathbf{a}_2,b_1+b_2)
(
a
1
+
a
2
,
b
1
+
b
2
)
とする
b
1
+
b
2
−
(
a
1
+
a
2
)
⋅
s
=
m
1
+
m
2
+
e
1
+
e
2
b_1+b_2-(\mathbf{a}_1+\mathbf{a}_2)⋅\mathbf{s}=m_1+m_2+e_1+e_2
b
1
+
b
2
−
(
a
1
+
a
2
)
⋅
s
=
m
1
+
m
2
+
e
1
+
e
2
になり、
m
1
+
m
2
m_1+m_2
m
1
+
m
2
が出てくるので加法準同型になっていることが分かる
誤差も
e
1
+
e
2
e_1+e_2
e
1
+
e
2
となっているので、足し算ができる回数には限界がある
誤差が大きすぎると復号を誤る確率が大きくなる
Bootstrapping
準同型暗号上で復号関数を評価することでエラーを除去する操作のこと
Gentryさんはこれを最初に提案し、構成を与えた
現状の完全準同型暗号は全てこれによって構成されている
TFHEではBlind Rotateという操作がほぼBootstrapingのこと
TLWEの具体的構成(平文がバイナリな場合)
m
∈
B
,
μ
=
1
/
8
∈
T
m∈ \mathbb{B},μ=1/8\in\mathbb{T}
m
∈
B
,
μ
=
1/8
∈
T
とする。
μ
(
2
⋅
m
−
1
)
∈
T
μ(2⋅ m-1)∈\mathbb{T}
μ
(
2
⋅
m
−
1
)
∈
T
である
TLWEの暗号文は
b
=
a
⋅
s
+
μ
(
2
⋅
m
−
1
)
+
e
b=\mathbf{a}⋅ \mathbf{s}+μ(2⋅ m-1)+e
b
=
a
⋅
s
+
μ
(
2
⋅
m
−
1
)
+
e
復号は
(
1
+
s
g
n
(
b
−
a
⋅
s
)
)
/
2
(1+\mathit{sgn}(b-\mathbf{a}\cdot\mathbf{s}))/2
(
1
+
sgn
(
b
−
a
⋅
s
))
/2
である。(
s
g
n
\mathit{sgn}
sgn
は符号関数)
復号のときには
T
=
[
−
0.5
,
0.5
)
\mathbb{T}=[-0.5,0.5)
T
=
[
−
0.5
,
0.5
)
になっている
Visual Image(ノイズ無しでの加算)
Visual Image(ノイズありでの加算)
バイナリ演算のアイデア
Torusにエンコードされた平文は{-1/8,1/8}
２つのTLWEを足したものの平文は{-1/4,0,1/4}
これを
(
0
,
1
/
8
)
(\mathbf{0},1/8)
(
0
,
1/8
)
から引くと{-1/8,1/8,3/8}
-1/8になるのは両方の暗号文がバイナリの平文として1のとき
3/8は両方0、1/8は２つが異なる
この暗号文を復号すると、負符号のものは0に、正符号は1になる
つまり、両方1の暗号文を入力としたときだけ0になるのでNANDになっている
Remark: Bootstrappingは暗号上で復号を評価する
Torusの実装法
実数の小数部の集合なので、素直に考えると倍精度浮動小数点数で実装したくなる
ただ、倍精度浮動小数点数で
m
o
d
1
\bmod 1
mod
1
の計算をするのは重い
そこで、小数点が最上位bitの前にあるような固定少数点数を用いることにする
例:8bit幅の場合、
0.5
0.5
0.5
は
0
b
1000000
0b1000000
0
b
1000000
、
0.375
0.375
0.375
は
0
b
01100000
0b01100000
0
b
01100000
になる
この方法だと加算や乗算で出た整数部分はオーバーフローで捨てられるので剰余演算が要らない
例:8bit幅の場合、
0.5
+
0.625
m
o
d
1
=
0
b
1000000
+
0
b
10100000
=
0
b
0010000
=
0.125
m
o
d
1
0.5+0.625 \bmod 1=0b1000000+0b10100000=0b0010000=0.125 \bmod 1
0.5
+
0.625
mod
1
=
0
b
1000000
+
0
b
10100000
=
0
b
0010000
=
0.125
mod
1
固定小数点数の幅は
e
e
e
が十分に表現できる程度の幅であれば良い
つまりモジュラー正規分布の標準偏差によって十分な幅が決まる
実数とトーラスの変換の実装
モジュラー正規分布の実装には実数とTorusの変換が必要
理想的には実数の小数部分を取り出す操作
実数の整数部を取り出す操作を
i
n
t
(
)
\mathrm{int}()
int
(
)
、固定小数点の幅を
w
w
w
、入力となる実数を
d
d
d
とする
実数の小数部分を取り出すだけなら、
d
m
o
d
1
d \mod{1}
d
mod
1
でよい
実際には固定幅の固定小数点にしたいので、実数の上から
w
w
w
桁の部分を整数として取り出す
実装したい操作を数式で書くと以下のようになる
i
n
t
(
(
d
m
o
d
1
)
⋅
2
w
)
\mathrm{int}((d \mod{1})⋅2^w)
int
((
d
mod
1
)
⋅
2
w
)
TLWEのパラメータについて
この講義ではパラメータ128bit securityと現在推定されている値を紹介する
n
=
635
n=635
n
=
635
,
α
=
2
−
15
α=2^{-15}
α
=
2
−
15
、固定小数点の幅は32bit
TLWEの安全性はLWEの安全性の問題に帰着されるので、LWE用の推定方法がつかえる
Torusで理論は説明するが実装は
2
32
2^{32}
2
32
を法とした剰余環
剰余環とどちらが本質か？(たまに悩んでいる)
LWE Estimator
がデファクトスタンダード
推定のコードは
ここ
乱数生成について
暗号の安全性は乱数の質に大きく左右される
メルセンヌ・ツイスタを用いてはいけない(ポケモンの乱数調整)
原論文著者実装では使っているが真似してはいけない
一番安全なのはOSが提供する乱数を使うこと(Linuxなら/dev/urandom)
暗号学的に安全性が担保された疑似乱数をCSPRNG(Cryptographically Secure PseudoRandom Number Generator)という
TFHEppでは
Randen
を使っている
TLWEで最低限実装するもの
HomNANDを作るのに必要なだけを挙げるのでより汎用的に作るかどうかは設計思想に任せる
平文をバイナリに限定した場合の暗号化と復号さえ実装できればいい
暗号文同士の加算は後で使うので、ベクトルっぽい加算がしやすいようにデータを保持しておくと良い
パラメータは後で簡単に変更できるように書いておいた方が汎用性は高い
page_number: true