数学上の難問を利用して暗号を作るWitness Encryptionとは？

Table of Contents

はじめに

この記事では、Witness Encryptionとよばれる暗号方式を紹介します。
計算複雑性理論的に解くことが難しいとされているNP問題に属する問題と答えの組は、平文を暗号化するための暗号鍵と復号鍵として扱えるという話です。ざっくり言えば、「与えられた鍵を正しく組み合わせると復号のための鍵になるが、正しい組み合わせ方を見つけるのがNP完全であるような問題」を考えます。
まず、Exact Cover Problemを説明し、Witness Encryptionの基礎になっているExact Cover Problemを用いたスキームを説明します。その後記号の定義、Witness Encryptionの概要、Multilinear mapsの詳細について述べます。

Exact Cover Problem

まず、Exact Cover Problemの説明をします。
ある集合 $X$ の部分集合の集合 $S$ が与えられて、その $S$ の部分集合であるような $S^*$ において、 $X$ に含まれる要素全てが $S^*$ の中にひとつだけ含まれるとき、 $S^*$ はExact Coverであると言います。
たとえば、集合 $X=\{1, 2, 3, 4\}$ だとします。そして集合 $S=\{A, B, C,D\}$ として、 $A,B,C,D$ は以下のようであるとします。
$A=\{1,2,3\}$
$B=\{1,4\}$
$C=\{2,3\}$
$D=\{2,3,4\}$
このとき、 $S^*=\{B,C\}$ はExact Coverです。なぜなら集合 $B,C$ は共通要素を持たず、これらの和集合は $\{1, 2, 3, 4\}$ であり $X$ と等しいからです。

しかし、 $S^*=\{A,D\}$ はExact Coverではありません。なぜなら、これらの和集合は $\{1, 2, 3, 4\}$ になり $X$ と等しくなりますが、 $A$ と $D$ では要素 $2$ と $3$ が共通しているからです。

Exact Cover Problemを用いたスキーム

今回は、NP完全問題である3-Exact Cover problemを扱います。
3-Exact Cover problemとは $[n]$ の部分集合で、要素数が3である部分集合 $T_1,...,T_l$ に対して、Exact Coverである $T_{i_1},...,T_{i_t}$ を見つける問題です。
これは、 $[n]$ の $\begin{pmatrix}n \\3\\\end{pmatrix}$ 通りの部分集合である $T$ と別のパーティー $P_T$ を対応させる秘密分散スキームに対応しています。
この秘密分散スキームでは、それぞれのパーティー $P_T$ の秘密シェア $\lambda_T$ から秘密 $x$ を構成します。
この秘密分散スキームには2つの条件があります。

efficient recovery
$P_{{T_i}_1},...,P_{{T_i}_t}$ の集合がexact coverを知っていたら、これらのパーティーはそれぞれの秘密シェア $\lambda_{{T_i}_1},...,\lambda_{{T_i}_t}$ から秘密 $x$ を効率的に回復できる。
privacy
$P_{{T_i}_1},...,P_{{T_i}_t}$ がexact coverを含んでいなければ、秘密 $x$ と $x'$ の区別ができない。

記号の定義

Exact Cover Problemのインスタンスは、 $n$ と $T_1,...,T_l\subset[n]$ から成り立ちます。
$[n]$ の分割である $\{T_i:i\in I\}$ のもと、Witnessは集合 $I\subseteq[l]$ です。

$n$ -多線形性族は、位数 $p$ ,
生成元 $g_1,...,g_n$ の群 $\mathbb G_1,...,\mathbb G_n$ と
$i + j \leq n$ に対して $e_{i,j}(g^a_i,g^b_j)=g^{ab}_{i+j}$ を満たすようなMultilinear maps $e_{i,j}:\mathbb G_i\times \mathbb G_j \rightarrow \mathbb G_{i,j}$ から構成されます。
Multilinear mapsは以下のように書き換えられます。
$i_1+...+i_t \leq n$ に対して、
$e( g_{i_1}^{a_1},..., g_{i_t}^{a_t})=(g_{i_1+...+i_t})^{a_1+...+a_t}$
を満たすような
$e:\mathbb G_{i_1}\times...\times\mathbb G_{i_t}→\mathbb G_{i_1+...+i_t}$

Witness Encryptionの概要

ユーザは、メッセージ $M$ を特定の問題インスタンス $x$ に暗号化して、暗号文を生成することができます。
暗号文の受信者は、 $x$ が言語にあり、受信者が解wを知っていて、 $R(x,w)$ が成立する場合、メッセージを復号することができます。
もし $x$ が言語 $L$ になければ、同じ長さのメッセージを受信者は区別できません。
また、受信者は、 $x$ が実際に言語 $L$ に含まれているかどうかわからないかもしれません。

Witness Encryptionの詳細

もしも $I$ がWitnessならばパズルピースとも言える $\{T_i:i\in I\}$ はパズル $[n]$ の答えに対応しています。
Witnessは複数いることが想定されるので、パズルを解けるピースは複数あるといえます。
Witness Encryptionではmultilinear(多重線形性) mapsを用いて、パズルピースの乗算をできるようにします。
Exact Coverインスタンス $(n,T_1,...,T_l)$ と $n$ -多線形性族に対して、Witness Encryptionを以下のように定義します。
$M\in \mathbb G_n$ を暗号化するのに、ランダムにスカラー $a_1,...,a_n\in \mathbb Z_p$ を生成し、 $C=M\cdot g^{a_1\cdot \cdot \cdot a_n}_n$ と $i \in [l]$ に対するパズルピース $C_i=(g_{|T_i|})^{\prod_{j \in n}a_j}$ から構成される暗号文を作成して復号者に送ります。
もし復号者が、 $[n]$ の分割である $\{T_i:i\in I\}$ に対するWitness $I=\{i_1,...,i_t\}\subseteq [l]$ を知っていれば多重線形性写像を用いて復号できます。特に $M$ を復号するために、 $g^{a_1\cdot \cdot \cdot a_n}_n=e(C_{i_1},...,C_{i_t})$ を計算し、 $C$ からこの値を分割します。
直観的には、 $g^{a_1\cdot \cdot \cdot a_n}_n$ を作ることが、 $[n]$ のExact Coverを見つけることです。
このアルゴリズムは、“Decision Multilinear No-Exact-Cover Problem”の困難性に基づいて安全性を保証します。
これは、直観的には、解のないExact Coverのインスタンス $x$ が与えられた場合、 $r$ がランダムかつ他の変数に対して独立だとしたとき $(C_1,...,C_l,g^{a_1\cdot \cdot \cdot a_n}_n)$ 分布と $(C_1,...,C_l,g^r_n)$ 分布を区別するのは困難であるというものです。

Multilinear mapsの詳細

Diffie-HellmanからMultitilinear mapsへ

Diffie-Hellmanの鍵交換方式では、
生成元 $g$ 、位数 $q$ の巡回群 $\mathbb G$ で $a,b\in \{0,...,q-1\}$ に対し、
アリスが $A=g^a$ を、ボブが $B=g^b$ を送り合い、互いに $g^{ab}=A^b=B^a$ を計算する。

[Jou04]では、1ラウンドで3人の鍵交換をするために以下のスキームが考案された。
生成元 $g$ 、位数 $q$ の巡回群 $\mathbb G$ 、非退化な二重線形写像 $e:\mathbb G \times \mathbb G→\mathbb G_T$ 、 $a,b,c\in \{0,...,q-1\}$ に対しアリスが $A=g^a$ を、ボブが $B=g^ｂ$ を、チャーリーが $C=g^c$ を送り合い、 $e(g,g)^{abc}=e(A,B)^C=e(B,C)^a=e(C,A)^b$ を算出する。

Multilinear mapsの定義

あらゆる $a_1,...,a_n\in \mathbb Z$ と $g_1,...,g_n\in \mathbb G$ に対して、 $e( g_{i_1}^{a_1},..., g_{i_n}^{a_n})=e(g_{i_1+...+i_n})^{a_1...a_n}$ が成り立ち、かつ、 $\mathbb G$ の生成元 $g$ に対して $e(g_{g,...,g})$ が $\mathbb G_T$ の生成元のうえで、 $e$ が非退化であるとき、
巡回群 $\mathbb G$ と素位数 $q$ の $\mathbb G_T$ に対するmap(写像) $e:\mathbb G^n→\mathbb G_T$ はn-linear mapまたはnを省略して Multilinear mapといいます。

非退化の定義

対称双一次形式 $\beta: V \times V→\mathbb R$ が非退化であるとは、次の条件が成り立つときをいう。
$\forall v\in V[(任意のw\in Vに対し\beta (v,w)=0)ならばv=0]$

双一次形式の定義

$V,W$ を体 $\mathbb K$ 上のベクトル空間とする。 $\beta: V \times W→\mathbb K,(v,w)\mapsto\beta(v,w)$ が $V\times W$ 上の双一次形式(双線型形式)(a bilinear form)とは片側の変数を固定した時、線形である時をいう。
すなわち $v,v'\in V,w,w'\in W,k \in \mathbb K$ に対して
・ $\beta(v+v',w)=\beta(v,w)+\beta(v',w),\beta(kv,w)=k\beta(v,w)$
・ $\beta(v,w+w')=\beta(v,w)+\beta(v,w'),\beta(v,kw)=k\beta(v,w)$ ・ $\beta(v,w+w')=\beta(v,w)+\beta(v,w'),\beta(v,kw)=k\beta(v,w)$
さらに $\beta(v,w)=\beta(w,v)$ が成り立つ時、 $V$ 上の対称双一次形式という。

出典: http://www.rimath.saitama-u.ac.jp/lab.jp/Fukui/lectures/Linear_algebra.pdf

今回のスキーム

暗号文の加算と乗算を任意の回数行える完全準同型暗号(FHE)の暗号文と、Multilinear mapsの群要素の指数とが似ているという直感から以下の[GGH13a]スキームは生まれました。
素位数 $q$ の巡回群 $\mathbb G_i$ の生成元 $g_i$ が $g_{i+j}=e(g_i,g_j)$ を満たす時、加法 $g_i^a \cdot g_i^b=g_i^{a+b}\in \mathbb G_i$ かつ乗法 $i+j \leq n$ に対して $e(g_i^a,g_j^b)=g_{i+j}^{a\cdot b}\in \mathbb G_{i+j}$ が成り立ちます。
この写像は以下のように書き換えられます。
$i_1+...+i_t \leq n$ に対して、
$e( g_{i_1}^{a_1},..., g_{i_t}^{a_t})=(g_{i_1+...+i_t})^{a_1+...+a_t}$
を満たすような
$e:\mathbb G_{i_1}\times...\times\mathbb G_{i_t}→\mathbb G_{i_1+...+i_t}$
この写像こそが今回Witness Encryptionで扱ったMultilinear mapsです。

まとめ

Witness EncryptionはExact Cover ProblemとMultinlinear mapsを活用した暗号方式になっています。Exact Cover ProblemはNP完全問題なので、クラスNPに属する任意の問題はこのスキームを用いて暗号鍵に変換することができると言えます。
興味を持たれた方は、ぜひ論文を読んでみて下さい。