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
)
に値をとる
2つの値域のどちらを使うのが良いかは状況によって変わる
定義より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
)に値をとるが、TLWEでは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
とする
TLWEの暗号文は
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要素のベクトルである
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とは
名前にあるとおり、Errorが重要な役割を果たす
mがわかっている暗号文が好きなだけ手に入るとき(IND-CPA)Errorがないと、手に入った暗号文の
a
\mathbf{a}
a
を並べた行列の逆行列を計算すれば秘密鍵がわかってしまう
Errorがあると単純な逆行列の問題からずれ、Errorが大きいほど難しくなる
行列のサイズが大きい程難しいともいえるので
n
n
n
も安全性に寄与する
LWEへの具体的攻撃法は「格子暗号解読のための数学的基礎」がよい
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
となっているので、足し算ができる回数には限界がある
誤差が大きすぎると復号を誤る確率が大きくなる
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の実装法
実数の小数部の集合なので、素直に考えると倍精度浮動小数点数で実装したくなる
ただ、倍精度浮動小数点数で
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
=
630
n=630
n
=
630
,
α
=
2
−
15
α=2^{-15}
α
=
2
−
15
、固定小数点の幅は32bit
TLWEの安全性はLWEの安全性の問題に帰着されるので、LWE用の推定方法がつかえる
LWE Estimatorがデファクトスタンダード(
https://bitbucket.org/malb/lwe-estimator/src/master/
)
推定のコードはここ(
https://tfhe.github.io/tfhe/security_and_params.html
)
乱数生成について
暗号の安全性は乱数の質に大きく左右される
メルセンヌ・ツイスタを用いてはいけない(ポケモンの乱数調整)
原論文著者実装では使っているが真似してはいけない
一番安全なのはOSが提供する乱数を使うこと(Linuxなら/dev/urandom)
暗号学的に安全性が担保された疑似乱数をCSPRNGという
Cryptographically Secure PseudoRandom Number Generator の略
TFHEppでは
Randen
を使っている
TLWEで最低限実装するもの
HomNANDを作るのに必要なだけを挙げるのでより汎用的に作るかどうかは設計思想に任せる
平文をバイナリに限定した場合の暗号化と復号さえ実装できればいい
暗号文同士の加算は後で使うので、ベクトルっぽい加算がしやすいようにデータを保持しておくと良い
パラメータは後で簡単に変更できるように書いておいた方が汎用性は高い
page_number: true