FHEにおける比較演算の実装

前提としてFHEは加算と乗算しかできない

比較演算を実装するための直感的なアイデアとしては加算と乗算から減算を実装し、減算結果の正負を判定できれば実現できそうである。しかし、BFVのように整数が多項式で表される場合、それぞれの係数を比較しても意味がない。

CKKS (Cheon-Kim-Kim-Song)

1.近似比較:

CKKSスキームは実数を扱うため、数値の差を計算し、その符号を確認することで比較を行います。直接的な比較は難しいため、差の絶対値がある閾値以下であるかどうかを確認することで近似的に比較を行います。比較関数をテイラー級数などで近似し、その多項式を暗号文に適用します。

2.ビット拡張:

比較対象の数値をビットごとに拡張し、各ビットの比較を行います。この手法は計算コストが高くなりますが、より精密な比較が可能です。

特徴

近似計算のため、厳密な比較ではなく、近似的な比較結果が得られます。

浮動小数点数の比較に適しています。

計算コストは比較的高いですが、バッチ処理による最適化が可能です。

TFHE (Torus FHE) スキーム

1.フルアダー回路:

TFHEでは、フルアダー回路を使用してビットごとの加算を行い、その結果を利用して比較演算を行います。ビットごとの操作が得意なため、効率的な比較が可能です。

2.LUTベースの比較:

ルックアップテーブル（LUT）を使用して、比較演算の結果をあらかじめ計算し、効率的に結果を取得する方法です。

特徴:

厳密な比較が可能です。

ビット単位の操作により、複雑な比較条件も実装できます。

他のスキームと比べて比較的高速です。

ブートストラッピングのオーバーヘッドはありますが、各ゲート操作後に行われるため、深い回路でも安定して動作します。

参考