概要

準同型暗号とは、

暗号化したまま計算することができる暗号

のことです。

準同型暗号にはいろいろな種類（いろいろな数学的構築）が存在していますが、
その中でも「格子暗号」は「完全準同型暗号」と呼ばれ、期待度が高い暗号形式です。

この「格子暗号」についてもいくつかの形式が存在
し、理解するのが少しややこしいです。

今回はこの「格子暗号」の中でも一番よく使われている（もしくは研究されている）

CKKS形式
TFHE形式

について、両者の違いやそれぞれの良さについて解説してみます。

CKKS形式

始祖論文

CKKS形式は2016年に

この論文で発表された格子暗号形式のことです。

特徴

一番の特徴は、少数をそのまま暗号化できることです。

CKKS形式より以前のBFVやBGV形式では、暗号化できるのは整数のみでした。

実際にアプリケーションで使用する時に、
少数に大きな数をかけて整数に丸めてから暗号化するのはあまりいいユーザイクスペリエンスではなかったため、
CKKS形式が少数をそのまま暗号化できることは大きなメリットです。

得意とする演算

CKKS形式では、BFVやBGV形式を踏襲した、SIMD演算を行うことができます。

わかりやすく言うと、
少数を要素としたベクトルをそのまま暗号化し、暗号状態でベクトル演算を行うことができます。

従って、線形演算を効率的に実行することが可能です。

例えば２つの暗号化されたベクトルに対して内積を取ったり、
暗号化された行列と暗号化されたベクトルを掛け合わせたりすることができます。

苦手とする演算

線形演算以外の、非線形演算を実行することは難しいです。

例えばサイン、コサインのような演算、expの様な演算は、
テイラー展開と呼ばれる近似式を用いてしか実行できません。

また、暗号同士の比較演算も原則実行できません。(*1)

max関数やmin関数をCKKS形式の暗号に対して実行することは基本的にはできません。

このような演算を実行したい時は、ユーザに一時復号をしてもらって実行するか、
もしくは近似を使うか、CKKS形式のLUT（ルックアップテーブル）を使う必要があります。
LUTを使うのは現在の技術では非常に難易度が高いため、現実的には近似が一時復号が落とし所になります。

(*1) 比較演算をCKKS形式で実装することも可能は可能ですが、準同型暗号の計算だけではなく、紛失通信などを含んだ「通信ありきの」プロトコルが必要となります。詳しく知りたい場合は

こちらをご覧ください。

よく使われるライブラリ

一番有名でユーザが多いのは、マイクロソフトリサーチが管理しているSEALライブラリです。

しかしながら、最近整備が行われているのが

こちらのOpenFHEです。

また、Go言語で書かれている

Lattigo にも非常に強力なCKKSの実装がなされています。

もし言語の好みがないのであれば、OpenFHEから始めるのがいいのでは、
と思います。

TFHE形式

始祖論文

TFHE形式は２０１８年に発表された格子暗号の形式の一つです。

特徴

ビットを暗号化する形式です。

BFVやBGV形式が整数を、CKKS形式が少数を暗号化する一方で、ビットを暗号化するため、
演算は基本的にバイナリ回路がベースになります。

また、SIMD演算も基本的にはできません。
従って、１０ビットの暗号を作りたければ、１０個の暗号を作る必要があります。

そのため、CKKS形式などに比べると少数を要素としたベクトル演算などはかなり実行に時間がかかります。

得意とする演算

NANDなどをはじめとしたビットを入力とする演算をサポートしています。

また、それらの演算を制限なしに何度でも暗号状態で計算できるため、
時間はとてもかかるものの、暗号状態でどんな演算でも実行可能です。

入力ビットが０か１かによって出力がかわるマルチプレクサも暗号状態で実行することができます。

CKKS形式では難しかったmaxやmin、比較演算も実行することも可能です。

苦手とする演算

NAND回路が任意回数計算できるため、基本的にすべてのバイナリ回路を暗号状態で計算できるのですが、

問題点は演算速度です。

現状汎用CPUでNAND回路を暗号計算する時にかかる時間は50ミリ秒程度ですから、

すべての演算を暗号状態で行いたければ、20ヘルツのPCで計算する様なことになります。

したがって、現実的に計算をすべて暗号でしようとすると非常に実行時間が長くなるため、
この「遅さ」が欠点となります。

素朴な疑問

CKKS形式とTFHE形式どちらが安全とかあるの？

CKKS形式とTFHE形式はどちらも

格子暗号の「LWE問題」と呼ばれる数学的に解読困難な問題をセキュリティの基盤としている

ため、どちらも同じセキュリティに基づく、と言うことができます。

しかし、ライブラリによってそのLWE問題に設定するパラメータが異なることがあり、
セキュリティはそのパラメータに依存しているため、どのようなパラメータを使っているかには注意が必要です。

CKKS形式のパラメータ（SEALライブラリを使う時）については

こちらの記事を参照してください。

どちらが計算が遅い？

何の演算をしたいかによりますが、一般的にはCKKS形式が大きく有利になります。

例えばベクトルとベクトルの内積をCKKS形式とTFHE形式で実行しようとすると、
圧倒的にCKKS形式の方が速く終わります。

ただし、前述の通りCKKS形式はそもそも暗号状態で計算できない演算があるため、TFHE形式が実用上有利になることもあります。

CKKS形式でナイーブに暗号状態での足し算、掛け算などを実測した結果（SEALライブラリを利用）は、

こちらなどをご覧ください。

どちらが暗号文が重い？

同じサイズの平文を暗号化しようとすれば、TFHE形式の方が圧倒的に大きくなります。

例えば、TFHE形式の暗号文は数キロバイトから数十キロバイト程度ですが、この暗号には１ビット分の情報しか入れることができません。
CKKS形式では１つの暗号文は１００キロバイト以上になることもありますが、
少数を1000個くらい１つの暗号文に入れることができます。

従って、トータルで見ればCKKS形式の暗号の方が軽く、TFHE形式の方が重くなります。

SEALライブラリを使った時のCKKS形式の暗号サイズについては、

こちらを参照してみてください。

どちらが将来使われそうか？

これは難しい質問ですが、仮に今現状の演算速度を１万倍にする専用ハードウェアなどが開発されたと仮定すると、TFHE形式の方が使われるのではないかと思います。
理由はやはりCKKS形式には演算できないものがあるからです。

しかしながら、CKKS形式の線形演算は非常に高速であり、演算速度も進化していますから、CKKS形式はこれからも使われていくでしょう。

どちらを最初に勉強した方がいい？

これも難しい問題ですが、TFHE形式の始祖論文を理解するのは一つのゴールにしていいと思います。
今から勉強するのであれば、TFHE形式を勉強しつつ、何か使ってみたい時はCKKS形式を使って秘密計算を実装するのがいいのではないでしょうか？

もし格子暗号について勉強したかったら、

これをフォローするのをお勧めします。

使われているライブラリ

CKKS形式の時にも紹介したC++で書かれた

OpenFHEと、

Go言語で書かれている

に加えて、ZamaAIが開発しているRustで書かれたライブラリ

の３つがとりあえずの選択肢になるかと思います。

最後に

今回は格子暗号でも現在の花形である２つの形式

CKKS形式
TFHE形式

について両者の違いやメリットなどについてまとめてみました。

秘密計算の領域は非常に広く、そして各分野は数学的に深いので、
格子暗号だけでもフォローするのは難しいですが、非常に面白い分野なのは確かです。

もし興味があれば勉強してみるのはいかがでしょうか。

今回はこの辺で。

@kenmaro