突貫で書いてしまった部分もあるので、大いに誤りを含む可能性があります。誤字・脱字レベルでも構いませんので、ご指摘ください。
また、予告なしに内容の加筆や構成の変更を行うことがありますが、読みやすくするためのものですので、ご容赦ください
自己紹介
秘密計算のスタートアップで働いている社会人１年目です。
普段は、秘密計算の研究や社会実装を行なっています。
学生時代は、耐量子計算機暗号（特に格子暗号の電子署名方式）を研究していました。
概要
本記事では, 仕事で TFHE を勉強する機会をいただいたため,
その際に勉強してみての感想を書きたいと思います。
TFHE とは
TFHE とは 「Fast Fully Homomorphic Encryption Over the Torus」の頭文字を取ったもので, 完全準同型暗号 (FHE: Fully Homomorphic Encryption) の一種になります。(TFHEの原論文)
理解しやすい部分
TFHE の理解しやすい部分はずばり、
- TFHE 内で用いられるアルゴリズムを絵で表しやすい
です。
TFHE 方式内では, Gadget Decomposition, External Product, CMux Gate など様々なアルゴリズムが用いられるのですが, 絵を使って説明しやすいようなアルゴリズムが多々あります。
例えば, CMux Gate は TRGSW 暗号文(TRGSW ciphertext)と2つの TRLWE 暗号文(TRLWE ciphertext)を入力として受け取り,
TRGSW 暗号文の平文(plaintext)の値に従って, TRLWE 暗号文のいずれかを出力するアルゴリズムなのですが, これを図示すると以下のように描けます。
理解が難しかった部分
反対に、TFHE で理解しづらかった部分は,
- level(lvl) という概念
です。
TFHE では, アルゴリズムが実行されるたび暗号文内にノイズというものが蓄積されていきます。
これがある一定の許容値を超えると, 暗号文を正確に復号することができなくなってしまいます。
ノイズがどれくらい蓄積されるかは各アルゴリズムごとに異なるため,
TFHEでは lvl という概念を用いて, それぞれの lvl ごとに実行できるアルゴリズムを定め，それらに応じてパラメータを使い分けています。
例えば, 以下の TFHEpp という @nindanaoto さんらが開発する, TFHE 方式を実装したライブラリがあり,
このライブラリの中の
というフォルダーにパラメータ関連のコードがまとまっています。
その中の 128bit.hpp ファイル には 128 bit secruity を満たすようなパラメータが書かれています。
このファイルを覗くと分かる通り, lvl0param, lvlhalfparam, lvl1param などといった具合で各 lvl ごとにパラメータが分けられているのですが,
このような概念は準同型暗号特有なものになります。
TFHE を勉強している際には, 常に今自分がどの lvl 上での議論をしているのかを意識しなければならず, 混乱する場面が多々ありました。
Tips: 因みになのですが, CKKS のレベルとは異なる概念であり, CKKS のレベルは、乗算回路の深さ（大雑把には、乗算回数の上限）を表します。
まとめ
TFHE の勉強をしていた際, CMux など TFHE 内で用いられる多くのアルゴリズムが図示しやすかったことは, 理解を進めるうえで非常に助かったと記憶しています。
一方で, lvl とパラメータの使い分けは理論理解や実装の際に常に意識する必要があり, 常に悩まされた印象です。
このように, TFHE はアルゴリズム単体の直感的な理解はしやすい一方で,
lvl やパラメータ設計のような「複数のアルゴリズムを組み合わせて暗号全体を成立させる部分」で難しさが一気に増すように感じました。
TFHEpp などのオープンソースが増えてきているので，次は lvl やパラメータ設計をもっと簡単にできるようなツールが更に整ってくれば，今回自分が悩まされた部分もかなり解消されそうだなと思います。