• ホーム
• 情報セキュリティ
• 暗号技術

関数型暗号

関数型暗号とは

• 概要
  伝統的な暗号システムでは，暗号鍵 ($ek$) により暗号化されたデータは対応する復号鍵 ($dk$) によってのみ復号でき，この関係は固定的である．すなわち，暗号化されたデータは復号鍵を持つ特定の個人のみ利用することができる．
  関数型暗号 (Functional Encryption) は，これに対し暗号化データを幅広く共有する可能性を提供する新しい手法である．関数型暗号では，暗号鍵と復号鍵がそれぞれ $x$ と $v$ でパラメータ化され，暗号鍵 $ek_x$ と復号鍵 $dk_v$ となる．
  暗号鍵 $ek_x$ で暗号化されたデータは，$x$ と $v$ に関する関係 $R(x, v)$ がある条件を満足するときのみ復号鍵 $dk_v$ で復号することができる．このことは，暗号文を生成する者が，どのようなユーザに暗号文を利用できるようにするかの条件(ポリシー)を指定できることを意味する．
  関数型暗号は，インテリジェント暗号とも呼ばれている．
  
  関数型暗号には，関係 $R(x, v)$ をどのように選択するかにより，次のような幾つかの方式がある．
  • IBE (Identity-Based Encryption)
    $x = v$ のときのみ $R(x, v)$ が成立つ．すなわち，通常のIDベース暗号である．
  • ABE (Attribute-Based Encryption)
    $ek$ または $dk$ に対応するパラメータのどちらかが属性の組であり，他方がアクセス構造である． ここで，アクセス構造が暗号文に埋め込まれる方式が Ciphertext-Policy ABE (CP-ABE) であり，アクセス構造が復号鍵に埋め込まれる方式が Key-Policy ABE (KP-ABE)である．
    なお，アクセス構造とは与えられた属性に対して，アクセスを受理するか拒否するかを判断する データ構造である．
  • IPE (Inner-Product Encryption)
    $ek$ または $dk$ に対応するパラメータは，それぞれ体 $\mathbb{F}_q$ 上のベクトル $x \in {\mathbb{F}_q}^n$，$v \in {\mathbb{F}_q}^n$ である． 関係 $R(x, v)$ は， $x・v = 0$ ($x$ と $v$ の内積が 0) のときのみ成立つものである． ここで， $x$ および $v$ は属性や条件を表す論理式に対応させる．
• 関数型暗号のタイプ
  
  • Ciphertext-Policy
    予め適切な属性（住所，氏名，職業，資格等）の鍵を配布する． 様々の鍵に対し，その任意の部分集合でしか復号できない暗号文を生成する．相手を特定する必要は無い． 適切な鍵を持つ者だけが復号できる（アクセス構造が暗号文に，属性は復号鍵に埋め込まれる方式）．
  • Key-Policy
    適当な属性（ID）を使って暗号化する．通信相手を決める必要は無い． 様々な公開鍵で暗号化されてるデータに対し，その任意の部分集合を復号できる鍵を後から生成して配布する． 鍵として与えられた権利範囲の暗号文が復号できる（アクセス構造が復号鍵に，属性は暗号文に埋め込まれる方式）

方式概要

関数型暗号は，$\mathrm{Setup}$，$\mathrm{KeyGen}$，$\mathrm{Encrypt}$，$\mathrm{Decrypt}$ の 4 つのアルゴリズムから構成される．

• $\mathrm{Setup}$
  セキュリティパラメータ $λ$ と属性空間 $U$ を入力として，公開パラメータ $pp$ とマスタ秘密鍵 $msk$ を生成するランダム化されたアルゴリズムである．

  $(λ, U) \rightarrow (pp, msk)$

• $\mathrm{KeyGen}$
  
  • Ciphertext-Policy
    属性集合 $A$，マスタ秘密鍵 $msk$ および公開パラメータ $pp$ を入力として，復号鍵 $sk$ を生成するランダム化されたアルゴリズムである．

    $(A, pp, msk) \rightarrow sk$

  • Key-Policy
    アクセス構造 $S$，マスタ秘密鍵 $msk$ および公開パラメータ $pp$ を入力として，復号鍵 $sk$ を生成するランダム化されたアルゴリズムである．

    $(S, pp, msk) \rightarrow sk$

• $\mathrm{Encrypt}$
  
  • Ciphertext-Policy
    メッセージ $m$，公開パラメータ $pp$ およびアクセス構造 $S$ を入力として，暗号文 $ct$ を生成するランダム化されたアルゴリズムである．

    $(m, S, pp) \rightarrow ct$

  • Key-Policy
    メッセージ $m$，公開パラメータ $pp$ および属性集合 $A$ を入力として，暗号文 $ct$ を生成するランダム化されたアルゴリズムである．

    $(m, A, pp) \rightarrow ct$

• $\mathrm{Decrypt}$
  暗号文 $ct$，復号鍵 $sk$ および公開パラメータ $pp$ を入力として，暗号文を復号しメッセージ $m$ を生成する． ここで，復号できるためには属性集合 $A$ がアクセス構造 $S$ を満足している必要がある(これらの情報は，暗号文と復号鍵に埋め込まれている)．

  $(ct, sk, pp) \rightarrow m$

アクセス構造と秘密分散

関数型暗号には，次の考え方が使われている．

• アクセス構造
  与えられた属性に対して，アクセスを受理するか拒否するかを判断するデータ構造である．属性の集合 $P = \{P_1, \cdots ,P_n\}$ に対し，$P$ の空でない部分集合の集り $A$ である．$A$ に含まれる集合は有資格集合と呼ばれ，$A$ に含まれない集合は禁止集合と呼ばれる．
• 線形秘密分散法 (LSSS)
  アクセス構造 $Γ$ による秘密情報 $s$ の分散方法であり，属性の集合 $B$ に対して以下の関係が成り立つ．
  

  $B \in Γ$（有資格集合）ならば，$s$ を計算することができる．

  $B \in Γ$ でなければ，$s$ に関する情報を得ることができない．

  
  属性の集合 $P$ についての秘密分散法 $Π$ は，次の条件が満たされるとき $Z_p$ で線形と言う．
  • 各属性に対する分散情報は，$Z_p$ 上のベクトルを構成する．
  • 分散情報生成行列と呼ばれる $l$ 行 $n$ 列の行列 $A$ が存在する．
    すべての $i = 1, \ldots, l$ に対して，$A$ の $i$ 番目の行は，属性 $ρ(i)$ に対応付けられる ($ρ$ は {$i = 1,\ldots,l$} から $P$ への写像)．
    列ベクトル $v = (s, r_2,\ldots,r_n)$ を考える．ここで，$s \in Z_p$ は分散される秘密情報であり，$r_2,\ldots,r_n \in Z_p$ は乱数である． このとき，$A_v$ は秘密分散法 $Π$ に従った秘密情報 $s$ の $l$ 個の分散情報を示すベクトルとなる．分散情報 ($A_v)_i$ は属性 $ρ(i)$ に属する．
  
  $S$ を有資格集合，$I = \{i\ |\ ρ(i) \in S\}$ のように $I \subseteq \{1,\ldots,l\}$ を定義する． 秘密情報 $s$ の任意の分散情報 $\{λ\}_i$ に対して，$\sum_{i \subseteq I} ω_i λ_i= s$ となるような定数 $\{ω_i \in Z_p \}_{i \in I}$ が存在する． 禁止集合に対しては，このような集合 $ω_i$ は存在しない．
• アクセス木とブール式
  LSSS は，アクセス木を表すブール式に対応させることができる．アクセス木は，内部ノードが AND または OR ゲートなどの論理ゲートであり，葉ノードが属性に対応する木構造である．
  すなわち，条件を表すブール式をアクセス木に変換し，これを LSSS構造 (LSSS行列) に変換することができる．

／