TFHE実装入門

8.Parameter Selection

松岡　航太郎

Security Parameter

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

lwe-estimator

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

コード(TFHE公式の抜粋)

  • 両方で128を超えるのがとりあえずの目安
# To reproduce the estimate run this snippet on http://aleph.sagemath.org/
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\mathbb{A}⋅\mathbb{v}=\mathbf{0}となるv∈Zqm\mathbb{v}∈\mathbb{Z}_q^mで短い非零ベクトルを探す
  • 見つかったらv⋅b\mathbf{v}⋅\mathbf{b}を計算して値が十分小さければv\mathbb{v}の非零要素に対応する暗号文は乱数でないと判定できる
  • ∵b=AT⋅s+e\mathbf{b}=\mathbf{A}^T⋅\mathbf{s}+\mathbf{e}よりv⋅b=b⋅e\mathbf{v}⋅\mathbf{b}=\mathbf{b}⋅\mathbf{e}でe\mathbf{e}は短いベクトル

量子コンピュータ

  • LWE暗号はポスト量子コンピュータ暗号の候補である
  • しかし量子コンピュータの方が強いのは変わらない
  • lwe-estimatorは量子アルゴリズムに対する耐性も推定できる

パラメータとノイズ

  • LWEはノイズがあるので準同型演算によってノイズが増える
  • ノイズが多すぎると暗号文が壊れる
  • 高速なパラメータはノイズの増加を伴うことが多い
  • ∴ ノイズの増加量とパフォーマンスを天秤にかける必要がある
  • 以降TFHEのBootstrappingにおけるノイズの評価式を構成していく
  • 許容できる誤り確率をきめてそれを満たすノイズの範囲でパラメータを調整する
  • 評価においてはノイズは分散として扱う
  • メッセージの間隔の4分の1をww、分散をσ2σ^2とすれば誤り確率はerfc(w2σ)\rm{erfc}(\frac{w}{\sqrt{2}σ})
  • 半分ではなく4分の1なのはHomNANDなどを処理するときに２つを足すことになるので、そのときに誤る確率を計算しているから
  • TFHEの現論文に従うならw=116w=\frac{1}{16}とすれば良い

External Productのノイズ

  • 加算のノイズは自明なので省略
  • Decompositionによる丸め誤差をϵ=1Bglϵ=\frac{1}{Bg^l}、TRLWEの誤差の標準偏差をααとする
  • 2lN(Bg2)2αbk2+(1+N)∣∣μ[X]∣∣2ϵ2+∣∣μ[X]∣∣2α22lN(\frac{Bg}{2})^2α_{bk}^2+(1+N)||μ[X]||^2ϵ^2+||μ[X]||^2α^2
  • 第1項は係数の絶対値がBg2\frac{Bg}{2}以下のNN次多項式が零の暗号文の行列にかかるときのノイズ
  • 第2項はDecompositionによるノイズが復号時にどれだけ増幅されるか
  • 第3項はTRLWEのノイズがTRGSWの平文によってどれだけ増幅されるか

CMUXのノイズ

  • 当然ほぼExternal Productと一緒の結果になる
  • 明らかに∣∣μ[X]∣∣2||μ[X]||^2≤1
  • 足し引きの関係から入力となるTRLWEの標準偏差で大きい方をααとする
  • ∴2lN(Bg2)2αbk2+(1+N)ϵ2+α22lN(\frac{Bg}{2})^2α_{bk}^2+(1+N)ϵ^2+α^2

Blind Rotate

  • 今回の範囲ではTest Vectorはノイズを含まない
  • nn回CMUXをするのでこうなる
  • n(2lN(Bg2)2αbk2+(1+N)2ϵ2)n(2lN(\frac{Bg}{2})^2α_{bk}^2+(1+N)2ϵ^2)

Identity Key Switching

  • 入力となるTLWElvl1のノイズをααとする
  • α+Ntαks+N2−2(t∗basebit+1)α+Ntα_{ks}+N2^{-2(t*basebit+1)}
  • 第2項は合計NtNtこのTLWElvl0を足すことから来ている
  • 第3項は整数に丸める際の丸め誤差の影響を表している

Gate Bootstrapping

  • 今まで出てきたものをすべて足せばいい
  • n(2lN(Bg2)2αbk2+(1+N)2ϵ2)+Ntαks+N2−2(t∗basebit+1)n(2lN(\frac{Bg}{2})^2α_{bk}^2+(1+N)2ϵ^2)+Ntα_{ks}+N2^{-2(t*basebit+1)}

パフォーマンスから選定の基本

  • すでに述べているが多項式乗算を出来る限り避ける
  • llは可能な限り小さいほうがよくn,Nn,Nも小さいに越したことはない
  • ttも小さいほうがいいがそんなに影響しない

参考文献

page_number: true