準同型暗号とは

準同型暗号（HE）を使うと、暗号化されたデータに対して直接計算を実行できます。その結果として得られる暗号文を復号すると、平文に対して同じ演算を実行した結果と一致します。「復号せずに暗号文上で計算する」という考え方です。

側面に特別な手袋が取り付けられた、鍵のかかった箱の中に数字を入れると想像してください。箱を開けることなく、手袋を通して数字を操作（加算や乗算）できます。箱を開けたときに結果を見られるのは、鍵を持つ人だけです。

部分準同型暗号は、1種類の演算を回数制限なくサポートします。RSA（教科書的な方式）は乗法準同型であり、Enc(m1)*Enc(m2) = Enc(m1*m2)となります。Paillierは加法準同型であり、Enc(m1)*Enc(m2) = Enc(m1+m2)となります。電子投票やプライベート情報検索で使用されます。

限定準同型暗号は加算と乗算の両方をサポートしますが、乗算できる回数（回路の深さ）には制限があります。乗算するたびにノイズが増加し、しきい値を超えると復号に失敗します。Gentryが2009年に初めて構成しました。

完全準同型暗号は、暗号化されたデータに対する任意の計算（任意の論理回路や算術回路）をサポートします。Gentryは2009年に、「bootstrapping」によってFHEが可能であることを示しました。これは、復号回路を準同型的に評価して暗号文を更新し、ノイズをリセットする方法です。

ほとんどのHE方式は格子ベースです（BGV、BFV、CKKS）。暗号化すると暗号文にノイズが加わります。加算ではノイズが加法的に増加します。乗算ではノイズが乗法的に増加します。ブートストラッピングでは暗号文を準同型的に復号し、ノイズを初期レベルにリセットします。ブートストラッピングは高コストです。

FHEは現在でも平文計算より10^6倍遅いです。32ビット整数を1個暗号化するだけで、数キロバイトの暗号文が必要になります。ブートストラッピングにはゲート1つあたり数秒かかります。実用的なFHEの対象は、機械学習の推論、データベースクエリ、ゲノム解析など、特定のワークロードです。

ほとんどのHE方式は、Learning With Errors（LWE）またはRing-LWE（RLWE）の困難問題に基づいており、耐量子性があると考えられています。HEを破るにはRLWEを解く必要がありますが、RLWEに対して大幅な高速化を実現する既知の量子アルゴリズムはありません。

SEAL（Microsoft、BFV/CKKSをサポート）、HEAAN（Seoul National University、CKKS）、OpenFHE（オープンソース、BGV/BFV/CKKS/FHEW/TFHE）、HElib（IBM、BGV）があります。いずれも研究用途レベルであり、本番環境での導入はまれで、分野も限定されています。

医療ゲノミクスでは、ゲノムを明らかにせずに遺伝子データベースを検索できます。暗号化ML推論では、クラウドがデータの内容を見ることなく、ニューラルネットワークを実行できます。プライベート分析では、暗号化されたユーザーデータの統計を集計できます。機密性の高いポートフォリオを対象に、金融リスクを計算することもできます。

HEでは、ある当事者が別の当事者によって暗号化されたデータを計算します。MPCでは、複数の当事者が互いの入力を明らかにせずに共同で計算します。ハイブリッド方式では、オフライン前処理にHEを、対話型プロトコルにMPCを使用します。トレードオフとして、HEはレイテンシが高く、MPCは通信オーバーヘッドが発生します。

Homomorphic Encryptionを使用すると、暗号文に対して計算できます。PHEは1種類の演算をサポートし、SHEは限定的な深さをサポートし、FHEはブートストラッピングによって任意の回路をサポートします。これらはLWE/RLWEの困難問題に基づいています。次は、LWEの数学的基盤について学びます。