TFHE実装入門

11.ParameterSelection

松岡 航太郎

  • 準同型暗号においてはSecurityと性能の両方にパラメータの選定が効いてくる
    • 格子暗号に対する攻撃は日々進化し続けている
    • 1年後も同じパラメータを使えるとは限らない
  • TFHEのパラメータの具体的決定法をみることで今後の進歩に対応する
    • 決定法に関する決まったinstructionがあるわけではないことには留意
      • ここで説明する方法は私のやり方
    • 一例と思ったほうがいいかもしれない

lwe-estimator

  • 安全性を推定するためのデファクトスタンダード
    • LWEに対する知られている限りの攻撃法による計算量を評価
    • 更新されるたびにパラメータ変更を要する可能性があると思っていい
      • 最近更新が止まってて怪しい
  • 必要な安全性を満たすための必要条件をこれで最初に探す
    • 他のパラメータを決めてみてうまく行かなかったら戻ってくる

コード(TFHE公式の抜粋)

  • 両方で128を超えるのがとりあえずの目安
    • ここではT(R)LWElvl1を例示する
  • SageMathはインターネットからのloadができなくなったので使えなくなったのでローカルで行うこと
from sage.all import load, sqrt, RR, ZZ, pi, oo
load('https://bitbucket.org/malb/lwe-estimator/raw/HEAD/estimator.py')
n = 1024                 # ciphertext dimension (also, key entropy)
sd = 2**(-25)            # noise standard deviation
alpha = sqrt(2*pi)*sd    # estimator defines noise rate = sqrt(2pi).stdev
q = 2**32                # for compatibility only (通常のLWEはTorusじゃなくて整数係数)
m = oo                   # the attacker can use as many samples he wishes 
secret_distribution = (0,1)
success_probability = 0.99
# Chosen cost model(主に2種類の攻撃パターンがある)
print("CLASSICAL PRIMAL") #LWEの秘密鍵を直接得る攻撃
print(primal_usvp(n, alpha, q, secret_distribution=secret_distribution, m=m, success_probability=success_probability, reduction_cost_model=BKZ.sieve))
print("CLASSICAL DUAL") #乱数と暗号文を識別する攻撃
print(dual_scale(n, alpha, q, secret_distribution=secret_distribution, m=m, success_probability=success_probability, reduction_cost_model=BKZ.sieve))

Primal

  • LWEの秘密鍵を直接得ようとする攻撃
    • LWEをunique Shortest Vector Problem(uVSP)またはBounded Distance Decoding(BDD)などに帰着する
  • mm本の0の暗号文が与えられているとしよう(m>nm>n)
  • A={a0,a1,...,am}∈Zqn×m,b={b0,b1,...,bm}∈Zqm\mathbf{A}=\{\mathbf{a}_0,\mathbf{a}_1,...,\mathbf{a}_m\}∈\mathbb{Z}_q^{n×m},\mathbf{b}=\{b_0,b_1,...,b_m\}∈\mathbb{Z}_q^{m}
  • 問題はarg minsb−AT⋅s(s∈Zqn)s\mathop{\rm arg~min}\limits_{\mathbf{s}}\mathbf{b}-\mathbf{A}^T⋅\mathbf{s}(\mathbf{s}∈\mathbb{Z}_q^{n})s

Dual

  • (一様)乱数と暗号文を識別する攻撃
    • 識別できるということは暗号文に相関があるということ
    • 相関を見つけれた場合情報が漏れる可能性がある
  • Primalより弱いようにも見えるが簡単とは限らない
  • 問題としてはA⋅v=0\mathbf{A}⋅\mathbf{v}=\mathbf{0}となるv∈Zqm\mathbb{v}∈\mathbb{Z}_q^mで短い非零ベクトルを探す
    • 余談: v\mathbf{v}の非零要素の最小個数はspark(A)\mathrm{spark}(A)とかかれる
    • 余談: 圧縮センシング的な問題である
  • 見つかったらv⋅b\mathbf{v}⋅\mathbf{b}を計算して値が十分小さければv\mathbb{v}の非零要素に対応する暗号文は乱数でないと判定できる
  • ∵b=AT⋅s+e\mathbf{b}=\mathbf{A}^T⋅\mathbf{s}+\mathbf{e}よりv⋅b=v⋅e\mathbf{v}⋅\mathbf{b}=\mathbf{v}⋅\mathbf{e}でe\mathbf{e}は暗号文に対応するものは正規分布から来ているはず

量子コンピュータ

  • LWE暗号はポスト量子コンピュータ暗号の候補である
    • しかし量子コンピュータの方が探索に関して強いのは変わらない
    • 単に現時点で特別効率的なアルゴリズムがないだけ
  • lwe-estimatorは量子アルゴリズムに対する耐性も推定できる

パラメータとノイズ

  • LWEはノイズがあるので準同型演算によってノイズが増える
    • ノイズが多すぎると暗号文が壊れる
  • 高速なパラメータはノイズの増加を伴うことが多い
    • ∴ ノイズの増加量とパフォーマンスを天秤にかける必要がある
  • 以降TFHEのBootstrappingにおけるノイズの評価式を構成していく
    • 許容できる誤り確率をきめてそれを満たすノイズの範囲でパラメータを調整する
  • メッセージの間隔の半分をwwとすると、誤差が±w± wを超える確率が誤り確率
    • メッセージから±w± wのものはそのメッセージに丸められる
    • HomNANDの範囲だとw=18w=\frac{1}{8}とすれば良い
  • ※誤り確率がどれくらいなら許容されるかの標準的回答はない
    • たぶん10−4010^{-40}ぐらいでまず十分かと個人的には思っている

正規分布の性質

  • 正規分布の確率密度関数: f(X)=12πσ2exp⁡(−(X−μ)22σ2)f(X)=\frac{1}{2\pi\sigma^2}\exp(-\frac{(X-μ)^2}{2\sigma^2})
  • 定数倍: Y=aX,dXdY=1a,f(Y)=f(X)dXdY=12πσ2exp⁡(−(Ya−μ)22σ2)1a=12πa2σ2exp⁡(−(Y−aμ)22a2σ2)Y=aX,\frac{\mathrm{d}X}{\mathrm{d}Y}=\frac{1}{a},f(Y)=f(X)\frac{\mathrm{d}X}{\mathrm{d}Y}=\frac{1}{2π \sigma^2}\exp(-\frac{(\frac{Y}{a}-μ)^2}{2\sigma^2})\frac{1}{a}=\frac{1}{2π a^2\sigma^2}\exp(-\frac{(Y-aμ)^2}{2a^2\sigma^2})
  • 正規分布の積率母関数: E[etX]=eμt+σ22E[e^{tX}]=e^{μt+\frac{σ^2}{2}}
  • 再生産性: E[et(X+Y)]=E[etX]E[etY]=e(μX+μY)t+σX2+σY22E[e^{t(X+Y)}]=E[e^{tX}]E[e^{tY}]=e^{(μ_X+μ_Y)t+\frac{σ_X^2+σ_Y^2}{2}}

ノイズの取り扱い方

  • 正規分布の平均は平文のことなので考える必要はない
  • 正規分布の性質から、正規分布については分散だけ知っていれば良い
  • 丸めなどのために一様分布も出てくる
    • これはその幅と加わる個数の２つを追っかける必要がある
      • 違う幅のものは個別に追っかける必要がある

External Productのノイズ

  • 加算のノイズは自明なので省略
    • Decompositionによる丸め誤差をϵ=12Bglϵ=\frac{1}{2Bg^l}、TRLWElvl1の誤差の標準偏差をαα、TRGSWの標準偏差をαbkα_{bk}
  • 正規分布の分散は2lN(Bg2)2αbk2+∣∣μ[X]∣∣2α22lN(\frac{Bg}{2})^2α_{bk}^2+||μ[X]||^2α^2で抑えられる
    • 第1項は係数の絶対値がBg2\frac{Bg}{2}以下のNN次多項式が零の暗号文の行列にかかることによる分散
    • 第2項はTRLWEのノイズがTRGSWの平文によってどれだけ増幅されるか
  • これに加えて[−∣∣μ[X]∣∣1ε,∣∣μ[X]∣∣1ε][-||μ[X]||_1 ε, ||μ[X]||_1 ε]に値をとる一様分布が(1+N)(1+N)個加わる
    • 適切な暗号文はほぼ一様乱数に見えるので丸め誤差も一様分布になる
    • Decompositionによるノイズが復号時にどれだけ増幅されるか

CMUXのノイズ

  • ほぼExternal Productと一緒の結果になる
    • 明らかに∣∣μ[X]∣∣2=1||μ[X]||^2=1
  • 入力となるTRLWEの標準偏差で大きい方をααとする
    • 本当は選択される方だけが影響を及ぼすが上から抑えたいので
  • 正規分布の分散: 2lN(Bg2)2αbk22lN(\frac{Bg}{2})^2α_{bk}^2
  • 一様分布: 幅ϵ\epsilonが1+N1+N個

Blind Rotateのノイズ

  • HomNANDの範囲ではTest Vectorはノイズを含まない
    • XXのべき乗を掛けるのはノイズを増やさない
    • nn回CMUXをする
  • 正規分布の分散: n(2lN(Bg2)2αbk2)n(2lN(\frac{Bg}{2})^2α_{bk}^2)
  • 一様分布: 幅ϵ\epsilonがn(1+N)n(1+N)個

Identity Key Switching

  • 入力となるTLWElvl1のノイズをααとする
  • 正規分布の分散: α+Ntαksα+Ntα_{ks}
    • 第2項は合計NtNt個のTLWElvl0を足すことから
  • 一様分布: 幅2−(t∗basebit+1)2^{-(t*basebit+1)}がNN個
    • 整数に丸める際の丸め誤差の影響を表している

Gate Bootstrapping

  • 今まで出てきたものをすべて足せばいい
  • 正規分布の分散: n(2lN(Bg2)2αbk2)+Ntαks2n(2lN(\frac{Bg}{2})^2α_{bk}^2)+Ntα_{ks}^2
  • 一様分布: 幅ϵ\epsilonがn(1+N)n(1+N)個と幅2−(t∗basebit+1)2^{-(t*basebit+1)}がNN個

Blind RotateでのRounding

  • Blind Rotateでは入力を2N2N倍して丸める
  • つまり[−14N,14N][-\frac{1}{4N},\frac{1}{4N}]の一様分布が各係数に加わる
    • 複合した結果を考えるのでn+1n+1個加わる
  • このノイズを加算した状態での復号が成功しないとBootstrappingが誤る

誤り確率の推定方法

ここでは3つの方法を紹介する

  1. 一様分布を正規分布で置き換える方法(ラフな近似)
  2. Chernoff-Cramer Bound(厳密な上界)
  3. 重点サンプリング(数値的方法)

一様分布を正規分布で置き換える方法

  • TFHEの原著論文で使われている方法
  • 一様分布をその幅の2乗の分散の正規分布に置き換える
    • 1σ1σの中に一様分布を入れている
    • 一様分布の分散の３倍
      • 備考: 一様分布の和の分布はIrwin-Hall分布という
    • 正当性は不明
  • すべての誤差が正規分布なら分散を足して一つの正規分布とみなせる
    • 正規分布に従う確率変数がある幅±w± wに収まる確率は誤差関数erf\mathrm{erf}を用いてerf(wσ2)\mathrm{erf}(\frac{w}{\sigma\sqrt{2}})
    • 1−erf1-\mathrm{erf}は精度の都合上erfc\mathrm{erfc}として別関数になっている
      • Scipyとかに実装がある

Chernoff Cramer Bound

  • よくCC boundと書かれる
  • 確率分布のtail-boundを上から抑える不等式
    • tightな結果が出てくることが多いので格子暗号系ではよく使われるらしい
      • 鍵交換のNewHopeには実際に出てくる
    • Markov不等式から導出できる
    • 実際に求めたい値はこれの２倍(対称な分布なので)

X=∑iXi,Pr(X≥w)=Pr(etX≥etw)≤min⁡t>0e−tw∏iE[etXi]X=\sum_i X_i, \mathrm{Pr}(X≥ w)=\mathrm{Pr}(e^{tX}≥ e^{tw})≤ \underset{t>0}{\min} e^{-tw}\prod_i E[e^{tX_i}]

  • 和に出てくる分布の積率母関数をかけてttについて最適化を施す
    • かなり変な形になるので大域的最適化を考えたほうが良い
    • 対数をとったほうが良いと思う

重点サンプリングの発想

  • CC Boundの計算があっているか調べるのに良さそうと思っているが試してない
  • 対称となる分布をp(X)p(X)、関数をf(X)f(X)とする
    • 求めたいのは∫f(X)p(X)dX∫ f(X)p(X)\mathrm{d}X、つまりf(X)f(X)の期待値
    • f(X)f(X)をww以上の時1でそうでなければ0とすればtail-bound
  • p(X)p(X)からサンプルするとf(X)f(X)の値が大きいところをほぼサンプルできない場合がある
    • tail-boundの場合はまさにそう
  • f(X)f(X)の値が大きいXXをとりやすい提案分布q(X)q(X)を考えてそこからサンプルする

重点サンプリングの計算法

  • サンプル数をLL、q(X)q(X)からのサンプルをX(l)X^{(l)}とする
  • 近似の精度は当然q(X)q(X)のとり方に依存する
    • 良い提案分布の形については調査中

∫f(X)p(X)dX=∫f(X)p(X)q(X)q(X)dX≈1L∑f(X(l))p(X(l))q(X(l))∫ f(X)p(X)\mathrm{d}X = ∫ f(X)\frac{p(X)}{q(X)}q(X)\mathrm{d}X ≈ \frac{1}{L}∑ f(X^{(l)})\frac{p(X^{(l)})}{q(X^{(l)})}

よりtightな推定をするために必要なこと

  • 正規分布も一様分布も連続なものとして扱っている
    • 実際は剰余環上の離散分布なのでそのことを考慮する必要がある
    • この講義では連続な正規分布を四捨五入して離散正規分布を得ているのでそのことの考慮も必要
      • somewhat unnatural “rounded Gaussian” errorGMPW20が増える
        • この変な誤差がちゃんと安全性の証明と合致しているかも本当は考えないといけない
      • Pei10だと正規分布の丸めをランダムにしている
        • これはこれで一様分布の誤差が入る
      • 離散正規分布を直接サンプルする方法もある

パフォーマンスからみたパラメータ選定の基本

  • 多項式乗算を出来る限り避ける
    • llは可能な限り小さいほうがよくn,Nn,Nも小さいに越したことはない
  • ttも小さいほうがいいがそんなに影響しない
    • basebitbasebitはあまり大きくするとメモリアクセスが足を引っ張る

参考文献

参考文献

page_number: true