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

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

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

暗号プロトコル概要

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

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

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

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

ビットコミットメント

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

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

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

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

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

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

紛失通信

紛失通信は「メッセージが相手に伝わったかどうか不明」である通信のことです。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$は排他的論理和です。

この手順で，なぜ先ほどの状況を作り出せるのかを説明します。要するに，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色彩色問題に関するゼロ知識対話証明の例をいかに挙げます。

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

秘密分散

秘密分散とは「少し秘密を無くしても復元できる」「少しの情報だけでは秘密が分からない」というような情報保持の仕方です。数式的に書くと，ディーラーが$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)$上の適当な点を分配すればいいのです。

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

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

カードベースプロトコル

カードベースプロトコルに関してはこちらの資料[カード組を用いた秘密計算]が非常に分かりやすいです。カードベースプロトコルは，物理的なカード組を使って秘密計算を行うものです。秘密計算とは，$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$のコミットメントと呼びます。以下のようにして，気まずくない告白（論理積）を行うことができます。