アカデミック

【初学者向け】マルチメディア通信<暗号プロトコル編>

この記事では,マルチメディア通信に関わる知識を簡単にまとめていきたいと思います。ただし,全ての知識が詳しく網羅されている訳ではありません。また,分かりやすいように多少意訳した部分もあります。ですので,参考程度におさめていただければ幸いです。

間違えている箇所がございましたらご指摘ください。随時更新予定です。他のマルチメディア通信に関する記事はコチラのページをご覧ください。

暗号プロトコル概要

こちらの記事[マルチメディア通信<暗号編>]でお伝えした暗号化技術は,プロトコルとして応用されています。暗号プロトコルとは,以下のように説明できます。

秘匿性(各マシンの入力や出力の一部が秘密の情報を含む場合にそれらの秘密に関するいかなる情報も攻撃者に漏えいしないこと)や頑健性(攻撃者が各プレイヤの計算を誤った結果に導くことができないこと)などの安全性がディジタル署名,秘密分散,公開鍵暗号,ゼロ知識証明等の暗号技術を用いて実現されているプロトコルの総称である。

http://www.ieice-hbkb.org/files/01/01gun_03hen_09.pdfより

つまり,暗号化技術をどのように応用すれば,うまいこと「安心・安全」な通信が行われるかを定めたルールのことを暗号プロトコルと呼びます。それでは,以下では早速様々な暗号プロトコルについて見ていきましょう。なお,こちらのサイト[外部リンク:シニアエンジニアの庵]が非常に分かりやすく,参考にさせてもらいました。

ビットコミットメント

ビットコミットメントは,遠隔地でコイン投げゲームを行うことを実現させるためのプロトコルです。何を言っているのかよく分からないと思いますので,AliceがBobとメールでコイン投げゲームを行うことを考えてみます。

ルールは,お互い0か1を選び,その排他的論理和を取って0であればAliceの勝ち,1であればBobの勝ちというものです。つまり,二人が選んだ数が同じであればAliceの勝ち,異なればBobの勝ちとするゲームです。

このゲームを遠隔地で行うことを考えましょう。単純に自分に選んだ数を紙に書いて相手に送ってしまえば,相手は自分が勝つように数字を選べてしまうため,何かしらの方法で「同時に数字を送り合う」というような状況を作り出さなければなりません。しかし,遠隔地でやり取りをしているため,同時に何かしらの操作を行うのは不可能です。つまり,このゲームでは以下のような不正を防ぐ必要があります。

●途中で手を変える
最初にAliceからBobに手を送ると考えるとAliceはBobに手を送ってから自分の手を変えられてはいけません(拘束性)
●相手の手が分かる
最初にAliceからBobに手を送ると考えるとBobはAliceの送った手が分かってはいけません(秘匿性)

そこで,「自分しか開けられない鍵」を使って自分の選んだ数が書かれた紙に鍵のかかった封筒に入れることで,お互いが自分の手を公平に知らせることができます。さらに,排他的論理和では,途中で手を変えたところで,相手の手を知らなければ勝ち負けはランダムになります。そのため,上の2つの不正は「自分しか開けられない鍵」を使って防ぐことができます。

ただし,お互いがルールに従っていればの話です。つまり,ビットコミットメントはお互いがルールに従っているという仮定のもとで成り立つものです。

拘束性・秘匿性ともに確率1で成り立つようなビットコミットメントは存在しないことが知られています。また,一方向関数を利用すれば他方を満たしつつ,もう片方が無視できる程度に小さな誤りを許す程度のビットコミットメントは構成可能であることも知られています。

具体的には,以下の性質をもつ関数$f$を設計します。ただし,$b$は0か1の整数,$r$は乱数とします。

●$f(b,r)=f(b’,r’)$となる$b'(\neq b)$を探すのは困難(対拘束性)
●$y=f(b,r)$から$b$を求めるのが困難(対秘匿性)

このような関数$f$を鍵としてりようすることで,以下のようなビットコミットメントを構成することができます。$b$はAliceの手,$c$はBobの手です。

1.Aliceはランダムに選んだ$b$と乱数$r$から$y=f(b,r)$を計算してBobに送る
2.Bobはランダムに選んだ$c$をAliceに送る
3.Aliceは$b\oplus c$を計算して自分の結果を知る
4.AliceはBobに$b$と$r$を送る
5.Bobは$y=f(b,r)$を計算して先ほどAliceから受け取った$y$と一致するか検証する
6.検証が正しい場合Bobも$b\oplus c$を計算して自分の結果を知る

ビットコミットメントは電子入札や電子投票などに応用されるプロトコルです。

「公開鍵暗号化方式を用いればビットコミットメントは実現可能」は自明としてOKです。「特に一方向関数が存在すればビットコミットメントが実現する」に関しては[1]に記述があります。

紛失通信

紛失通信は「メッセージが相手に伝わったかどうか不明」である通信のことです。2つのデータの送受信を考えるときに,受信者は$\frac{1}{2}$でメッセージを正しく受信できますが,実際に伝わったかどうかを$A$は知ることができません。少し異なる設定をすれば,受信者は欲しいデータを指定することもできますが,もう片方のデータを知ることはできません。

どのような場面で応用されるかというと,プライバシーを守りたいような通信です。例えば,Xさんが好きな楽曲をデータベースから取り出したいとき,Xさんは何を選んだかをデータベース側に知られたくないとします。このようなときに,「Xさん↔︎データベース」間で紛失通信が行われます。何を言っているのか分からないと思いますので,実際に例を示すことで理解していきましょう。

Alice(送信側)とBob(受信側)の通信を考えます。Aliceは$M_0$と$M_1$のデータを持っており,Bobは$M_1$のデータを欲しいとします。しかし,Bobは$M_1$のデータが欲しいとAliceに知られたくないとします。以下の手順に従えば「Aliceから$M_1$のみがBobに渡り」「AliceはBobが何を選んだか知ることができず」「Bobは$M_0$の内容を知られない」状況を作り出すことができます。ただし,$\oplus$は排他的論理和です。

1.まずお互いに暗号化関数$\rm{ENC}$を決める
2.Aliceは復号関数$\rm{DEC}$を決める
3.AliceはBobに適当に作った$m_0$と$m_1$を送る
4.Bobはランダムに$r$を選ぶ
5.Bobは送られた2つのメッセージからランダムに$m_k$を選ぶ
6.BobはAliceに$q=\rm{ENC}(m_k)\oplus m_r$を送る
7.Alice$l_0=\rm{DEC}(q \oplus m_0)$と$l_1=\rm{DEC}(q \oplus m_1)$を計算する
8.AliceはBobに$l’_0 = M_0\oplus l_0$と$l’_1 = M_1\oplus l_1$を送る
9.Bobは$l’_r \oplus m_k$を計算する

この手順で,なぜ先ほどの状況を作り出せるのかを説明します。要するに,Bobが最後に$l’_r \oplus m_k$を計算して$M_r$が得られること,加えて$\overline{l’_r} \oplus m_0$を計算しても$\overline{l’_r} \oplus m_1$を計算しても$\overline{M_r}$が得られないことを示せばOKです($\overline{l’_r}$は$l_r$ではない方の$l$,$\overline{M_r}$は$M_r$ではない方のデータ)。

\begin{align}
l’_r \oplus m_k
&= (M_r\oplus l_r) \oplus m_k\\
&= \{ M_r\oplus (\rm{DEC}(q \oplus m_r)) \} \oplus m_k\\
&= \{ M_r\oplus \{ \rm{DEC}(\rm{ENC}(m_k)\oplus m_r \oplus m_r) \} \} \oplus m_k\\
&= \{ M_r\oplus \{ \rm{DEC}(\rm{ENC}(m_k)\oplus 0) \} \} \oplus m_k\\
&= \{ M_r\oplus \{ \rm{DEC}(\rm{ENC}(m_k)) \} \} \oplus m_k\\
&= ( M_r\oplus m_k ) \oplus m_k\\
&= M_r\oplus 0\\
&= M_r
\end{align}

これでBobが$M_r$を得られることが分かりました。rはランダムですので,データを得られるか得られないかは平等です。加えて,AliceはBobがデータを正しく受信できたかどうか分かりませんし,どちらを選んだかも分かりません。続いて,Bobが$\overline{M_r}$を得られないことを示します。

\begin{align}
\overline{l’_r} \oplus m_k
&= (\overline{M_r}\oplus \overline{l_r}) \oplus m_k\\
&= \{ \overline{M_r}\oplus (\rm{DEC}(\overline{q} \oplus \overline{m_r})) \} \oplus m_k\\
&= \{ \overline{M_r}\oplus \{ \rm{DEC}(\rm{ENC}(m_k)\oplus \overline{m_r} \oplus m_r) \} \} \oplus m_k\\
\end{align}

ここで,$\overline{m_r} \oplus m_r$はお互い違う要素をもつ配列同士の排他的論理和であるため,結果は何も意味を持ちません。ですので,Bobが復号した片方のデータは何も意味を持たないということです。

ゼロ知識対話証明

対話証明プロトコルとは,検証者が証明者による証明に納得するまでやり取りが行われる計算モデルのことを指します。また,ゼロ知識証明とはある命題が正しいことを「余計な知識を漏らさずに」納得させる方法です。つまり,ゼロ知識対話証明というのは,証明者が検証者に対して「余計な情報を与えずに」ある命題を真と証明する計算モデルのことを指します。

より詳しくいうと,命題Lに対して「完全性」「健全性」を備えた場合「証明者と検証者は命題Lの対話証明系である」と定義します。完全性とは「正しい例を示す証明者と対話した場合,検証者は非常に高い確率で納得する」性質です。逆に言えば,納得するためには証拠が必要であるという性質です。

一方,健全性とは「正しくない例を示す任意の証明者と対話した場合,非常に高い確率で納得しない」という性質です。逆に言えば,証明者はズルして命題を「真」とでっち上げることができないということです。

また,「正しい証明者に対して検証者がどのように振舞っても,証明の正しさ以外の情報は一切わからない」性質がゼロ知識性です。まさに,余計な情報を漏らさずに,という日本語と対応しています。

ゼロ知識証明は対話証明の部分集合でもあります。

こちらのサイト[外部リンク:Understanding Zero-knowledge proofs through illustrated examples]が秀逸な例を示しています。Aliceが証明者,Bobが検証者としてウォーリーを探し出せたことを証明する対話証明系を考えます。証明方法は「Aliceがウォーリーだけを切り取る」ことでOKです。というのも,Bobが切り取られたウォーリーを見れば「Aliceがウォーリーを探し出せた」ことを必ず納得できます。一方,Aliceはウォーリーを見つけなければウォーリーのみを切り取ることは不可能です(ランダムに切り出したとしてそれがウォーリーの姿形に完全一致する確率は非常に低いです)。これらより,Aliceの証明方法は「完全性」「健全性」の2つを兼ね備えており,対話証明系と呼ぶことができます。

ゼロ知識証明の例も,先ほどのサイトに取り上げられていました。色盲のAliceが検証者,色を識別できるBobが証明者とします。目標は,Bobが色に関する情報を伝えないように,自分が「色を区別できる」ことをAliceに伝えることです。証明方法は,Aliceに青と赤のボールを2つもたせ,Bobの見えないところでボールを「入れ替える」もしくは「そのまま」にします。Bobは色が区別できればボールが入れ替わったかどうか判定することができます。

一方,色が見えなければ$\frac{1}{2}$の確率でしか当てることはできません。試行回数を十分に大きくして,Bobが毎回必ずボールが入れ替わっているかを当てることができれば,AliceはBobが色を識別できると納得することができます。このように,ゼロ知識証明はあくまでも統計的な根拠に基づく証明方法です。

ゼロ知識対話証明は「証明プロトコル」の一種です。実際にはゼロ知識証明はハッシュ関数などを利用して「非対話系」として扱われることが多いです。対話系だと平文でパスワード等を流してしまうことになります。

例えば「パスワードを知っている」ことを証明して入力を省略するときや,ブロックチェーンで「自分の過去に行ったトランザクションをバラさずに」二重払いしていないことを示すときに利用されるプロトコルです。

ゼロ知識対話証明系の具体例としては,地図の3彩色問題が有名です。例えば,証明者Pは検証者Vに対して3色に塗り分けられた地図を見せることを考えます。実際に3色で塗り分けられていれば検証者は納得し,塗り分けられていなければ納得しません。これが対話証明系です。

次に,塗り分けられた地図を見せることなく「地図が塗り分けられること(完全性)」「塗り分けられる地図が存在すること(健全性)」を証明するのがゼロ知識証明です。地図の3色彩色問題に関するゼロ知識対話証明の例をいかに挙げます。

0.塗り分けに使う3色A,B,Cと検証に使う3色A’,B’,C’を選ぶ

<以下を検証者Vが納得するまで繰り返す>
1.証明者Pは地図を塗り分ける
2.3色A,B,Cをそれぞれランダムに他の3色A’,B’,C’に対応させる
3.A’,B’,C’の色のカードを作る
4.塗り分けられた地図の領域の上に箱を置く
5.地図の色に対応する色のカードを箱の中に入れる
6.箱の隣接関係を崩さないまま色が塗られていない地図にすり替える
7.証明者Pは検証者Vに地図と上に置かれた箱を見せる
8.検証者Vは適当に2つの隣接した領域の箱を指定する
9.証明者Pは箱の中身を見せる

以上を繰り返せば,証明者Pが毎回塗り分ける色と検証者Vが塗り分ける色が異なるため,検証者Vは地図の塗り分け方に関する情報は一切手に入らないことが分かります。また,何回も繰り返すことで証明者Pは隣接する任意の領域は二色で分けられることを示すことができ,結局地図を3色で塗り分けられることを示せました。つまり,上の例はゼロ知識証明です。

隣接した領域の箱に入っているカードが異なる色であれば検証者は必ず納得します。また,隣接した領域に入っているカードが同じ色であれば,必ず検証者は納得しません。したがって,上の例は対話証明系であることが分かります。

ちなみに対話証明系は「NP」を拡張したものともみなせます。NPはYesの証拠が与えられた場合には多項式時間で解けるような問題です。また,Pは多項式時間で解ける問題です。PはNPの部分集合であることは示されていますが,P=NPであるかどうかは分かりません。これはつまり,以下のような主張をしています。

「与えられた答が正しい答であるかどうかの検証は簡単だが、
自分で答を見つけるのは難しい問題は存在する。」

21世紀の7大未解決問題の1つです。例えば2彩色問題はPかつNPです。3彩色問題はNPではあるもののPであるかは未解決です。

NPの場合は,証明者→検証者の対話は1回きりになります。また,検証者は決定的な値を使って検証を行います。対話証明系は,これを拡張して証明者→検証者の対話を複数回行い,検証者は乱数を利用することで統計的に検証を行います。

対話証明系を持つクラスとしては「IP」などが挙げられます。グラフ同型問題は,ノードの対応関係の組み合わせを考えることで判定できるためNPです。NPはIPに含まれるため,グラフ同型問題は同時にIPでもあります。

秘密分散

秘密分散とは「少し秘密を無くしても復元できる」「少しの情報だけでは秘密が分からない」というような情報保持の仕方です。数式的に書くと,ディーラーが$n$人のプレイヤー$P_1,P_2,\cdots,P_n$に対してシェアと呼ばれる値$s_1,s_2,\cdots,s_n$を分配するプロトコルです。$(k,n)$しきい値法は,$k$人のプレイヤーが集まれば秘密を復元でき,$k-1$人のプレイヤーでは秘密が分からないような分配方法・復元方法のことを指します。

$(k,n)$しきい値法に関しては,高校数学の美しい物語さんが非常に分かりやすいです。Shamirの秘密分散法では,「$k$点を通る$k-1$次多項式は1つに定まる」という定理からラグランジュの補完公式を利用します。簡単には,定数項($y$軸との交点のイメージ)を秘密情報$s$にしておいて,$k-1$次多項式$f(x)$を適当に作ればOKです。あとは,$f(x)$上の適当な点を分配すればいいのです。

ここでは,ディーラーが「正しく」秘密情報を分配するという仮定のもと説明をしました。実際には,そのような仮定が絶対正しいとはいえないため,ディーラーの分配が正しいかどうかの検証をするような秘密分散を行います。これを「Verifiable Secret Sharing(VSS)」と呼びます。VSSは暗号化された秘密分散をディーラーが分配し,ディーラーが証明者となるゼロ知識証明を利用します。

マルチパーティープロトコル

マルチパーティープロトコルとは,プレイヤーがもつ秘密情報をお互いに知られないようにして,秘密情報から得られる情報を計算する方法です。簡単な例として,全員の秘密情報の和を求める以下の方法が挙げられます。

1.各プレイヤーは他のプレイヤー全員に自分の秘密情報を分配する
2.各プレイヤーは他のプレイヤー全員から受け取った値を足す
3.全員の値を合計したものが全員の秘密情報の和になっている

信頼できるセンターを利用するという方法もあります。

カードベースプロトコル

カードベースプロトコルに関してはこちらの資料[カード組を用いた秘密計算]が非常に分かりやすいです。カードベースプロトコルは,物理的なカード組を使って秘密計算を行うものです。秘密計算とは,$n$人のプレイヤー$P_1, P_2, \cdots, P_n$が秘密の入力$x_1,x_2,\cdots,x_n$を持っているときに,関数の結果$f(x_1,x_2,\cdots,x_n)$のみを全員が共有することです。

秘密計算の有名な例として「気まずくならない告白」があります。$n=2$と設定し,AliceとBobが付き合うかどうかを決めるという状況を考えます。AliceとBobはそれぞれ秘密の値$\{0,1\}$を決めます。$0$はNo,$1$はYesを示します。このとき,秘密計算の目的関数を$a\wedge b$とすれば,お互いの気持ちを知らせずに結果のみを知ることができます。

この告白シチュエーションにおける秘密計算を,カードベースプロトコルによって実現する方法を見てみましょう。「Five-Card Trick」と呼ばれています。ここでは,都合上二枚のカードをAとBとします。AとBのカードの裏にはXが書かれており,裏にした状態では区別がつかないものとします。Five-Card Trickでは2枚のAと3枚のBを利用します。

まず,YesかNoを表す$\{0,1\}$として,以下のような組み合わせによって符号化を行います。このルールを$\alpha$と名付けます。

AB→0
BA→1

ルール$\alpha$の下で,$x\in \{0,1 \}$を表す裏返しのカードXXを$x$のコミットメントと呼びます。以下のようにして,気まずくない告白(論理積)を行うことができます。

1.Bの左側にAliceは$a$の否定$\overline{a}$のコミットメント,右側にBobは$b$のコミットメントを並べる
2.Bを裏返す
3.ランダムカット(5枚を円にしてグルグル回して順番を変化させる操作)を行う
4.Bが連続して3枚並ぶ場合,$a\wedge b=1$を表す
5.Bが連続して3枚並ばない場合,$a\wedge b=0$を表す

カードベースプロトコルの研究はこの「 Five-Card Trick」を発端として始まりました。

入力のコミットメントに対して出力もコミットメントとなるようなプロトコル(コミット型プロトコル)も考案されています。8枚のカードに対してランダムカットが平均で2回必要というような方法があります[Stiglic, 2001]。また,2009年にはランダムカットの代わりに「ランダム二分割カット」というシャッフル方法が考案され,効率的なANDプロトコル/XORプロトコルが考案されました。

秘密投票を応用するアプリケーションとして投票が挙げられます。投票を実現するために必要な加算器や半加算器もカードベースプロトコルによって実現可能です。

参考文献

[1] Goldreich, Oded. Foundations of cryptography: volume 2, basic applications. Cambridge university press, 2009.

COMMENT

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です