@kenmaroです。
普段は主に秘密計算、準同型暗号などの記事について投稿しています。
秘密計算に関連するまとめの記事に関しては以下をご覧ください。

秘密計算エンジニアを始めて１年が経った。

秘密計算エンジニアを始めて２年半が経った。

概要

準同型暗号を用いた際の計算には、平文で計算するときにはあまり気にしなかったことを気にしたりすることがあります。
また、そもそも暗号状態で計算できるというのがピンとこないときに、いくつか質問をいただいたことがあったので、
そのような疑問というのは他の方も気になっているのではないかと思い、ここにまとめてみようと思います。

注意

一般的な質問というよりも、技術的な質問の方が多かったので、少しマニアックな話になるのをご理解ください。

格子暗号って本当に安全なの？世界的に認められているの？

格子暗号は比較的新しい暗号であり、数学的にはその安全性は認められているものの、
世界的に標準化というのは今行われている真っ最中です。
詳しくは以前まとめたこの記事をご覧ください。

ついに来るか？主要格子暗号スキームのISO標準化

格子暗号での計算遅いって聞くけど、GPUとかで高速化できないの？

最近１、２年で、格子暗号（特にバイナリ型TFHE形式）をハードウェアで高速化する取り組みが行われています。
(記事は例えばこちらをご覧ください。Intel と MicrosoftがDARPAプログラムで準同型暗号のハードウェア高速化を目指す)

これは格子暗号の処理に特化したチップを作ってライセンス化しようとする動きですが、
汎用的なGPGPUを用いた高速化の取り組みも（少数ながら）あります。

このレポジトリは、メンテナンスされていて実際に動作を確認している数少ない、GPUを用いたTFHEのライブラリです。興味のある方はぜひご覧ください。

BFV、BGV形式などで出てくる、平文空間のモジュラスは計算にどう影響するのか？

論文などではtで表現されますが、平文空間で剰余多項式を用いたときの、各係数に対して適用するモジュラスについてです。
tは平文空間で使われるもジュラスなので、tは平文空間で許容できる最大値（つまり平文空間で演算中にtを超えるようなことがあるとオーバーフローする）となります。
例えばSEALライブラリのBFV形式を用いたとき、tは設定可能ですが、2^10 ~ 2^15程度のことが多いです。
つまり、BFV形式を用いた時の暗号状態の演算では、10~15ビット程度の精度を担保するものであり、
普通に平文で用いるような32ビットや64ビットレベルの精度を持った計算は（基本的に）難しいものになっています。
C言語などを使用する時のように、このビットに収まらないような演算を行った場合は計算がオーバーフローし、演算結果が壊れることになるので、暗号状態での演算には平文で行う時より、オーバーフローをより気にする必要があります。
よってtを大きい値で設定することは、オーバーフローを防ぐ意味で意義があります。
ただしtが大きくなるにつれてセキュリティが弱まるので、q（暗号空間のもジュラス）も大きくする必要があり、
それは演算速度、および暗号文データサイズを重くする要因となります。
したがって、精度ビットとセキュリティはトレードオフの関係となっています。

暗号状態でのセキュリティと精度のトレードオフなどについて、CKKS形式に限ってですが以前以下の記事に書いたので、
ぜひご覧ください。
結論を言うと、CKKS形式であれば１６ビット程度の精度は担保でき、AIの推論によく使われるFloat16(半精度)程度の精度で暗号状態でもML推論が可能です。

格子暗号のCKKS形式のパラメータ、精度ビットなどについて解説！（SEALライブラリ）

SEALライブラリのBFV形式で可能なバッチングと、CKKS形式のバッチングの違いはなんなのか？

バッチング、パッキングなどいろいろな呼び方がありますが、これは簡単に言えば「ベクトル」をそのまま暗号化する方式です。
これにより、数字を一つ一つ暗号するのに比べ、ベクトルに対して暗号文を１つ生成すれば良いので、暗号文の数を少なくすることができます。
この時１つの暗号文に入れることのできる平文の数には限りがあり、この数はスロット数と呼ばれます。
このスロット数は暗号パラメータに依存しますが、基本的にスロット数は使われる剰余多項式の次数の上限に依存します。
剰余多項式は、多項式を円分多項式で剰余をとっているものですが、この時の円分多項式の次数をNとした場合、
BFV形式であれば、スロット数はNとなり、CKKS形式であれば、スロット数はN/2となります。
両者の一つの違いとして、このようにスロット数の数に違いがあります。

以下はもう一点の両者の違いとなります。
BFV形式のパッキングは係数パッキング呼ばれ、CKKS形式のパッキングはCRTパッキング(Chinese Remainder Thorem)パッキングと呼ばれます。前述のスロット数の違いは、このパッキング方式が違うことに起因しています。

係数に入れるパターン（係数パッキング）、subRingにcannonical embedding して入れるパターン（CRTパッキング）はどちらが良いという話ではなく、用途によって使い分けることになりますが、最近準同型暗号を用いたAIなどを処理するアプリケーションにおいては、CKKS形式で用いられるCRTパッキングが使われることが多いです。

CRTパッキングにおいて、暗号文に入れたベクトルに対しての演算は、通常のnumpy array などを用いた時のような演算が可能なため、ベクトル演算などと相性が良いです。
一方で係数パッキングを用いた時は、各平文は多項式の係数に埋め込まれており、暗号文同士の掛け算は、多項式同士の計算を行うため、用途は限られます。多項式同士の計算を行うと、ベクトル同士の内積を効率的に求めることが可能なため、
そのような要件のあるシナリオでは効果的になることもあります。
詳しくは以前にまとめた記事がありますので、ぜひご覧ください。

準同型暗号を用いた高速化の例

GSW形式の用途はどんなものなのか？単体で使うことはあるか？

GSW形式というのは、TFHE形式暗号同士の掛け算を実行するときに用いられる、TFHE形式の拡張版のようなものです。
TFHE形式は暗号文をベクトルのように表現しますが、GSW形式ではそれをBitDecomposeと呼ばれる展開を用いて拡張し、
行列のように表現します。

GSW形式を用いることで、TFHE形式の暗号同士の掛け算を実行できると書きましたが、これにより、MUXゲートを暗号状態で実行することができます。（マルチプレクサゲートの詳細はこちら　https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%83%81%E3%83%97%E3%83%AC%E3%82%AF%E3%82%B5）

このMUXゲートにより、結果的に暗号文のブートストラップ（ノイズを除去する操作）が可能になります。
したがって、GSWの用途は基本的にブートストラップ（BS)を実装することである、といっても間違いではないと思います。
実際にGSWもGSWで準同型暗号として完結できますが、他の形式よりとても遅く重いので、実質的にGSW形式を単体として扱うということはなく、あくまでもTFHE形式を扱う時に、マルチプレクサを実装する際に用いる、と考えて良いでしょう。

TFHE形式以外にもブートストラップは可能なのか

一般的には可能です。暗号形式によってBSのアルゴリズムが違うので、ブートストラップのアルゴリズムも異なります。
これは、ブートストラップが原理的には、暗号形式の復号回路を、準同型的に実行する、ということだからです。（形式により復号回路に差異があれば、もちろんブートストラップを実行する時のアルゴリズムも異なります。）
以前TFHE形式のブートストラップについては、いくつか記事を書きました。（CKKS形式についてはまだ書いてませんが、、、）
ただあまりわかりやすくまとめられていない気がしているので、もう少しどうにかならないかなあという気持ちです。
もし興味がある方がいらっしゃいましたらぜひご覧ください。

TFHEのブートストラップを理解したい人生だった (ビジュアル編)

上でも書いていますが、TFHEにおけるBSは自身の復号回路を暗号状態で行うというよりも、入力となったLWEの似たようなコピーを一定のノイズで、かつ秘密鍵なしで作る、という考え方の方がしっくりくるため、CKKS形式のBSのように忠実に復号回路を暗号状態でおこなうようなものとは少しだけ考え方が違うかな、とも思います。

CKKS形式のブートストラップはどのように行われるか

例えばCKKSではmod演算をsine関数の近似を暗号状態で行うことで自身の復号回路を計算しています（つまり暗号状態でモジュラスをとりたいわけであり、HomModを実行しなければならないということです。）。
HomRoundは基本的にCKKSやTFHEでは必要です。
理由はCKKSやTFHEが後に言及のあった統計的な誤差処理を行っているからなのですが、CKKS
やTFHEのBSは暗号文にBS実行の時に乗ってくるノイズを付与したものを結果として出力するため、
ラウンドを行うようなBFV形式のように誤差の出ない暗号計算とは異なり、本質的に計算誤差を許容したものがTFHEやCKKSとなります。

RLWE問題とLWE問題って何が違うの？

全く質問には答えていませんが、まずはLWE問題について理解することが必要です。
結果的にwikiが一番わかりやすい気もしており、一応リンクを貼っておきます。
https://en.wikipedia.org/wiki/Learning_with_errors

LWE問題では出てくるものは乱数と暗号鍵の内積であり、どちらもベクトルです。
RLWE問題では乱数や暗号鍵が多項式になります。これらの多項式は剰余環上で定義されているため、
RLWE問題はLWE問題を並列で多項式の次元数N分だけ並列で利用しているようなイメージになります。

RLWE問題の安全性はRegevによって既に証明されていますが、RLWEではLWEではできないような攻撃が考案される可能性があるかもしれない、というところがあり、それがもし発見されたとすれば、RLWEはLWEに対して制限されたセキュリティ強度しかないということになりますが、今のところ大丈夫のようです。

鍵の選び方に方式はあるのか？

BFV,CKKS、TFHEなどを通して鍵の選び方はだいたい[0,1]のバイナリタイプか、[-1, 0, 1]のタイプ（名前を忘れました、、）のタイプに分かれます。
[-1, 0, 1]のタイプは実際にはライブラリではほとんど使われず、ほとんどの実装はバイナリ鍵を使っています。
TFHEだからバイナリ鍵というわけではなく、CKKSやBFVでもバイナリ鍵を使っています。

暗号形式によるセキュリティ強度の違いはあるのか？

格子暗号の形式は全てセキュリティの根底にLWE問題、もしくはRLWE問題を持っています。
したがって鍵の選び方で将来的なセキュリティ評価が決まるわけではなく、あくまで裏で動いているセキュリティを担保する数式、つまりLWE、RLWE問題が破られるかどうかでセキュリティ的な評価が決まります。
この意味で、CKKS、BFVは同じ数学を用いているので破られた時は同時に破られるだろうし、TFHEはトーラス上でのLWE問題であるため、トーラス上のLWE問題を破るために特化した攻撃が見つかったとすれば、TFHEのみセキュリティ評価が低くなり、BFVとCKKSの評価は変わりません。
したがって理想的には全ての形式を使えるようにしておいた方が、セキュリティのオプションとしては高まることが予想されます。

TFHE の　BS関数の出力は TLWE? TRLWE?

これについては最先端の秘密計算技術、格子暗号スタディロードマップを公開！！（エンジニア、リサーチャー必読でも紹介した
@nindanaoto さんの講義資料　https://nindanaoto.github.io/
を参照するのが一番わかりやすいとは考えますが、TLWE形式にBSを施した時（すなわちBllindRotateをし終わった時）の出力はTRLWEとなっています。
あくまで最初に出てくるものはTRLWEであり、それに対してSample Extractを行うことで目当てのTLWEを出力します。
実質的にBSの本体はTRLWEを行った時に終わっているのですが、
実装上はこの操作をラップしてあたかもBS(TLWE) → TLWEとなるような形わかりやすくまとめることが多いです。
CKKSであればBSにはRLWEが入り、RLWEが直接出てきますし、またはLWEが入ってLWEが出てくると考えて差し支えないです。

TFHE と　TFHE亜種（Zamaのプログラマブルブートストラップ形式）の本質的な違いはなんなのか？

TFHEのデメリットは、BFVのt=2と同じなので、全ての演算をバイナリ回路にする必要があることです。
ただこれはメリットと捉えることもでき、任意のバイナリゲートを暗号状態で実行可能なため、どんな計算も実行できます。
つまりTFHEを用いると、単純な足し算も全加算器をソフトウェア上で実装することになります。（ここをハードウェア化すればいいかも？）
一方プログラマブルブートストラップの手法（TFHE亜種：Zama形式）のメリットは実数のエンコーディングとLUTの組み合わせで、バイナリ回路を計算する必要がなく、また、LUTはBSの応用として実装されるのでどんな関数でも一定時間で、またいつも同じ回路により実装できることです。
（したがって、LUTを高速化するような回路さえ作ってしまえば全部の演算が高速化するし、TFHEのように演算によって通すバイナリ回路を変形する必要がない。）
実装下においては、演算は異なるLUTを搭載した連続的なPBSをLWEに対して順番に施していくようなプログラムになります。

Zama形式のPBS形式などについては他に記事を書いておりますので、ぜひご覧ください。

格子暗号で新ブレイクスルー！！プログラマブルブートストラップを解説！！

まとめ

今回はいくつか格子暗号の技術的なところについて質問を聞くことが多かったものについて、
せっかくなのでまとめてみました。

もし参考になったという方がいたらとても嬉しいです。

誰かの持つ質問は、きっと他の誰かも疑問に思っていることだと思いますので、
もしなにか格子暗号周りで質問がある方がいらっしゃいましたらいつでも聞いてください。
お待ちしております。

今回はこの辺で。

@kenmaro