準同型暗号 (FHE)

暗号文のまま加算・乗算を評価でき、復号すると平文に同じ演算を施した結果が得られる暗号。秘密計算（secure-multiparty-computation、TEE と並ぶ三本柱）の中核技術で、クラウドにデータを渡さず計算を委譲できる。

スキームの系譜

SHE / Leveled HE: 評価のたびにノイズが増え、回路の深さに上限がある。乗算の乗法的深さが消費を支配する。
FHE: ノイズをリセットするbootstrappingを備え、任意深さの回路を評価できる。

世代	スキーム	基盤
2009	Gentry scheme	イデアル格子。世界初の FHE
2010	DGHV	近似 GCD（整数上）
2011	BV scheme	LWE、modulus switching
2012-	BFV	RLWE、整数 SIMD
2013	GSW	eval key 不要
2016-	CKKS	RLWE、近似（固定小数点）
2016-	CGGI	torus、高速 bootstrap

LTV/YASHE は NTRU ベースだが安全性問題で廃れた。Functional Encryption や indistinguishability Obfuscation との理論的関係も研究対象。

共通する技術要素

基盤問題: ほとんどが格子上の LWE / Ring-LWE の困難性に依拠。耐量子性を持つ。
ノイズ管理: 乗算でノイズが急増。CKKS の rescale、BGV/BFV の modulus switching で modulus chain を降りながら抑える。
relinearize: 乗算で 3 成分に増えた暗号文を 2 成分へ戻す key-switching。
SIMD / batching: CRT エンコードで $N /2$ 個の値を 1 暗号文に詰め、回転鍵で slot を巡回シフトする。

応用とエコシステム

PPML: 暗号化したまま推論・学習。
HE コンパイラ: パラメータ選択・rescale 挿入を自動化。
FHE ライブラリ: HElib、Microsoft SEAL、Lattigo、HEAAN、concrete。

参考: 早稲田大山名研、筑波大西出研などが国内の主な研究拠点。

BGV / BFV スキーム

整数（有限体 $Z_{t}$ ）上の正確な演算を行う準同型暗号。ともに Brakerski-Gentry-Vaikuntanathan の “(Leveled) FHE without bootstrapping” 系譜に属し、Ring-LWE を基盤とする。近似演算の CKKS と対になる二大系統。

BGV

BV scheme（2011）に modulus switching を導入し、平文空間を 1 bit から複数 bit（ $Z_{t}$ ）へ拡張。
乗算後に modulus chain を 1 段降りてノイズを線形に抑える。ノイズはメッセージとは別の下位ビットに乗る。
HElib が代表的実装。理論的には fully-homomorphic-encryption とほぼ同じ構造（rescale/mod-switch の扱いが異なる）。

BFV

BGV の後継。scale-invariant な方式で、メッセージを最上位ビットに置き modulus switching を明示的に行わない。
乗算結果はrelinearizeで 2 成分へ戻す。
Microsoft SEAL の主要スキーム。

SIMD batching

平文多項式を中国剰余定理で分解すると、 $Z_{t}$ の複数 slot を 1 暗号文に詰めて並列演算できる（Smart-Vercauteren の Fully Homomorphic SIMD Operations）。slot 間の移動は Frobenius / 回転で行う。

比較演算

整数 FHE では大小比較が非自明で、多項式近似や桁ごとの回路で実装する（Faster homomorphic comparison for BGV and BFV）。

実装: Microsoft SEAL。関連クラスタ: _moc-crypto

CKKS スキーム (HEAAN)

Cheon-Kim-Kim-Song が論文「Homomorphic Encryption for Arithmetic of Approximate Numbers」で提案した、実数・複素数の近似演算に特化した準同型暗号。実装名から HEAAN とも呼ばれる。固定小数点演算をネイティブに扱えるため機械学習応用の主流。

エンコード

$N /2$ 次元の複素ベクトル $z$ を、スケーリングファクタ $Δ$ を掛けて多項式環 $R = Z [X] / (X^{N} + 1)$ の元へ写す:

$m (X) = σ^{- 1} (⌊ Δ \cdot π^{- 1} (z)⌉)$

$σ$ は標準埋め込み（Vandermonde 行列で表せる）。 $Δ$ が大きいほど精度が上がる代わりにノイズ余裕を食う。

スキーム

鍵生成はRing-LWE 性 $b + a s = e$ を満たす pk と、 $s^{2}$ を暗号化した evk を持つ。
Add: $ct + ct^{'}$
Mult: 暗号文を掛けると 3 成分になるので evk でrelinearizeして 2 成分へ。
Rescale: 乗算後に modulus chain $q_{ℓ} = p^{ℓ}$ を 1 段降り、スケールを $Δ$ に戻してノイズを抑える。レベルを消費する。
Rotation / Conjugation: ${1, 5, \dots}$ が $Z_{2 N}^{\times}$ の部分巡回群をなすことを使い、 $Y \mapsto Y^{5}$ で slot を回転。回転鍵 rk・共役鍵 ck が必要。

RNS variant

係数をRNS（中国剰余定理）表現で複数の機械語素数に分解し、多倍長演算を排して高速化する。実装はほぼこの RNS-CKKS を使う。

Bootstrapping

CKKS は本来 leveled だが、復号写像 $[t]_{q}$ を $S (t) = \frac{q}{2 π} sin (\frac{2 π t}{q})$ で近似評価して FHE 化する。詳細は fully-homomorphic-encryption。CoeffToSlot→EvalExp→SlotToCoeff の流れで、線形変換は BSGS で最適化する。

安全性の注意

近似であるため復号結果がノイズを漏らす攻撃が指摘されている（On the Security of HE on Approximate Numbers）。

実装: Microsoft SEAL。関連クラスタ: _moc-crypto

TFHE / CGGI スキーム

Chillotti-Gama-Georgieva-Izabachène が提案（“Faster FHE: Bootstrapping in less than 0.1 Seconds”）した、torus 上で動作するFHE。1 ビット演算ごとに高速 bootstrap を回すアプローチで、任意のブール演算・非線形関数を扱える。

構成要素

トーラス $T = R / Z$ 上で 3 種類の暗号文を使い分ける:

TLWE: スカラー（ $T$ ）
TRLWE: 多項式（ $T [X]$ ）
TRGSW: torus 上で GSW を模した行列暗号文。bit decomposition / flatten を用いる。

平文が直接見えてしまうのを防ぐため $Enc (0)$ を足してマスクする。

Programmable Bootstrapping (PBS)

TFHE の bootstrap は単にノイズを消すだけでなく、任意の 1 変数関数をルックアップテーブルとして同時に評価できる（programmable bootstrapping）。CKKS/BGV が苦手とする非線形関数（活性化関数など）を正確に計算できるのが強み。深層ニューラルネットの暗号化推論に応用される。

Integer-Wise Functional Bootstrapping: 整数全体に関数を適用する拡張。
CKKS（算術型・SIMD 並列）とは相補的で、両者を変換する CHIMERA / 浮動小数点表現の研究もある。

実装

concrete（Zama）が programmable bootstrapping を提供。
axell-corp/oveus-tfhe など。

bit 演算が得意な反面 SIMD 並列性は弱い。算術型 FHE との対比は fully-homomorphic-encryption を参照。関連クラスタ: _moc-crypto

FHE Bootstrapping

暗号文に溜まったノイズを、復号写像そのものを準同型評価することでリセットし、ふたたび乗算可能な状態へ戻す操作。Gentry が初めて示した FHE 化の鍵で、これにより leveled HE が任意深さの回路を扱える真のFHEになる。

CKKS の bootstrapping

CKKS の recryption は次の流れ（Cheon らの 2018 論文）:

MODRAISE → COEFFTOSLOT → EVALEXP → IMGEXT → SLOTTOCOEFF

Modulus raising: $ct (mod q)$ を大きな modulus $Q_{0}$ へ持ち上げると $t = q I + m$ の形になる。
CoeffToSlot: 係数表現 $(t_{0}, \dots, t_{N - 1})$ を slot へ移す線形変換。
EvalExp: 復号の剰余 $[t]_{q}$ を直接評価できないので $S (t) = \frac{q}{2 π} sin (\frac{2 π t}{q})$ で近似。 $exp (i θ / 2^{r})$ を $r$ 回 2 乗する 2 倍角公式で実装する。
SlotToCoeff: 逆変換で元へ戻す。

誤差は $∣ F (t) - S (t) ∣ = O (q \cdot ∣ m ∣^{3} / q^{3})$ （マクローリン展開 $x - sin x < x^{3} /3!$ より）。

高速化の系譜

Better Bootstrapping: Taylor は高次で不安定なので回避。
Improved Bootstrapping: Chebyshev 補間で深さを最適化、CoeffToSlot を FFT 風に分解。Lattigo v2 に実装。
Non-Sparse Keys（2021）: 多項式評価・key-switch を最適化し double-hoisting を導入、約 14 倍高速。
GPU / memory-centric: モジュラ乗算をメモリ中心に最適化し 100 倍超の高速化。

線形変換（CoeffToSlot/SlotToCoeff）はbaby-step giant-step (BSGS)で回転回数を減らすのが定石。TFHE の bootstrapping は逆にビット単位で頻繁に回し、関数評価も兼ねる（programmable bootstrapping）。

ElGamal 暗号と準同型性（暗号化バイラテラル制御）

ElGamal 暗号は離散対数の困難性（ecdh-key-exchange と同じ DH 系の仮定）に基づく公開鍵暗号で、乗法準同型性を持つ。すなわち暗号文同士の積を復号すると平文の積になる:

$Dec (Enc (m_{1}) \cdot Enc (m_{2})) = m_{1} \cdot m_{2}$

一方で加法は素直には計算できないため、行列積のような線型演算をそのまま暗号文上で計算できないという制約がある。

暗号化バイラテラル制御という応用

マスタ・スレーブ間の遠隔操作で使うバイラテラル制御（双方向の力・位置フィードバック制御）を、制御則そのものを暗号化したまま実行したい、という秘密計算の応用がある (2025-05 のメモ)。

制御則の本質は係数行列とのベクトル積（線型演算）。
素の ElGamal は乗法準同型しか持たないため、暗号文のままでは行列積を計算できないはず。
これに対し「修正された乗法準同型暗号方式」を使うと暗号化された行列積が計算できる、とされる（cf. JACC 65 (2021) 152）。詳細な仕組みは要精読 (TODO)。

位置づけ

完全準同型暗号 fully-homomorphic-encryption は加法・乗法の両方を任意回数扱えるが重い。ElGamal のような部分準同型 (partially homomorphic) は演算が限定される代わりに軽量で、線型制御則のような限定的な計算に向く。
入力を秘匿したまま計算する技術の全体像は secure-multiparty-computation / privacy-preserving-machine-learning を参照。
制御理論側の背景は control-theory-laplace。

tags	crypto, fhe, homomorphic-encryption, lattice, bgv, bfv, rlwe, ckks, approximate-arithmetic, tfhe, torus, programmable-bootstrapping, bootstrapping, noise, elgamal, control-theory, secure-computation
aliases	bgv-bfv-schemes, ckks-scheme, tfhe-cggi-scheme, fhe-bootstrapping, elgamal-homomorphic-encryption

過ぎるだけの時間じゃ悔しい

Explorer

準同型暗号 (Fully Homomorphic Encryption)