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

お知らせ
Table of Content

はじめに

この記事では、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と等しくなりますが、ADでは要素23が共通しているからです。

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つの条件があります。

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

記号の定義

Exact Cover Problemのインスタンスは、nT_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 mapse_{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}_ni \in [l]に対するパズルピースC_i=(g_{|T_i|})^{\prod_{j \in n}a_j}から構成される暗号文を作成して復号者に送ります。
もし復号者が、[n]の分割である\{T_i:i\in I\}に対するWitnessI=\{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 Ga,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_Ta,b,c\in \{0,...,q-1\}に対しアリスがA=g^aを、ボブがB=g^bを、チャーリーが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 Zg_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_ig_{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に属する任意の問題はこのスキームを用いて暗号鍵に変換することができると言えます。
興味を持たれた方は、ぜひ論文を読んでみて下さい。

参考サイト

https://eprint.iacr.org/2013/258.pdf

Knuth's Algorithm XとDancing Linksの解説 - TopCoderとJ言語と時々F#
Exact Cover Problem 今回解説するKnuth's Algorithm Xは、Exact Cover Problemという問題を解くためのアルゴリズムです。Exact Cover Problemについてはうまい日本語訳が分からない(「敷き詰め問題」とか?)ので英語のまま書いています。数学で言うと、ある集...

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

https://www.cryptrec.go.jp/exreport/cryptrec-ex-2603-2016.pdf

[Jou04] http://cgi.di.uoa.gr/~aggelos/crypto/page4/assets/joux-tripartite.pdf

[GGH13a] https://eprint.iacr.org/2012/610.pdf

タイトルとURLをコピーしました