暗号のままで計算しよう 〜B/FV編〜

セキュリティ・キャンプ2025ミニ（石川開催）

松岡　航太郎

自己紹介

• 京都大学大学院情報学研究科 佐藤高史 研究室 博士課程
• 京都大学工学部電気電子工学科卒　特色入試
• 東京都立戸山高等学校卒
• 2019年度未踏スーパークリエータ
• 京都大学機械研究会(2019年度NHK学生ロボコン優勝)
• 趣味は読書
• 卒業研究は超伝導体と磁性体を含む動電磁界シミュレーション
• 修士論文はTFHEのFPGA実装, 最近ASICも作った

目標

• B/FVの乗算を実装し、背景となる理論を説明できるようになること
• 目に見える目標は乗算のテストが動くPython実装の製作

準同型暗号とは？

• Homomorphic Encryption
• 「暗号文のママ計算できる」暗号
• 平文に対する演算と準同型な演算を暗号上で定義できる
• 概念が提案されたのは1978年(RSAと同年)
• DARPA、Intel、IBM、Microsftなどが鎬を削っている
• 流行りの応用は医療データなどの機密性の高いデータを扱うPrivate AI
• 標準化の動きも在る
  • ISO/IEC 18033-6:2019(en) IT Security techniques — Encryption algorithms — Part 6: Homomorphic encryption

準同型暗号の実応用例

1. MicrosoftのPassword Monitor
   • パスワードが漏洩しているかどうかを判定
   • Edge経由で使えるらしい
2. AppleのCaller ID, Business Services in Mail, Enhanced Visual Search
   • Caller ID: 迷惑電話として知られている番号かどうかを判定
   • Business Services in Mail: メールの送信元がスパムとして知られているかを判定
   • Enhanced Visual Search: 画像からどこでとられた写真家推定する
     • On-Device MLやDifferential Privacyなども使われているのでHEだけではない

Fully Homomorphic Encryptionとは？

• FHEとよく略す。日本語で言えば完全準同型暗号。
• 暗号文を入力として、暗号文のママ『任意』の関数を適用できるような暗号
  • 整数の暗号文であれば任意の回数加算と乗算ができることが十分条件
  • bitの暗号文であれば任意の回数NANDができることが十分条件
• TFHEは後者で論理回路として表現できる関数なら評価可能

FullyじゃないHomomorphic Encryption

• 多くのHEは剰余環上の整数に対する演算をサポートしている
• PHE(Partial): 加算だけもしくは乗算だけできるHE (RSAとか)
• SHE(Somewhat): 両方できるが乗算の回数に暗号方式に依存した回数制限がある
• LHE(Leveled): 両方できるがパラメータ依存で乗算の回数制限があるもの

FHEの世代

• wikipediaが詳しい
• 第1世代FHE: Gentryさんの博士論文(2009)など
• 第2世代FHE: Brakerski-Gentry-Vaikuntanathan (BGV, 2011)など
• 第3世代FHE: Craig Gentry, Amit Sahai, and Brent Waters (GSW,2013)やTFHE(2016)など
• 第4世代FHE: Cheon Jung Hee, Kim Andrey, Kim Miran, Song Yongsoo(CKKS, 2017)

B/FV

• Brakerski-Fan-Vercauteren の略

• 有限体上の計算を行う

  • 各係数が剰余環の値であるような多項式の剰余が成す体
    • 剰余環は整数を割った余りの成す環
    • 有限体は有限な元が成す体なので法が素数なら剰余環も有限体になる

• BFVとよく似た方式にBGVが存在する

  • MSB側に平文を乗っけるかLSB側に平文を乗っけるかの違いしかない
    • 相互にノイズの増大があるだけで変換できることが知られている
  • 歴史的にはBGVが先
    • 両方とも第２世代に分類される

講義の流れ

• 以下のような章構成として, 各章の後に実装時間を設けます
  • 最後の章は昼食後にアドバンスドな話とかするだけなので最悪省略
  • 実装は既定の時間が終了しかつ半数以上の人が達成したら終了の予定
• Relinearlizationは時間内に実装できるか怪しい
  • 時間内にできなくても落ち込まないで
• 課題はこのGitHubレポジトリにある

1. 導入とTRLWEの暗号化と復号(今)
2. TRLWEの加法性と乗法性
3. Relinearlization
4. Advanced Topics

TRLWEとは

• Torus Ring Learning With Errorsの略
  • LWEの多項式環版のトーラス係数版
• 多項式を暗号化する暗号化方式
• Ringは多項式『環』の上で定義することから来ている
  • 課題でやってもらった多項式の剰余演算が出てくる
  • 厳密にはTorus係数多項式だと環じゃない気がする
    • 後に見るようにTorusには乗算が定義できない

Torusの直感的定義

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

Torusとは

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

モジュラー正規分布

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

TRLWEの具体的構成(平文がの場合)

• 暗号の安全性を決めるパラメータは2つで
• とする
  • は一般にTernaryと呼ぶ(表記は一般的ではない)
• が平文、,,とする
• TRLWEの暗号文はとして、という次の多項式要素のベクトルである
• になるので、このをどうにかして削除する方法を加えるとがとれて復号できる
• を大きくすればするほど安全(は大きくしすぎると暗号文が壊れる)
• 同じ安全性・データならTLWEよりTRLWEはサイズが小さい(と信じられている)

TRLWEの具体的構成(平文がの場合, BFVの暗号文)

• とする
• TRLWEの暗号文は
• 復号は
  • ここの丸めはuintでやった方が考えやすいかも?

OffTopic: TRLWEの安全性の直感的理解

• は行列ベクトル積としてかける
  • の係数で作った巡回行列との係数のベクトル
    • つまりみたいな形にできる
• の逆行列が計算できるとすると, もしこれが実数の話なら最小二乗法的な話に落ちる
  • 実際はTorusで周期性があるのでもっと難しいが
  • 最小二乗法だと思うと, ノイズがないとすぐ解けそうということはわかるはず
• 一般の解法については「格子暗号解読のための数学的基礎」とかを読むと良い

Torusの実装法

• 実数の小数部の集合なのでナイーブには倍精度浮動小数点数で実装したくなる
  • ただ、倍精度浮動小数点数での計算をするのは重い
• そこで、小数点が最上位bitの前にあるような固定小数点数を用いることにする
• 例:8bit幅の場合、は、はになる
• この方法だと加算や乗算で出た整数部分はオーバーフローで捨てられ剰余が不要
• 例:8bit幅の場合、
• 固定小数点数の幅はが十分に表現できる程度の幅()であれば良い
  • つまりモジュラー正規分布の標準偏差によって十分な幅が決まる
• 符号付きで考えたほうが一般性があるためそちらを想定するが符号なしでも構成できるはず
  • 符号付きが必要な時だけ切り替えればよい

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

• モジュラー正規分布の実装には実数とTorusの変換が必要
• 理想的には実数の小数部分を取り出す操作
• 実数の小数部分を取り出すだけなら、でよい
• 実際には固定幅の固定小数点にしたいので、実数の上からの部分を整数として取り出す
• はPythonだと正の数になるのでuintにしてからintにする
  • Python組み込みのIntの場合, intへの変換はを以上ならを引く
  • NumpyならCと同じでuint64をint64にするとbit列として解釈され意図通り
• 実装したい操作を数式で書くと以下のようになる

多項式環上の乗算

• ここではナイーブな実装を扱う(課題1の想定回答の疑似コード)
• ２つの元を掛け算, その剰余を取り, 係数の小数部を抜き出せば良い
  • 係数の型を適切にとればオーバフローにより係数の剰余は自動的にとれる
• 入力をとする
  • 実装上は両方整数なので気にすることはないが
• である

for i from 0 to N-1
  cᵢ = 0
for i from 0 to N-1
  for j from 0 to N-1
    if i+j<N
      cᵢ₊ⱼ += aᵢ⋅bⱼ
    else
      cᵢ₊ⱼ₋ₙ -= aᵢ⋅bⱼ (Nの下付きが打てないのでₙになっている)

演習タイム(課題3)

• ここまで説明したTRLWEの暗号化と復号を実装しよう
  • 課題3のテストが通ればとりあえずよし
  • 本当はちゃんとした乱数生成器を使う必要があるが, 今回はそこには目を瞑ることにする
    • 乱数の品質が低いと暗号が脆弱になる

BFVの加算

• TRLWEは加法準同型性が成り立つ
• ２つの暗号文を考える
• その和をとする
• になり、が出てくるので加法準同型になっている
• TLWEよりサイズが小さいのでより高速に加算ができることになる
  • 係数ごとに独立した加算なのでSIMDライク
• ノイズも加算されているので回数には限界がある

BFVの乗算(naive)

• TRLWEは乗算に近いものも定義できる
  • 乗算するために片方を倍して整数に丸める

• ということは乗算結果の新しい暗号文として を与えれば乗算になる
  • この形の暗号文の名前は把握していない
  • で割るので乗算は剰余を取らずに実数として考えて実行する
  • あるいは先にTorusをで割っていると考える
    • Torusはdivisible gorupでもあるので整数で割ることはvalidな演算(のはず)

実装における実際の挙動

• は本来とは独立に選べる
  • しかし明らかにのとき丸め誤差が入る
  • に取ってしまえばここを考えなくていい
  • 見たことある実装は基本的にこのアプローチ
• つまり実装上はは出てこなくてすべての多項式を整数係数多項式だと思ってで割ればいい
  • 実装上はも上なのでで割る形で書くことになる
    • 課題3でのの定義を参照のこと
• つまりコード上はこんな見た目になる

実装的な実数での乗算の扱い

• 除算して乗算の上側をとることになるので一時的に64bitより大きい計算が必要
  • long double(x86のWindows以外の環境なら80bit)で計算するのが一番楽?
    • numpyで実装できる
    • 誤差が出るが, 暗号のエラーと区別できないのであまり問題でない
    • 提供する高速版はこのアプローチが自然にとれるようにしてある
  • 精度を維持したいならPythonの整数型は精度に上限がないのでそれも簡単
    • おそらく見れる速度にはならないのでやめた方がいい
• 除算した後は64bitに丸めなおす
  • ちょっとノイズが増えるが, そうしないと小数部分がどんどん伸びてしまう
  • 実装上遅いし扱いが面倒なだけでダメなわけではない

演習タイム(課題4,5,6)

• 課題4の暗号文の加算は自明なのでテストを走らせるだけ
  • 暗号化・復号実装がちゃんとしていればきっと動くはず
• 課題5はテストしやすいように分離しているだけ
  • ExtendedEncryptは実際は全く使わないので, ExtendedDecryptの実装だけ書いて終わりでも良い
  • 課題6でMulとどっちが悪いのかわからなくなると困りそうなので一応分けた
• 課題6の乗算は実のところ多項式の乗算を適切に扱うのが一番面倒かも
  • Extendedpolymul
  • 必要であれば自分でもう一つテストを書くと良いかもしれない
    • テスト提供するとほぼ答えなので分けていない
  • 提供している高速多項式実装の場合, 最後にuintでcastする前に割れば良い
• ExtendedDecryptionは
  • が必要な項があることに注意

Relinearlization(アイデア)

• 乗算をすると出力の暗号文は次元がになってしまう
  • 乗算をこのまま続けていくとどんどん次元が増えてしまう
  • 絶対にだめなわけではないが計算効率が急速に下がる
• 乗算で増えてしまった次元を減らすのがRelinearlization
• が計算できれば次数が元に戻る
  • を計算するにはをで暗号化して送ってやればいい
  • このために使われるのがGLevと呼ばれる暗号形式

整数多項式とTorus多項式の積

• いきなりGLevの具体的構成をみてもモチベーションがわからない
• やりたい演算を順次構成していくことでGLevを導出する
• 以下のような演算を復号せずにやりたい(準同型暗号上の多項式乗算)
• 乗算の結果の3要素の暗号文のと掛ける項をとする
• 計算したいのは
  • 整数係数多項式とTorus多項式の積

スケーリング

• Glevの構成には2つ重要なアイデアがあり、１つがスケーリング
• TRLWEは整数係数多項式をそのまま平文にすることはできない
• をTorus係数にしてその分をに押し付けて整数係数に丸める
  • 丸めの分だけノイズが増えることに注意
• ノイズ()が倍されることに留意
  

に関するトレードオフ

• の係数の最大値は
• つまりを大きくするとが増幅される
• しかしを小さくすると丸めによる誤差が大きくなる
  • に取ればなくなるがそんな値は取れない
• このトレードオフから逃れるのがDecomposition

Decomposition(一般的定義)

• 丸めるときにを基数とみなして桁に分解する
  • を大きくせずに丸めによるノイズを減らせる
• Decompositionは多項式を入力にとる
• 出力として多項式のベクトルを返す
  • 要素となる多項式の係数は入力となる多項式の係数の一桁を抜き出したもの
  • Torusを進表現したときの１番上の桁を集めたもの、次の桁という具合でベクトルの要素は並ぶ
• はを満たす
  • でなくにとるのはノイズを小さくしたいから
• を次の係数がである多項式とする
  • 多項式のベクトルの番目の要素をとして返す

Decompositionでつくるもの

• 逆操作を先に見ることでイメージを得よう
• はの場合のDecompositionになっている

Decomposition(具体的構成)

• を具体的に与えるアルゴリズムを示していく
  • 簡単のためと書ける場合に限定する
  • Torusはuint64_tで表現されているものとする
    • 符号付きで考えると面倒になってしまうので一時的にcast
• だと係数が負になる場合を考える必要がある
• 各桁にをたすことでにずらす
• こうするとbitマスクで取り出すだけで良くなる
  • このあたりが面倒になる
• 最後に各係数からを引いて元に戻す
  • 戻したら符号付きに戻る

Decomposition(基本的アイデア)

• 前提としてもし各桁をの範囲で取るならmaskだけで良い
  • にとる場合をとする
  • つまり
  • は四捨五入のための定数
  • これはを満たす
• を経由したへの変換を考える
  • 以下のような関係が成り立つようにを決めることができる(要は桁上がりをしている)

Decomposition(疑似コード)

• このアイデアをナイーブに実装した場合の疑似コードを示そう
  • ほぼ繰り上がり計算なので加算機でやる最適化が可能だが複雑になりすぎる
  • Torusは64bit固定小数点表現されていることを仮定している

Decomposition(c[X])
  roundoffset = 1 << (32 - l * Bgbit - 1)
  for i from 1 to l
    for j from 0 to N-1
      ̂cᵢⱼ=(((cⱼ+roundoffset)>>(64-Bgbit*i))&(Bg-1))
  for i from l to 1
    for j from 0 to N-1
      if ̂c ᵢⱼ ≥ Bg/2
        c̄ᵢⱼ = ĉᵢⱼ - Bg
        ĉ₍ᵢ₋₁₎ⱼ += 1
      else
        c̄ᵢⱼ = ĉᵢⱼ
  return c̄[X]

Glevの具体的構成

• Decompostionをに施して掛け算をすると考えるとGLevの暗号文は以下
  • 今回は平文がだけなのでそう書いているが一般には他のものでも良い
• 要はTRLWEのベクトル
  • 各行のは独立に選ぶ
    

に関するトレードオフ

• を増やせば丸めのノイズを減らすことができる
• を増やすとGLev暗号文由来のノイズが増える
  • たくさん足し合わせることになるので
• は丸めには指数で効き0の暗号文由来には線形で効く
  • トレードオフの出方がと違う
  • ノイズを最小化するの組が存在する
• を増やすほどExternal Productの多項式乗算が増えて重くなる
  • ノイズが許容される範囲でを小さくとりがち

演習タイム(課題7)

• RelinearlizationKeyGenがを平文とするGLevの暗号化関数
  • 復号は(一般の場合でも知る限り)使わないので必要ない
• かなり計算が複雑になるので提供する高速多項式実装の利用を推奨
  • もちろん自前の実装が十分速いならそれでも問題ない
  • 模範解答として作った実装だと1回7sかかった
    • Ryzen 9800X3D上なので, ノートパソコンだと3倍くらいはかかるかも
  • 時間が余ったら高速化を試みると良い
    • Numpyの使い方の工夫だけでも早くなったりするかも
    • PyPy, Codon, Numba, Cythonあたりも試す?

参考文献

• B/FV原論文(Brakerski)
• B/FV原論文(Fan-Vercauteren)
• The Chinese Remainder Theorem
• Introduction to BFV
• Bootstrapping for HElib
• BFVのGPU実装
• TFHEのPython実装

Advanced Topics

• 時間が余ったら喋ろうと思っている話題のリスト
  • バッファとして消費する可能性もあるので喋らないかも
  • その時の様子で内容は決める

1. RNS&Double Decomposition
2. Fast Polynomial Multiplication
3. Bootstrapping (Lifting)
4. Packing
5. CLPX

Packing

• Canonical Embeddingと呼ばれることもある
  • Embeddingは日本語で言えば埋め込みでwikiによると数学的構造間の構造を保つような単射のことらしい
• BFVの特徴としてよく言われるもの
  • (CKKSもだが)一般にはこちらの方式がよく使われる
• Packingは平文のエンコーディング方法の一つ
  • 暗号文の演算としては変わらない
• RLWEに見られる性質として, 加算に関しては係数ごとに並列な演算ができる
  • 乗算に関しても独立な計算ができたら便利そう
    • を法とするNTTをかけてやればこれが達成できる
      • とかがよくつかわれる
    • CKKSだとFFT
    • 厳密には次全てを使うのでなければNTTとして完全に分解できる必要はないのでをとかにとってもよい
      • の下でが分解できる式の数が並列で扱えるスカラーの数
        

Slot2Coeff/Coeff2Slot

• Packingで値を詰めた場合の各値のことをSlotと呼ぶ
  • たぶんSIMDレジスタ的な気持ち
• しかしBootstrappingなどをするときには多項式の係数に対して考えたほうが楽な場合が多い
  • 平文がNTTがかかってる状態のやつを暗号上でINTTをかけて係数に平文が来るようにしたい
• Nai"eveな実装はとても簡単
  • NTTやINTTは行列(Vandermonde matrix)とベクトルの積として書ける
    • これをKeySwitchingとしてやればよい

Lifting

• Bootstrappingをするにはノイズを消去する必要がある
  • SampleExtractIndexしてTFHEでBootsrapingする方法も知られてはいる
• BFV固有のBootstrappingのアイデアとしてLiftingがある
  • 平文を基数で分解できる()ものとして最下位を得る演算
    • 最下位を得られればそれを引けば最下位が消去できる
• 最も単純なものはの場合
  • 乗して引くことを繰り返すだけ

Liftingの疑似コード

• Bootstrapping for HElibのFigure 1より
  • jのLoopのところがLifting
  • これで最上位桁を取り出せる

Digit Extraction(z,e)
w₀,₀ ← z
For k ← 0 to e-1
  y ← z
  For j ← 0 to k
    wⱼ,ₖ₊₁ ← (wⱼ,ₖ)ᵖ
    y ← (y - wⱼ,ₖ₊₁)/p
  wₖ₊₁,ₖ₊₁
return wₑ,ₑ