関数型暗号(FE:Functional Encryption)
概要
公開鍵暗号では基本的に暗号鍵と復号鍵は同一人物の管理下にある。
Functional Encryptionは復号鍵を持っていても、暗号化されたデータの全ての情報を得るわけではなく、指定された関数に基づいた結果だけが得られる。この特徴を利用して暗号文を他人に共有したり、機密性を保ちながら限定的な情報や計算結果のみを取得することを可能にする。例えば属性ベース暗号では、ある属性を持つユーザであれば誰でも暗号文に特定の操作を加えたり復号することが許可される。
暗号鍵と復号鍵の関係を1:1ではなく、1:nやn:1に拡張できる点もユースケースを広げるだろう。
サンプル
FEにおける関数とは何か？イメージがつきにくいのでいくつかサンプルを示す。
抽象的な概念としてはあるデータに対して特定の条件や計算を行い、その結果だけを取り出す操作である。
例1: 集約計算を行うFE
仮に暗号化された社員データベースがあり、そのデータベースには各社員の給与が含まれているとする。通常の暗号化では、全ての給与データを復号してアクセスできる。しかしFEを使うと次のような「関数」を適用して特定の情報だけを復号できる。
関数: 「全社員の給与の平均を計算する」
結果: 復号後には給与の平均値だけが得られ、個別の給与データにはアクセスできない。
例2: 属性に基づくアクセス制御
クラウド上に暗号化されたファイルがあり、そこに「管理者」や「社員」などの属性が割り当てられている。
Functional Encryptionを使うことで、次のように特定の条件を関数として指定できる
関数: 「管理者のみがアクセスできる」
結果: 復号できるのは「管理者」の属性を持つ人だけで、他の人は復号できない。
このように予めユーザーが公開した公開鍵で誰かが情報を暗号化し、それを何かしらの関数に入れたとして、そこでの処理の道中で情報が漏れることはなく、ユーザーは所望の結果を復号し得ることができる。
A user Alice publishes her public key online and gives the spam filter a key for
the filtering function. Users sending email to Alice will encrypt the email with her public key. The spam filter
can now determine by itself, for each email, whether to store it in Alice’s mailbox or to discard it as spam,
without learning anything about Alice’s email (except for whether it was deemed spam or not).
The recent impossibility result of Agrawal, Gorbunov, Vaikuntanathan and Wee [AGVW12
分類
FEは以下の画像のように分類できる。
ここでPredicate(述語)とは暗号文に含まれる属性やデータが特定の条件を満たすかどうかを判断するための条件式のこと
ABE:属性ベース暗号、IBE:IDベース暗号の略称で、>HVEはHidden Vector Encryptionの略称で、ベクトル形式のデータが暗号化され、復号が可能かどうかはそのベクトルに対応する述語条件が満たされているかに依存する方式
https://scrapbox.io/files/67202af536760f58f233b9be.png
関数型暗号では暗号鍵と復号鍵がそれぞれ xと vでパラメータ化され，暗号鍵 ek_xと復号鍵 dk_vとなる．暗号鍵 ek_xで暗号化されたデータは，xと vに関する関係 R(x,v)がある条件を満足するときのみ復号鍵 dk_vで復号することができる．
暗号文を生成する者がどのユーザに暗号文を利用できるようにするかの条件(ポリシー)を指定できることを意味する
関係R(x,v)をどのように選択するかによって幾つかの方式がある
PE:Predicate Encryption
一般的なPEはベクトルの内積(Inner product)を使用するので、IPE:Inner-product encryptionと呼ばれる。
これは有限体上のベクトルx,vの内積が$ x ・v = 0の時にのみR(x,v)が成り立つという仕組み。
このxやvは属性や条件(Policy)を表す論理式に対応させる。
IBE :Identity-Based Encryption
x=vのときのみ R(x,v)が成立つ
関数的な観点でみるとIDベース暗号では、「このIDを持つユーザーのみが復号可能」という制約（関数）が機能している。
従って、復号の可否はID（関数の入力）に依存する
ABE :Attribute-Based Encryption
ekまたはdkに対応するパラメータの片方を属性の組、他方をアクセス構造とする。
どのように組み合わせるかで、下記のCP,KPに分類できる。
関数的な観点でみると「特定の属性を持つユーザーだけが復号可能」というアクセスポリシーが関数の役割を果たし、属性がその関数の入力となる。属性が条件を満たせば復号が可能。
CP:Ciphertext-Policy
あらかじめ属性に紐付いた鍵を配布する。
このように鍵に対しその任意の部分集合でしか復号できない暗号文を生成する
相手を特定する必要はなく、適切な鍵を持つ者だけが復号できる
アクセス構造が暗号文に、属性は復号鍵に埋め込まれる
KP:Key-Policy
様々な公開鍵で暗号化されてるデータに対し任意の部分復号が可能な鍵をあとから生成して配布する
鍵として与えられた権利範囲の暗号文が復号できる
アクセス構造が復号鍵に、属性は暗号文に埋め込まれる
アルゴリズム
Setup
パラメータvとXによって決まる関数fを定める。
マスター秘密鍵$ K_{prev}と公開鍵$ K_{pub}を生成する
Keygen
パラメータvによって決まる秘密鍵k_vを作成する
$ k_ v=KeyGen(K_{prev},K_{pub},v)
Encrypt
Xを公開鍵$ K_{pub}で暗号化する
$ c_X=Enc(K_{pub},X)
Decrypt
復号できるのは$ k_vを持っている人物のみである。
$ Dec(K_{pub},k_v,c_X)=f(v,X)
復号すると元の平文ではなく、関数に平文を入れた値が返ってくる。
Xをパラメータxと従来の平文の組X:=(x,m)としたとき、
if R (v,x)=true ... f(v,(x,m))=m
if R (v,x)=false ... f(v,(x,m))=null
となる
このif statementsは述語暗号に基づいており、ベクトルの内積(v,x)を計算することで検証できる。
どんな関数fでも使えるほど一般的な構成はできないらしく、iOを使えば可能であると提案されている
参考文献