TFHE実装入門

1.TLWE

松岡　航太郎

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

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

TLWEとは

• Torus Learning With Errorsの略
• Torus版のLWE暗号という意味
• LWEについては次スライド

LWEとは

• よく使われるのはTorusではなく剰余環に値をとるInteger LWE
  • これの拡張が耐量子暗号としてNIST PQCに選定された
• 名前にあるとおり、Errorが重要な役割を果たす
  • Errorのとり方も複数ある
  • 平文がわかっている暗号文が好きなだけ手に入るとき(IND-CPA)Errorがないと、手に入った暗号文のを並べた行列の逆行列を計算すれば秘密鍵がわかる
    • Errorがあると単純な逆行列の問題からずれ、Errorが大きいほど難しくなる
    • 実数なら最小2乗法だが何らかの離散化が入るのでそれより難しい
• 行列のサイズが大きい程難しいともいえるので暗号文の大きさ()も安全性に寄与する
  • 具体的攻撃法は「格子暗号解読のための数学的基礎」がよい
  • 過去にセキュキャン講師だったkurenaifさんが動画出してる

Torusの直感的定義

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

Torusとは

• ここでは、を定義とする。つまり、実数の小数部分で、またはに値をとる
  • 理論を理解する上ではだけでもよい
  • は実装上効率が良い場合が在る
• Torus同士の乗算は定義されないが、加算は定義できる
• 加算の例:
• 乗算が定義できない。例: なので、乗算が定義できるならだが成立しない。
• 整数()との乗算は定義できる。例:

モジュラー正規分布

• TFHEの原論文だとModular Gaussian Distribution。
• 通常の正規分布のサンプルは実数()に値をとるが、これはTorusに値をとる
  • 離散ガウス分布は整数に丸めるがこれはTorus
  • 実際の実装は整数に近似するので離散正規分布を使うべき説はある
• 正規分布のサンプルをしたものがモジュラー正規分布
  • これをエラーに使うのがTFHEでは最も標準的なのでまずはこれから

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

• で、バイナリの値の集合。
• 暗号の安全性を決めるパラメータは２つで
• をから個の値を独立にとる一様分布とする
• を平均標準偏差のモジュラー正規分布とする
• とする
• が平文、,,とする
• 暗号文はとして、という要素のベクトル
• なので、を削除する方法を加えるとがとれ復号できる
• を大きくすればするほど安全(は大きくしすぎると暗号文が壊れる)

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

平文	ノイズを加えた場合

• 強調して書いているように、復号が誤る確率は0ではない(実用的には無視できる)
  • おおむね以下なら良いといわれる
  • 一般的なPCでの誤り確率がこれくらいといわれている

TLWEの加法準同型性

• ２つの暗号文を考え、その和をとする
• になり、が出てくるので加法準同型になっていることが分かる
• 誤差もとなっているので、足し算ができる回数には限界がある
  • 誤差が大きすぎると復号を誤る確率が大きくなる

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

• とする。
• である
• TLWEの暗号文は
• 復号はである。(は符号関数)
• 復号のときにはになっている

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

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

バイナリ演算のアイデア

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

Visual Image(ノイズ無しでの加算の全パターン)

• から入力２つの和を引くと両方が1のときだけ左半面にあることになる
• 両方が1のときだけ0になるのはまさしくNAND
  • 最初の加減算の符号と定数の値はこうやって決められている
  • 他の２入力の論理ゲートも同じように選ぶことで作ることができる
    

Bootstrapping

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

Torusの実装法

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

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

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

Centered Binomial Distribution (CBD)

• モジュラー正規分布以外に使われるノイズ分布の一つ
  • 他には離散正規分布がよく使われる
  • Torusでは定義できないので, Torusを離散化した後でだけ使える
• 0または1を等確率でとる確率変数を用いて以下が定義

• がパラメータでこれが増えると裾が広くなる
• 計算が容易で値の範囲が有界なのが利点

TLWEのパラメータについて

• この講義ではパラメータ128bit securityと現在推定されている値を紹介する
• ,または、固定小数点の幅は16bit
  • 去年まで32bitだったがこのパラメータだと詰めれることに気づいた
• TLWEの安全性はLWEの安全性の問題に帰着されるので、LWE用の推定方法がつかえる
  • Torusで理論は説明するが実装はを法とした剰余環
    • その意味ではモジュラー正規分布ではなく離散正規分布やCBDを使うべきではある
  • 剰余環とどちらが本質か？(たまに悩んでいる)
• LWE Estimatorが安全性評価のデファクトスタンダード
  • 安全性推定のコード例はここ

乱数生成について

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

TLWEで最低限実装するもの

• HomNANDを作るのに必要なだけを挙げるのでより汎用的に作るかどうかは設計思想に任せる
• 平文をバイナリに限定した場合の暗号化と復号さえ実装できればいい
• 暗号文同士の加算は後で使うので、ベクトルっぽい加算がしやすいようにデータを保持しておくと良い
  • TFHEppはstd::arrayで持っているが、classにして演算子オーバロードするほうが多いかも
  • ではなくの形の方が一般的か
    • 最近この方がメモリアクセス的にほんのちょっと効率的な気がしている
• パラメータは後で簡単に変更できるように書いておいた方が汎用性は高い