公開鍵暗号の先へ：関数型暗号

従来の公開鍵暗号は、公開鍵で暗号化し、対応する秘密鍵で復号するという単純なモデルに従います。復号者は平文メッセージ全体を知ることになります。このオール・オア・ナッシングのモデルは、多くのアプリケーションにとって粗すぎます。たとえば、医療データベースでは、医師に患者の医療記録全体ではなく、特定の疾患があるかどうかだけを知らせたい場合があります。関数型暗号は、この限界に対処します。

IDベース暗号（IBE）は、Shamirが1984年に提案し、BonehとFranklinが2001年に構成した方式です。メールアドレス、ドメイン名、従業員IDなどの識別子文字列を公開鍵として使用できます。信頼できる鍵管理機関が、特定の識別子に対応する秘密鍵を生成します。IBEにより公開鍵証明書が不要になり、鍵の配布も簡単になります。IBEは関数型暗号の最も単純な形態です。

関数型暗号（FE）は、Boneh、Sahai、Watersが2011年に形式的に定義したもので、IBEを一般化したものです。FE方式では、鍵管理機関が任意の関数fに対する関数鍵sk_fを生成できます。暗号文Enc(x)と関数鍵sk_fが与えられると、復号者はf(x)を計算できますが、f(x)から明らかになる以上のxに関する情報は何も知ることができません。関数fには、その方式がサポートするクラス内の任意の計算可能な関数を指定できます。

内積関数型暗号では、sk_yを持つ復号者が、ベクトルxの暗号文から内積<x, y>を計算できます。これにより、プライベート機械学習推論が可能になります。ユーザーの特徴ベクトルxを暗号化し、モデル所有者に重みベクトルy用のsk_yを渡すと、モデル所有者はユーザーの特徴を知ることなく、ドット積（生の予測スコア）だけを得られます。実用的な内積用FE方式は複数存在します（ABDALLA et al. 2016）。

等価性テスト用FEを使用すると、暗号化された値が特定の値vと一致するかどうかを確認でき、等しいかどうかだけが分かります。これにより、プライバシーを保護したデータベースクエリが可能になります。サーバーが暗号化されたレコードを保持し、ユーザーが特定の値に一致するレコードを検索しても、サーバーはユーザーが何を検索しているかや、yes/noの一致結果を超える情報を知ることができません。実用的な構成では、双線形ペアリングが使用されます。

FEの中で最も強力な形態では、任意のブール回路または算術回路を関数としてサポートします。任意の多項式時間関数fに対するsk_fを持つ復号者は、Enc(x)からf(x)を計算できます。一般回路FEは、Garg、Gentry、Halevi、Raykova、Sahai、Waters（2013）によって多重線形写像を使用して理論的に構成されましたが、現在の一般FE構成は、不完全な多重線形写像の仮定に依存しているため実用的ではありません。

識別不能性難読化（iO）は、現在知られている中で最も強力な暗号プリミティブであり、機能暗号と密接に関連しています。iO方式は回路 C を受け取り、入力と出力の関係以外からは C に関する情報が何も分からない一方で、同じ関数を計算する難読化版 O(C) を生成します。iOからは、一般的なFEを含む、既知の暗号プリミティブの大半が導かれます。格子問題に基づく候補構成は存在しますが、実用化にはほど遠い状況です。

属性ベース暗号（ABE）は、関数 f がポリシー評価に制限された、実現可能性の高い機能暗号です。つまり、属性集合 x がポリシーを満たす場合は f(x) = 1、そうでない場合は 0 となります。ABEにより、復号権限をユーザーの属性に応じて決定する、きめ細かなアクセス制御が可能になります。ABEは機能暗号の中で最も実際に導入されている形式であり、クラウドストレージ、医療、IoTで実装されています。

FEの構成の歴史は、単純なものから強力なものへと発展してきました。IBE（Boneh-Franklin 2001）→ 等価性のためのFE（2005～2010年に複数の方式）→ 内積のためのFE（ABDALLA 2016）→ 有界深さ回路のためのFE（多重線形写像に基づく、2013年）→ 一般FE（iOから予想）。段階が進むほど高機能になりますが、同時に複雑さが増し、効率は低下します。実際の導入では、必要な機能を実現できる最も単純な形式が使われます。

FEの安全性は、2つのメッセージ x0 と x1 の暗号文が、任意の関数 f に対する関数鍵を与えられた場合でも識別不能であることによって定義されます。ただし、問い合わせたすべての関数について f(x0) = f(x1) が成り立つものとします。これにより、復号者が知り得るのは正確に f(x) だけで、それ以上の情報は得られないことが保証されます。セキュリティレベルには、選択的安全性（攻撃者が公開鍵を見る前にチャレンジメッセージを決める）と、適応的安全性（完全なシミュレーションベースの安全性）の2つがあります。

一般FEは依然として実用的ではありませんが、内積FEとABEは現在導入可能です。課題としては、信頼できる鍵管理者が必要であること（単一障害点となる）、鍵失効の複雑さ、ペアリング演算による性能オーバーヘッド、標準化の遅れなどがあります。研究の方向性には、単一の信頼された管理者を必要としないマルチオーソリティFE、分散鍵生成、多重線形写像を使わずにより大きな関数クラスを扱うFEなどがあります。

機能暗号（Boneh-Sahai-Waters 2011）は、IBEを一般化したもので、Enc(x) から x 全体を復元することなく f(x) を計算できる関数鍵 sk_f を提供します。内積FE（プライベートなML推論）や等価性テストでは、実用的な構成が存在します。ABEは、アクセスポリシーの評価に用いられる、実際に導入されている特殊例です。一般回路FEには多重線形写像が必要であり、実用的ではありません。iOは、関連するプリミティブの中で最も強力なものです。理論から効率的な実用へ移行することが、主要な課題です。