暗号文のまま関数を引く — 予習ノート

講義は FHE の概要 → LWE 暗号の基礎 → TFHE の Programmable Bootstrapping の 3 部構成。

そのあとホワイトボードセッション（テーマ調査・議論・2 グループ相互の発表とフィードバック）。事後課題は、セッションで出たクエスチョンの調査（提出不要）とコードの穴埋め課題。

暗号方式 = 3 つのアルゴリズムの組 (Gen, Enc, Dec) で、Dec(Enc(m, key_enc), key_dec) = m を満たすもの。

Enc と Dec で同じ鍵なら共通鍵暗号（AES など）。Gen が鍵ペア (pk, sk) を作り、pk で暗号化・sk で復号するなら公開鍵暗号（RSA など）。

準同型暗号 = 暗号文のまま計算できる暗号。Dec(c₁ ⊗ c₂) = m₁ ⊕ m₂。

例: RSA は暗号文同士を掛けて復号すると平文同士の掛け算になる。Paillier は暗号文の乗算が平文の加算になる。サーバーにデータを明かさずに計算を任せられる。

完全準同型暗号 (FHE) = 暗号文のまま、加算と乗算の両方を任意の回数行える準同型暗号。

Q. なぜ暗号文のまま加算と乗算ができたら嬉しいのか？（答えは次のカード）

m₁, m₂ ∈ {0,1} に対して 1 − m₁m₂ を暗号文のまま計算できれば NAND が評価でき、理論上任意の Boolean 回路を暗号文のまま評価できる。

概念の提唱（1978 年、Rivest ら）から初の実現（2009 年）まで 31 年かかった。

「何回まで演算できるか」で 3 段階 — SHE（有限回）→ LHE（パラメータで定めた回数まで、Bootstrapping なし）→ FHE（Bootstrapping により無制限）。

SHE: BGN など   LHE: BFV/BGV, CKKS など   FHE: GSW, FHEW, TFHE など

方式は「何の計算に向くか」で分かれる — BFV/BGV は整数（SIMD 的な演算可）、CKKS は浮動小数点などの近似値（機械学習と相性が良い）。どちらも Bootstrapping が重く、主に LHE として運用される。

出発点は 2009 年の Gentry's blueprint。演算で「ノイズ」が増えて復号できなくなる問題を Bootstrapping の導入で乗り越えたが、当初は計算量が非常に大きく実用には遠かった。

GSW が近似固有ベクトルの概念で暗号文を行列として扱う道を開き、FHEW が Bootstrapping を 1 秒未満に、TFHE が Torus への拡張で論文報告値約 13 ms まで縮めた。

FHEW は論理ゲートの評価とノイズのリフレッシュを同時に行えるようにした。

講義が置いた問い — 次のカードを見る前に、自分で挙げてみる。

Q. FHE の課題にはどのようなものがあると思いますか？

課題は 3 つ — 実行コスト、検証可能性、安全性モデル。

実行コスト: 暗号化でデータが大きくなる・演算が重い・Bootstrapping は改善されてもなおボトルネック
検証可能性: FHE だけでは計算結果の正しさは保証できない（Week 6 で説明）
安全性:     暗号文を意図的に変形できる機能そのものが non-malleability と両立しない。
            多くの方式は CPA 安全性中心。CCA が必要な応用では認証・検証レイヤーを別途設計

CPA / CCA を区別する: CPA（選択平文攻撃）では、攻撃者は選んだ平文の暗号化を要求できるが、復号は要求できない。CCA（選択暗号文攻撃）では、攻撃者が作った暗号文の復号も要求できる（CCA2 はチャレンジ暗号文を見た後も要求できるが、チャレンジそのものは除く）。FHE は Enc(m) → Enc(f(m)) と暗号文を加工する機能が本体なので、加工を禁止する non-malleability と両立しない。CCA が必要な用途では、認証・改ざん検知・復号要求の制限などを別途組み合わせる。

道順 — 近似連立方程式 → LWE 問題 → LWE 暗号とその演算 → 乗算とノイズ → TFHE の PBS（Blind Rotation / Sample Extraction / Key Switching）→ HomNAND。

通常の連立方程式は Gauss の消去法で高速に解ける。しかし各式の左辺に小さな誤差 e を足しただけで、誤差を知らずに解くのは困難になる。

橋: 中学の連立方程式は「片方の式からもう片方を引く」で必ず解けた。誤差入りだと引き算のたびに誤差も混ざり合い、消去が効かなくなる。

誤差入りの式 1 本は、係数ベクトル a と秘密ベクトル s の内積（同じ位置を掛けて全部足す）を使って ⟨a,s⟩ + e = b と 1 行に書ける。

a = (a₀, …, aₖ₋₁),  s = (s₀, …, sₖ₋₁)
⟨a,s⟩ = a₀s₀ + ··· + aₖ₋₁sₖ₋₁

何が嬉しいか: s を固定したまま a を変えると、秘密の異なる線形な組み合わせを 1 個の値として何本でも作れる。ノイズがなければ、それらを A s = b と並べて消去法で s を解ける。標本 i ごとに aᵢ・eᵢ・bᵢ は変わるが、s だけは共通です。

射影との関係では、⟨a,s⟩ は射影ベクトルを作る前に現れる 1 個の数です。ただし LWE で使う性質は図形より、⟨a+a′,s⟩ = ⟨a,s⟩ + ⟨a′,s⟩ という線形性です。

判定 LWE = 同じ秘密 s を共有する多数の標本が、bᵢ = ⟨aᵢ,s⟩ + eᵢ (mod q) から来たのか、(aᵢ,bᵢ) が一様ランダムなのかを識別する問題。

単一の組が式を満たすか、ではありません。 e を自由に選べば、ほぼどの (a,b) も式の形にはできます。区別するのは、aᵢ は一様、eᵢ は小さい、s は全標本で共通という分布です。

q = 11, s = (1,0) の観察用の例
a=(2,7), e=+1 → b=3    b−⟨a,s⟩ = +1
a=(8,4), e=−1 → b=7    b−⟨a,s⟩ = −1
a=(5,9), e= 0 → b=5    b−⟨a,s⟩ =  0

この例では s を見せたので残差が小さいと確認できますが、本物の判定ゲームでは s は見えません。大きい次元・mod q・多数の未知誤差の下で LWE 分布と一様分布を効率よく区別できない、という仮定が LWE 仮定です。(aᵢ,bᵢ) 群から共通の s を求める側は探索 LWE。

LWE 暗号 = 秘密鍵 s との内積で平文を隠し、e を足して式を少しずらす共通鍵暗号。b = ⟨a,s⟩ + Δm + e。

Gen: 秘密鍵 s ∈ {0,1}^k を一様ランダムに取る
Enc: c = (a, b = ⟨a,s⟩ + Δm + e)   a は一様ランダム、e は分布 χ から。Δ := q/p
Dec: m = ⌊(b − ⟨a,s⟩ mod q) / Δ⌉ mod p   （⌊·⌉ は四捨五入）

s を知る人は b から同じ内積を引き、Δm + e を得ます。e 自体を求めるのではありません。⌊(Δm+e)/Δ⌉ = ⌊m + e/Δ⌉ なので、−Δ/2 ≤ e < Δ/2 なら小さいずれが丸め落ちて m が戻ります。以降この暗号文を LWEₛ(Δm) と書く。

例: Δ=16, m=2, e=3
Δm+e = 35,  35/16 = 2.1875,  四捨五入 → 2

1. 内積:       ⟨a,s⟩ = 2×1 + 3×1 = 5
2. 平文を置く: Δm = 5×2 = 10
3. 暗号化:     b = 5 + 10 + 1 = 16
               暗号文 c = ((2,3), 16)

4. 鍵で消す:   16 − (2×1 + 3×1) = 11
5. Δで割る:    11÷5 = 2.2
6. 丸める:     2.2 → 2  （平文が戻る）

Q. 暗号文が復号できることを各自確認。

平文との乗算と暗号文同士の加算では、出力のノイズが元より増える — 演算を続ければ、いずれ −Δ/2 ≤ e < Δ/2 に収まらなくなる。

平文 m′ の加算:     (a, as + Δ(m+m′) + e)            ノイズ e のまま
平文 m′ の乗算:     (m′a, m′as + Δmm′ + em′)          ノイズ em′ に増加
暗号文同士の加算:   (a+a′, (a+a′)s + Δ(m+m′) + e+e′)  ノイズ e+e′ に増加

Δ=5, s=(1,1)
c₁: m=1, e=1  →  ⟨a,s⟩ + 5 + 1
c₂: m=1, e=−1 →  ⟨a′,s⟩ + 5 − 1

暗号文を加算:  平文 1+1=2、ノイズ 1+(−1)=0  → 復号しやすい
平文を 2 倍:   平文 1×2=2、ノイズ 1×2=2   → まだ |e|<Δ/2
さらに加算:    ノイズ 2+2=4                → Δ/2=2.5 を超え失敗

Q. これらの演算結果が正常に復号できるか各自確認してみよう。

暗号文同士の「乗算」の作り方が方式の分かれ目。Gentry's blueprint は暗号文を多項式のベクトルと見て積を取り、ノイズは指数関数的に増える — それを Bootstrapping（暗号文を暗号文の状態で復号する）で削減する。

BGV/BFV/CKKS はテンソル積で掛け、形の崩れた暗号文を Relinearization / Key Switching で通常形へ戻す。ノイズ・スケール管理の中心は BGV の Modulus Switching、CKKS の Rescaling。

(a₀+a₁x)(b₀+b₁x)
= a₀b₀ + (a₀b₁+a₁b₀)x + a₁b₁x²
ベクトル: (a₀b₀, a₀b₁+a₁b₀, a₁b₁)  ← 2 係数が 3 係数に膨らむ

GSW は暗号文を行列の形にして、積をビット分解と行列積で実現し、Gadget Decomposition でノイズの増大を抑えた。FHEW/TFHE はこれを使って Bootstrapping を高速化し、ノイズを減らしながら関数評価できるようにした。

平文同士の乗算は、平文を bit 表現して暗号文の状態の NAND を組み合わせれば実現できる。

基本 LWE       ベクトルで隠す。加算は簡単、暗号文同士の乗算が難しい
      ↓
GSW            行列として持ち、行列積で乗算。Gadget 分解で扱いやすくする
      ↓
FHEW / TFHE    GSW の仕掛けを使って Bootstrapping を高速化
      ↓
NAND           ビットの NAND を暗号文のまま評価。NAND を組み合わせれば任意の回路

TFHE = FHEW を Torus（トーラス）という代数構造に拡張した方式。論文中では約 13 ms で Bootstrapping を実行するパラメータ例が報告されている。

講義ではトーラスを使わない説明を取り、鍵生成・暗号化・復号は LWE 暗号と同じにする。トーラスの利点が気になる人は Chi20+ / Joy22 へ。

従来: 大きな整数 q の上で LWE を計算
TFHE : トーラス上の位相（小数の位置）で LWE を計算
       ↓
       Blind Rotation で表を回す
       Sample Extraction で1個のLWEに戻す
       Key Switching で鍵をそろえる
       ↓
       ノイズを抑えた暗号文

整数の 5 mod 3 = 2 と同じ要領で、多項式にも割り算の余りが取れる。mod xⁿ+1 の世界では xⁿ ≡ −1、そして x⁻ᵃ ≡ −xⁿ⁻ᵃ (0 ≤ a ≤ n)。

橋: 「x⁵+x+2 を x²+1 で割った余りは 2x+2」— 数 II の整式の割り算そのもの。係数が有限体 F_p のときは係数側にも mod p を取る。

x²+1 ≡ 0 なので x² ≡ −1
x⁴ ≡ (+1),  x⁵ = x·x⁴ ≡ x
x⁵+x+2 ≡ x+x+2 = 2x+2

Q. xⁿ ≡ −1 と x⁻ᵃ ≡ −xⁿ⁻ᵃ が成立することは各自確認。

やりたいこと = 平文を保ったまま、暗号文のノイズをリセットする。作戦: すべての平文を並べたリストの「ノイズの少ない暗号文」から、入力平文 mᵢ の部分だけを切り出す。

入力:  Enc(Δmᵢ + e)       ノイズ付き。mᵢ の場所が少しずれている
用意:  Enc(表)             m₀,m₁,…,mₚ₋₁ を幅を持たせて並べた表
操作:  暗号文が指す量だけ表を回す（秘密鍵で位置を読む必要なし）
読出:  0 番地の係数          → mᵢ の部分が0番地に来る
出力:  Enc(Δmᵢ + 新しいノイズ)  → 平文は同じ、古いノイズは引き継がない

選べる関数の例（p=2 のビット）
恒等 f(0)=0,f(1)=1  → 表 [0,1]
NOT  f(0)=1,f(1)=0  → 表 [1,0]

p=4 なら f(m)=m+1 mod 4 → 表 [1,2,3,0]

多項式 v(x) に x⁻ⁱ を掛けると (mod xⁿ+1)、係数 aᵢ が定数項に来る — 係数の列を「回転」させられる。

暗号文 (a, b) は b − as = Δmᵢ + e を満たす。だからこの量だけ回したとき定数項に mᵢ が来るように、v(x) の係数を組んでおけばよい。

係数の列:       [10, 20, 30, 40]
普通に1つ左へ:  [20, 30, 40, 10]
x⁴=−1 の世界:  [20, 30, 40, −10]  ← 端から来た10だけ符号反転

もう1回 x⁻¹:   [30, 40, −10, −20]
                 ↑ 元の30が先頭（定数項）へ

同じ mᵢ を、ノイズ候補ぶんの位置 Δmᵢ+e₀, …, Δmᵢ+e_r のすべてに並べておく。するとノイズ込みの回転量 Δmᵢ+e で回しても、定数項には mᵢ が来る。

平文 m=1、Δ=5、ノイズ候補 e∈{−1,0,+1}
正解の位置は Δm+e = 4, 5, 6

幅なし: 位置 5 だけに「1」
幅あり: 位置 4,5,6 に「1,1,1」

実際のノイズが +1 → 回転量は 6
幅なしだと別の値を読むかもしれない
幅ありなら位置6にも「1」があるので、答えは必ず1

平文0: 位置0〜3 → 0·(1+x+x²+x³)
平文1: 位置4〜7 → 1·(x⁴+x⁵+x⁶+x⁷)
平文2: 位置8〜11 → 2·(x⁸+x⁹+x¹⁰+x¹¹)
平文3: 位置12〜15 → 3·(x¹²+x¹³+x¹⁴+x¹⁵)

実用的なパラメータでは q が大きすぎるので、多項式の次数は q より小さい n にし、a と b を ⌊·(2n/q)⌉ で n の世界へ丸め直してから回す（Rescaling / Modulus Switching と呼ぶ）。

p = 8, q = 64, Δ = 8, n = 16 の手計算例 — b − as ≡ 10 = 8·1 + 2 の暗号文を、リスケーリング後の回転量 4 で回すと、定数項に平文 1 が現れる。

m = 1, s = (1,0,0,1,1,1,0,1), e = 2, (a, b) = ((8,34,4,32,0,31,58,7), 24)
v = 0·(1+x+x²+x³) + 1·(x⁴+…+x⁷) + 2·(x⁸+…+x¹¹) + 3·(x¹²+…+x¹⁵)
リスケーリング: Δ̂ = 4, â = (4,17,2,16,0,16,29,4), b̂ = 12
i = b̂ − âs = 12 − (4+16+0+16+4) ≡ 4 (mod 32) → x⁻⁴v の定数項 = 1 = m

Q. 5 分とるので、各自手を動かして具体例を確認（講義中の演習）。

PBS は 3 部品の直列。

回転量 b − as の計算には秘密鍵 s が要る。そこで as = Σ aⱼsⱼ をほどき、「sⱼ = 0 なら何もしない、1 なら x^aⱼ を掛ける」という 2 択（マルチプレクサ、MUX）を k 回繰り返す形に書き直す。

Q₀ ← x⁻ᵇ·v
for j = 0 … k−1:  Qⱼ₊₁ ← MUX(sⱼ, Qⱼ, x^aⱼ·Qⱼ)
return Q_k (= x^(−b+as)·v)

あとは v, sⱼ, Qⱼ を暗号文にして、この MUX を準同型演算で実行できればよい。

a=(2,5,1), s=(1,0,1), b=3 とする
最初: Q₀ = x⁻³v
j=0: s₀=1 なので x²を掛ける → Q₁=x⁻¹v
j=1: s₁=0 なので何もしない → Q₂=x⁻¹v
j=2: s₂=1 なので x¹を掛ける → Q₃=v

指数をまとめると −3 + 2×1 + 5×0 + 1×1 = 0
だから Q₃ = x⁰v = v

RLWE 暗号 = 平文・鍵・乱数をすべて多項式にした LWE。計算は mod xⁿ+1（係数は mod q）で行う。

Enc: (a(x), b(x) = a(x)s(x) + Δμ(x) + e(x))
Dec: b − as = Δμ + e を計算し、係数ごとに Δ で割って丸める

LWE と同様に、平文との加算・乗算、暗号文同士の加算ができる。

LWE:  b = a·s + Δm + e       （数字の足し算・掛け算）
RLWE: b(x) = a(x)s(x) + Δμ(x) + e(x)  （多項式の足し算・掛け算）

a(x)s(x)=(2+3x)(1+x)=2+5x+3x²

Gadget Decomposition = mod q の値の B 進数展開。19 = 10011₂ と同じ要領で、r = Σ rᵢ·q/Bⁱ⁺¹ (0 ≤ rᵢ < B) と桁に分け、g⁻¹(r) = (r₀, …, r_{l−1}) を出力する。

例（B = 4, l = 3）: Z₆₄ の 47 = 2·(64/4) + 3·(64/16) + 3·(64/64) → g⁻¹(47) = (2, 3, 3)。等式が成り立つには Bˡ = q が必要で、そうでない場合は各項を丸めて近似する。

大きな数 47
  ↓ 4進数の桁に分ける
(2, 3, 3)

64を一周とする世界でも、使う場所の重みを
64/4=16、64/4²=4、64/4³=1
と決めれば、47 = 2×16 + 3×4 + 3×1。

多項式も同じ要領で分解できる — 係数ごとに B 進展開し、q/Bⁱ⁺¹ の位ごとに多項式をまとめ直す。

例: Z₁₆, mod x³+1, B = 2, l = 4 で f = 15x² + 4x + 7 → g⁻¹(f) = (x², x²+x+1, x²+1, x²+1)。

f = 15x² + 4x + 7、q=16、B=2
15 → (1,1,1,1)   （8+4+2+1）
 4 → (0,1,0,0)   （0+4+0+0）
 7 → (0,1,1,1)   （0+4+2+1）

重み8の桁:  x²
重み4の桁:  x²+x+1
重み2の桁:  x²+1
重み1の桁:  x²+1

f = x²·8 + (x²+x+1)·4 + (x²+1)·2 + (x²+1)·1

RGSW 暗号文 = 「0 の RLWE 暗号文」を 2l 個並べたリスト Z に、平文 m を掛けた Gadget Matrix Gᵀ を足したもの。

各行は RLWEₛ(−s(x)·m·q/Bⁱ) または RLWEₛ(m·q/Bⁱ) の形になっている。Bˡ = q のとき G⁻¹((x₁, x₂))·Gᵀ = (x₁, x₂)。

RGSW(0) ⊡ Enc(m′) ≈ Enc(0)
RGSW(1) ⊡ Enc(m′) ≈ Enc(m′)

External Product ⊡ = RLWE 暗号文を Gadget 分解してから RGSW 暗号文に掛ける積。結果は RLWEₛ(Δmm′) — 平文同士の掛け算が暗号文のまま 1 回でできる。

G⁻¹(RLWE(Δm′))·(Z + mGᵀ) = RLWE(0) + m·RLWE(Δm′) = RLWE(Δmm′)

RGSW(0) ⊡ RLWE(m′) → RLWE(0)
RGSW(1) ⊡ RLWE(m′) → RLWE(m′)
RGSW(2) ⊡ RLWE(m′) → RLWE(2m′)

G⁻¹(c)(Z + mGᵀ)
= G⁻¹(c)Z + m·G⁻¹(c)Gᵀ

CMUX = MUX(b, a₀, a₁) = b(a₁−a₀) + a₀ の暗号版。選択ビット b を RGSW 暗号文、選択肢を RLWE 暗号文に置き換えて CMUX(c_b, c₀, c₁) = c_b ⊡ (c₁ − c₀) + c₀ = RLWE(Δa_b)。

普通のMUX:
b=0 → a₀=5 を選ぶ
b=1 → a₁=9 を選ぶ

式: b(a₁−a₀)+a₀
b=0: 0×(9−5)+5 = 5
b=1: 1×(9−5)+5 = 9

c₀ = Enc(5),  c₁ = Enc(9),  c_b = RGSW(b)
CMUX = c_b ⊡ (c₁−c₀) + c₀

Q. CMUX の出力が a_b の RLWE 暗号文になることを各自確認してみよう。

Blind Rotation = スライド 28 の MUX 反復を、そのまま CMUX 反復に置き換えたもの。sⱼ を別の鍵 s′ で RGSW 暗号化したリスト (RGSW_{s′}(s₀), …, RGSW_{s′}(s_{k−1})) を Bootstrapping Key と呼ぶ。

â ← ⌊a·(2n/q)⌉, b̂ ← ⌊b·(2n/q)⌉
Q₀ ← x^(−b̂)·RLWE_{s′}(Δv(x))
for j = 0 … k−1:  Qⱼ₊₁ ← CMUX(RGSW_{s′}(sⱼ), Qⱼ, x^âⱼ·Qⱼ)
return Q_k (= RLWE_{s′}(Δ·x^(−b̂+âs)·v(x)))

テスト多項式 v(x) は、a(x) = 0 としたノイズのない自明な暗号文 (0, Δv) とみなして初期値にできる。

秘密鍵を知っている左側:
Q₀=x⁻ᵇ̂v → s₀で回す/回さない → s₁で回す/回さない → …

秘密鍵を知らない右側:
Q₀=x⁻ᵇ̂RLWE(Δv) → 暗号化s₀のCMUX → 暗号化s₁のCMUX → …

Q.（講義が残した問い）x^i mod xⁿ+1 には negacyclic の性質があり、i ≥ n では係数の符号が反転する。Blind Rotation でこれが起こるとなぜ問題なのか。どうすれば回避できるだろうか。

Blind Rotation の出力 RLWE 暗号文 (a′(x), b′(x)) の b′ の定数項 b′₀ には Δm + e₀ が含まれている。あとは積 a′(x)s′(x) の定数項がどうなるかを調べればよい。

RLWE( Δ(m + μ₁x + μ₂x²+…) )
                 ↓ 定数項だけ
              LWE( Δm )

xⁿ ≡ −1 に注意すると、積の定数項は a′₀s′₀ − a′₁s′_{n−1} − ⋯ − a′_{n−1}s′₁ という「符号つきの掛けて足す」= 内積の形。だから a″ = (a′₀, −a′_{n−1}, …, −a′₁) と置けば、(a″, b′₀) は秘密鍵 s″ = (s′₀, …, s′_{n−1}) による平文 m の LWE 暗号文になる。

a′(x)=a′₀+a′₁x+a′₂x²+a′₃x³
s′(x)=s′₀+s′₁x+s′₂x²+s′₃x³

定数項に来るもの:
a′₀s′₀                         （最初からx⁰）
a′₁s′₃x⁴, a′₂s′₂x⁴, a′₃s′₁x⁴ （指数の和が4）

x⁴ ≡ −1 なので
b′₀のマスク部分 = a′₀s′₀−a′₁s′₃−a′₂s′₂−a′₃s′₁

Q. s″ で (a″, b′₀) が復号できることを各自確認。

抽出後の暗号文の鍵は s″ に変わっている。LWEₛ(a″s″) を引き算すれば鍵 s の暗号文に戻せる — が、毎回 a″ を委託元に送って暗号化して送り返してもらうのは避けたい。

Sample Extractionの直後:
        c = Enc_{s″}(m)   （平文m、鍵s″）

欲しい最終形:
        Enc_s(m)          （同じ平文m、元の鍵s）

事前に ksk[i,j] = LWEₛ(s″ᵢ·q/Bʲ⁺¹) を渡しておけば（Key switching key。Δ を使わないことに注意）、a″ の Gadget 分解の係数で ksk を組み合わせて引くだけで鍵を乗り換えられる。

LWEₛ(Δm) ← (0, …, 0, b′₀) − Σᵢ Σⱼ ā_{i,j}·ksk[i,j]

古い鍵: s″=3、古い暗号文の係数: a″=5
b″ = 5×3 + Δm = 15 + Δm

変換用データ: Enc_s(3)  （新しい鍵sで3を暗号化）
サーバー: 5×Enc_s(3) = Enc_s(15)
         b″ − Enc_s(15) → Enc_s(Δm)

二重和は Gadget 分解の再構成そのもので、まとめると LWEₛ(a″s″) になる。b′₀ = a″s″ + Δm + e₀ からそれを引くと (−ã, −ãs + Δm + e₀ − ẽ) — 秘密鍵 s による m の暗号文が残る。

Bootstrapping = 暗号文の形式と秘密鍵を変えながら、同じ平文 m の暗号文を作り直す操作。入出力は同じ形・同じ鍵・同じ平文で、ノイズだけが新しくなっている。

何をしているか: 普通の再暗号化ならいったん Dec_s(c) を平文で計算するが、Bootstrapping では秘密鍵 s も暗号化して渡し、復号処理そのものを暗号文のまま評価する。したがって m も s も見えず、古いノイズを引き継がない新しい Enc(m) が得られる（ノイズがゼロになるわけではない）。

入力 m=0,1 の例
恒等関数 f(m)=m:   0→0, 1→1
NOT関数 f(m)=1−m: 0→1, 1→0

回転と定数項抽出は同じ。
変えるのは、あらかじめ置く係数（v(x)）だけ。

テスト多項式の係数を mⱼ から f(mⱼ) に置き換えると、同じ Blind Rotation でノイズのリセットと関数 f の評価が同時にできる — 出力は LWEₛ(Δf(mᵢ))。

リスケーリングの丸めで回転先が少しずれても同じ値を取り出せるよう、同じ mⱼ に対応する複数の位置に f(mⱼ) を繰り返し置く。異なる平文が同じ位置に重なる場合、1 回の PBS で区別できるのは、それらの f(mⱼ) が同じときだけ。

回転量 i が n を超えると定数項の符号が反転する。v(x) = 1 + x + ⋯ + xⁿ⁻¹ なら定数項は 0 ≤ i ≤ n−1 で +1、n ≤ i ≤ 2n−1 で −1 — 1 回の回転で正と負の 2 値を表現できる。

この性質を bit 演算に利用する。

v=1+x+x²+x³
i=1: x⁻¹v = 1+x+x²−x³      → 定数項 +1
i=5: x⁻⁵v = −x⁻¹v
     = −1−x−x²+x³           → 定数項 −1

HomNAND = ① bit を 0 ↦ p−1, 1 ↦ 1 とエンコード ② c = (0, …, 0, Δ·1) − c₁ − c₂ を計算（c の平文は r = 1 − m₁ − m₂ mod p）③ 全係数 1 のテスト多項式で PBS ④ パラメータをうまく設定すると出力が NAND の暗号文になる。

3 < n < p−1 であれば、r = 1, 3 のとき定数項は反転せず 1 に、r = p−1 のとき反転して p−1 に — ちょうど NAND の真理値表と一致する。

(m₁,m₂)=(0,0): r=1−6−6≡3 (mod7) → 1
(m₁,m₂)=(1,0): r=1−1−6≡1 (mod7) → 1
(m₁,m₂)=(0,1): r=1−6−1≡1 (mod7) → 1
(m₁,m₂)=(1,1): r=1−1−1≡6 (mod7) → 0

具体例 p = 8, q = 32, n = 16, Δ = 4 — q = 2n なので Blind Rotation 時のリスケーリングは不要。入力暗号文のノイズの和 d ∈ {0, 1, 2} を含めても回転の番号の帯は分かれ、NAND の出力が読める。

(0,0):       r = 3  回転の番号 i = 10, 11, 12  定数項 1        → bit 1
(1,0),(0,1): r = 1  回転の番号 i = 2, 3, 4     定数項 1        → bit 1
(1,1):       r = 7  回転の番号 i = 26, 27, 28  定数項 −1 = 7   → bit 0

(0,0): r=3 → i=12−d = 12,11,10（全部0〜15） → 定数項+1 → bit1
(1,0),(0,1): r=1 → i=4−d = 4,3,2（全部0〜15） → 定数項+1 → bit1
(1,1): r=7 → i=28−d = 28,27,26（全部16〜31） → 定数項−1=7 → bit0

グループに分かれてテーマを調査・議論（イントロ 5 分 + 調査・議論 1 時間 30 分）し、2 グループ 1 組で発表 30 分（15 分 × 2）— お互いの発表にフィードバックする。

議論のテーマ: PBS の流れ（入力 LWE → Blind Rotation → Sample Extraction → Key Switching → 出力 LWE）のどこを、どんな工夫で速くしているかを TFHE-rs のドキュメントとコードから探す。

発表では、速くなる仕組みだけでなく「代わりに増えるコスト」と「新たに生まれた疑問」まで示す。工夫の個数に制限はなく、ソースコードを完全に理解する必要もない。参照先: github.com/zama-ai/tfhe-rs / docs.zama.ai/tfhe-rs。

① まず1つのサンプルを動かす（入力bit → 出力bit）
② PBSを4箱に分ける: Blind Rotation / Sample Extraction / Key Switching / 出力
③ 各箱で「速くする工夫」を1つ見つける
④ 速さの代償（メモリ・前処理・精度・実装の複雑さ）を1つ書く
⑤ 発表: 処理図に、工夫・根拠（docs/コード）・代償を3色で貼る

議論のテーマ: IND-CPA・IND-CCA1・IND-CCA2 を「攻撃者に許される操作」で比較し、FHE がなぜ non-malleability（頑強性）を満たせないのか、それが IND-CCA2 への具体的な攻撃にどうつながるのかを図または表で示す。

発展課題: IND-CPA のみを満たす FHE に対する鍵回復攻撃とその対策の概要（論文: eprint.iacr.org/2022/1563）。手がかり: indistinguishability game / encryption・decryption oracle / chosen-plaintext・chosen-ciphertext attack。

① 3つを表にする
   IND-CPA  : 平文を選んで暗号化してもらえる
   IND-CCA1 : さらに暗号文の復号も頼める（攻撃前）
   IND-CCA2 : チャレンジ後も復号を頼める（ただし挑戦文そのものは除く）
② FHEの操作 Enc(m) → Enc(f(m)) を書く
③ これは「暗号文を別の暗号文へ変形」なので non-malleability と衝突すると説明
④ その変形を使って、CCA2で何を見分けられるかを矢印で示す