TFHE実装入門
3.TRGSW & CMUX
松岡 航太郎
説明内容のHomNANDでの位置づけ
CMUXは次回説明するBlind Rotateで中心的役割を果たす
TRGSWとは
Torus Ring-GSWの略
GSWは考案者のCraig Gentry, Amit Sahai, and Brent Watersの頭文字を取ったもの
GSWは完全準同型暗号の一種で、それをTorus係数多項式に拡張したのがTRGSW
TRGSWを理解することがTFHEを理解する上で特に重要
整数多項式対角行列とTRLWEの積
いきなりTRGSWの具体的構成をみてもモチベーションがわからない
TRGSWを使ってやりたい演算を構成していくことでTRGSWを導出する
以下のような演算を復号せずにやりたい(準同型暗号上の多項式乗算)
加法ができることは既に見ている
簡単のためここでは を仮定する
この行列の部分をどうにかして暗号文にしたのがTRGSW
スケーリング
TRGSWの構成には3つ重要なアイデアがあり、1つがスケーリング
TFHEで考える暗号文は整数係数多項式をそのまま平文にすることはできない
行列の方をTorus係数にしてその分をTRLWEに押し付けて整数係数に丸める
は丸めによるノイズ
ノイズが 倍されることに留意
零行列加算
行列に0を暗号化したTRLWEを加算することで行列を隠す(暗号文でマスクする)
足した後の行列はTRLWEのベクトルとして解釈できる
は0を暗号化したTRLWE
つまり、
0の暗号文を定数倍し足しても0の暗号でノイズが増えるだけ
何をしているか
スペースの都合でこれは
に関するトレードオフ
の係数の最大値は
つまり を大きくすると0の暗号文由来のノイズが大きく影響する
しかし を小さくすると丸めによるノイズが大きくなる
このトレードオフから逃れるのがDecomposition
Decomposition(一般的定義)
TRLWEを丸めるときに を基数とみなして 桁に分解する
Decompositionは多項式 を入力にとる
出力として多項式のベクトル を返す
要素となる多項式の係数は入力となる多項式の係数の一桁を抜き出したもの
Torusを 進表現したときの1番上の桁を集めたもの、次の桁という具合でベクトルの要素は並ぶ
は を満たすとする
を 次の係数が である多項式とする
多項式のベクトル の 番目の要素を として返す
Decompositionでつくるもの
逆操作を先に見ることでイメージを得よう
は の場合のDecompositionになっている
Decomposition(具体的構成)
を具体的に与えるアルゴリズムを示していく
簡単のため と書ける場合に限定する
Torusはuint32_tで表現されているものとする
だと係数が負になる場合を考える必要がある
各桁に をたすことで にずらす
こうするとbitマスクで取り出すだけで良くなる
最後に各係数から を引いて元に戻す
Decomposition(基本的アイデア)
前提としてもし各桁を の範囲で取るならmaskだけで良い
にとる場合を とする
つまりᵢ
は四捨五入のための定数
これは を満たす
か ら を経由した への変換を考える
以下のような関係が成り立つように を決めることができる(要は桁上がりをしている)
Decomposition(疑似コード)
このアイデアをナイーブに実装した場合の疑似コードを示そう
やっていることはほぼ繰り上がり計算なので加算機にそれを任せる最適化が可能だが複雑になりすぎるのでここでは説明しない
Torusは32bit固定小数点表現されていることを仮定している
Decomposition(a[X])
roundoffset = 1 << (32 - l * Bgbit - 1)
for i from 1 to l
for j from 0 to N-1
âᵢⱼ=(((aⱼ+roundoffset)>>(32-Bgbit*i))&(Bg-1))
for i from l to 1
for j from 0 to N-1
if âᵢⱼ ≥ Bg/2
āᵢⱼ = âᵢⱼ - Bg
â₍ᵢ₋₁₎ⱼ += 1
else
āᵢⱼ = âᵢⱼ
return 𝐚̄[X]
TRGSWの具体的構成(平文が の場合)
DecompostionをTRLWEに施して掛け算をすると考えると の暗号文は以下
に関するトレードオフ
を増やせば丸めのノイズを減らすことができる
を増やすと0の暗号文由来のノイズが増える
は丸めには指数で効き0の暗号文由来には線形で効く
を増やすほどExternal Productの多項式乗算が増えて重くなる
トレードオフの出方が と違う
External Product
TRLWEとTRGSWの積のこと
TRGSWを として の場合を書く( は の略記)
ちなみにInternal ProductはTRGSW同士の積を指すが使わないので省略
CMUX
Controlled MUXの略らしい
External Productを使うことで、マルチプレクサを作ることができる
TRGSW( )の平文空間を とする
TRGSWの平文が0なら 、1なら が選ばれる
CMUXをするたびにノイズが増えるので回数には制限がある
これだけでもWeighted Finite Automataが作れたりするが省略
TRGSWのパラメータについて
はTRLWEと一致しないといけないことに注意
ノイズも一致させるほうが簡単(独立にしてはいけないわけではない)
実は でも良い可能性がある
現時点でこちらのパラメータのほうが高速であるといい切れていない
Decompositionがなくなって実装は簡単になるのでこちらをまずは採用するとよいかも
実は に適用する と に適用する は別にすると良いことが知られている
TRGSWの行ごとの平文に相関があることを利用した攻撃は知られていない
現状の安全性は行毎のTRLWEの安全性で評価(結局Integer LWEに落ちる)
TRGSWで最低限実装すべきもの
平文を としたTRGSWの暗号化(復号は必要ない)
External Product
CMUX
Previous slide Page 1 of 19 Next slide Toggle fullscreen Open presenter view