TFHE実装入門

1.TLWE

松岡 航太郎

説明内容のHomNANDでの位置づけ

  • lvl1は次回説明するので今回はTLWEといえばlvl0のこと

TLWEとは

  • Torus Learning With Errorの略
  • Torus版のLWE暗号という意味
  • LWEについては簡単に後述

Torusの直感的定義

  • 日本語で言うと円周群のこと。T\mathbb{T}とかく。
  • 時計の針の角度をイメージすると良い
  • 具体的な数字としては針の角度を2πで割ったもの

Torusとは

  • ここでは、Rmod1\mathbb{R} \bmod 1を定義とする。つまり、実数の小数部分で、[0,1)[0,1)または[0.5,0.5)[-0.5,0.5)に値をとる
    • 理論を理解する上では[0.5,0.5)[-0.5,0.5)だけでもよい
    • [0,1)[0,1)は実装上効率が良い場合が在る
  • Torus同士の乗算は定義されないが、加算は定義できる
  • 加算の例: 0.8+0.6=1.40.4mod1,0.30.9=0.60.4mod10.8+0.6=1.4≡0.4 \bmod 1,0.3-0.9=-0.6 ≡ 0.4 \bmod 1
  • 乗算が定義できない。例: 1.20.2mod1,2.40.4mod11.2≡0.2 \bmod 1,2.4≡0.4 \bmod 1なので、乗算が定義できるなら1.22.4=2.880.20.4=0.08mod11.2⋅ 2.4=2.88≡0.2⋅0.4=0.08\bmod 1だが成立しない。
  • 整数(Z\mathbb{Z})との乗算は定義できる。例:30.40.2mod13⋅ 0.4≡ 0.2 \bmod 1

モジュラー正規分布

  • TFHEの原論文だとModular Gaussian Distribution。
  • 通常の正規分布のサンプルは実数(R\mathbb{R})に値をとるが、これはTorusに値をとる
    • 離散ガウス分布は整数に丸めるがこれはTorus
  • 正規分布のサンプルをmod1\bmod 1したものがモジュラー正規分布

TLWEの具体的構成(平文がTorusな場合)

  • B={0,1}\mathbb{B}=\{0,1\}で、バイナリの値の集合。BZ\mathbb{B}⊂ \mathbb{Z}
  • 暗号の安全性を決めるパラメータは2つでnZ+,αR+n∈\mathbb{Z}^+,α∈\mathbb{R}^+
  • UTnU_{\mathbb{T}^n}T\mathbb{T}からnn個の値を独立にとる一様分布とする
  • DT,α\mathcal{D}_{\mathbb{T},α}を平均00標準偏差ααのモジュラー正規分布とする
  • aTn,e,bT,sBn,mT\mathbf{a}∈ \mathbb{T}^n, e,b∈ \mathbb{T}, \mathbf{s}∈ \mathbb{B}^n,m∈ \mathbb{T}とする
  • mmが平文、aUTn\mathbf{a}←U_{\mathbb{T}^n},eDT,αe←\mathcal{D}_{\mathbb{T},α},sUBn\mathbf{s}←U_{\mathbb{B}^n}とする
  • 暗号文はb=as+m+eb=\mathbf{a}⋅ \mathbf{s}+ m +eとして、(a,b)(\mathbf{a},b)というn+1n+1要素のベクトル
  • bas=m+eb-\mathbf{a}⋅\mathbf{s}=m+eなので、eeを削除する方法を加えるとmmがとれ復号できる
  • n,αn,αを大きくすればするほど安全(ααは大きくしすぎると暗号文が壊れる)

LWEとは

  • よく使われるのはTorusではなく剰余環に値をとるInteger LWE
    • これの拡張が耐量子暗号の候補としてNIST Round3まで生き残っている
  • 名前にあるとおり、Errorが重要な役割を果たす
  • 平文がわかっている暗号文が好きなだけ手に入るとき(IND-CPA)Errorがないと、手に入った暗号文のa\mathbf{a}を並べた行列の逆行列を計算すれば秘密鍵がわかってしまう
  • Errorがあると単純な逆行列の問題からずれ、Errorが大きいほど難しくなる
  • 行列のサイズが大きい程難しいともいえるのでnnも安全性に寄与する
    • 具体的攻撃法は「格子暗号解読のための数学的基礎」がよい
    • kurenaifさんが動画出してる

Visual Image(暗号化によるノイズ)

平文 ノイズを加えた場合
  • 強調して書いてはいるが、復号が誤る確率は0ではない(実用的には無視できる)

TLWEの加法準同型性

  • 2つの暗号文(a1,b1),(a2,b2)(\mathbf{a}_1,b_1),(\mathbf{a}_2,b_2)を考え、その和を(a1+a2,b1+b2)(\mathbf{a}_1+\mathbf{a}_2,b_1+b_2)とする
  • b1+b2(a1+a2)s=m1+m2+e1+e2b_1+b_2-(\mathbf{a}_1+\mathbf{a}_2)⋅\mathbf{s}=m_1+m_2+e_1+e_2になり、m1+m2m_1+m_2が出てくるので加法準同型になっていることが分かる
  • 誤差もe1+e2e_1+e_2となっているので、足し算ができる回数には限界がある
    • 誤差が大きすぎると復号を誤る確率が大きくなる

Bootstrapping

  • 準同型暗号上で復号関数を評価することでエラーを除去する操作のこと
  • Gentryさんはこれを最初に提案し、構成を与えた
    • 現状の完全準同型暗号は全てこれによって構成されている
    • TFHEではBlind Rotateという操作がほぼBootstrapingのこと

TLWEの具体的構成(平文がバイナリな場合)

  • mB,μ=1/8Tm∈ \mathbb{B},μ=1/8\in\mathbb{T}とする。
  • μ(2m1)Tμ(2⋅ m-1)∈\mathbb{T}である
  • TLWEの暗号文はb=as+μ(2m1)+eb=\mathbf{a}⋅ \mathbf{s}+μ(2⋅ m-1)+e
  • 復号は(1+sgn(bas))/2(1+\mathit{sgn}(b-\mathbf{a}\cdot\mathbf{s}))/2である。(sgn\mathit{sgn}は符号関数)
  • 復号のときにはT=[0.5,0.5)\mathbb{T}=[-0.5,0.5)になっている

Visual Image(ノイズ無しでの加算)

Visual Image(ノイズありでの加算)

バイナリ演算のアイデア

  • Torusにエンコードされた平文は{-1/8,1/8}
  • 2つのTLWEを足したものの平文は{-1/4,0,1/4}
  • これを(0,1/8)(\mathbf{0},1/8)から引くと{-1/8,1/8,3/8}
  • -1/8になるのは両方の暗号文がバイナリの平文として1のとき
  • 3/8は両方0、1/8は2つが異なる
  • この暗号文を復号すると、負符号のものは0に、正符号は1になる
  • つまり、両方1の暗号文を入力としたときだけ0になるのでNANDになっている
  • Remark: Bootstrappingは暗号上で復号を評価する

Torusの実装法

  • 実数の小数部の集合なので、素直に考えると倍精度浮動小数点数で実装したくなる
    • ただ、倍精度浮動小数点数でmod1\bmod 1の計算をするのは重い
  • そこで、小数点が最上位bitの前にあるような固定少数点数を用いることにする
  • 例:8bit幅の場合、0.50.50b10000000b10000000.3750.3750b011000000b01100000になる
  • この方法だと加算や乗算で出た整数部分はオーバーフローで捨てられるので剰余演算が要らない
  • 例:8bit幅の場合、0.5+0.625mod1=0b1000000+0b10100000=0b0010000=0.125mod10.5+0.625 \bmod 1=0b1000000+0b10100000=0b0010000=0.125 \bmod 1
  • 固定小数点数の幅はeeが十分に表現できる程度の幅であれば良い
    • つまりモジュラー正規分布の標準偏差によって十分な幅が決まる

実数とトーラスの変換の実装

  • モジュラー正規分布の実装には実数とTorusの変換が必要
  • 理想的には実数の小数部分を取り出す操作
  • 実数の整数部を取り出す操作をint()\mathrm{int}()、固定小数点の幅をww、入力となる実数をddとする
  • 実数の小数部分を取り出すだけなら、dmod1d \mod{1}でよい
  • 実際には固定幅の固定小数点にしたいので、実数の上からww桁の部分を整数として取り出す
  • 実装したい操作を数式で書くと以下のようになる

int((dmod1)2w)\mathrm{int}((d \mod{1})⋅2^w)

TLWEのパラメータについて

  • この講義ではパラメータ128bit securityと現在推定されている値を紹介する
  • n=635n=635,α=215α=2^{-15}、固定小数点の幅は32bit
  • TLWEの安全性はLWEの安全性の問題に帰着されるので、LWE用の推定方法がつかえる
    • Torusで理論は説明するが実装は2322^{32}を法とした剰余環
    • 剰余環とどちらが本質か?(たまに悩んでいる)
  • LWE Estimatorがデファクトスタンダード
  • 推定のコードはここ

乱数生成について

  • 暗号の安全性は乱数の質に大きく左右される
  • メルセンヌ・ツイスタを用いてはいけない(ポケモンの乱数調整)
    • 原論文著者実装では使っているが真似してはいけない
  • 一番安全なのはOSが提供する乱数を使うこと(Linuxなら/dev/urandom)
  • 暗号学的に安全性が担保された疑似乱数をCSPRNG(Cryptographically Secure PseudoRandom Number Generator)という
  • TFHEppではRandenを使っている

TLWEで最低限実装するもの

  • HomNANDを作るのに必要なだけを挙げるのでより汎用的に作るかどうかは設計思想に任せる
  • 平文をバイナリに限定した場合の暗号化と復号さえ実装できればいい
  • 暗号文同士の加算は後で使うので、ベクトルっぽい加算がしやすいようにデータを保持しておくと良い
  • パラメータは後で簡単に変更できるように書いておいた方が汎用性は高い

page_number: true