• ホーム
• 暗号技術
• プログラミング

暗号応用技術

暗号プロトコル

ビットコミットメント

• ビットコミットメントとは
  いま，Alice と Bob がネットワークを介して次のコイン投げゲームを行うことを考える． Alice と Bob はそれぞれ独立に1ビットの値を選び，その排他的論理和が1ならば Alice の勝ち，0ならば Bob の勝ちとする．ここで，公平性の観点からは Alice と Bob が対称であること，すなわち Alice の値と Bob の値が同時に開示されることが重要である．しかし，ネットワーク上で通信をしているような場合にはその同時性を確保することは困難であり，必然的に Alice と Bob の情報の開示に時間差が生じることになる．このような場合，その時間差を利用して先に情報を得た方がその情報をもとに自分の値を偽る不正（いわゆる「後出し」）ができないようなスキームを考える必要がある．
  実際のコイン投げでは，まず Alice が値を決め（コインを投げ），次に Bob が値を決め（表裏を選択し），最後に Alice が値を開示することになるが，ここで公平性の観点から重要なのは，Bob が表か裏かを決める際に Alice のコイン投げの結果がわからないこと（Bob の不正が不可能），Alice がコイン投げの結果を公開する際にいかさまができないこと（Alice の不正が不可能）の 2点である．
  
  実際のコイン投げでは，Alice と Bob が実際にそのコイン投げに立ち会うことによりいわば物理的にこの問題を解決しているが，暗号技術的にこの問題を解決する一つの方法がビットコミットメント $\mathrm{BC}(b, r)$（$b$ はコミットするビット，$r$ は乱数）である．
  ここで，ビットコミットメントとは，以下の 2 つの性質 P1，P2 をみたす関数

  $\mathrm{BC}: \{0,1\} \times \{0,1\}^k \rightarrow \{0,1\}^1$

  • P1: $\mathrm{BC}(b, r) = \mathrm{BC}(b',r')$ となるような $(b',r')$, $b \ne b'$ を求めるのが困難である．
  • P2: $X$ の値（$X = \mathrm{BC}(b, r)$）から，$b$ を求めるのが困難である．
  を用いたプロトコルである．
  ビットコミットメントは，以下の2つのフェーズからなる．
  1. コミットメント・フェーズ
     $A$ はランダムなビット $b \in \{0, 1\}$，乱数 $r$ を選び $X = \mathrm{BC}(b, r)$ を計算し，$X$ を $B$ に送る．なお，$\mathrm{BC}$ は多項式時間で計算できる関数である．
  2. 開示フェーズ
     $A$ は $(b, r)$ を $B$ に送る．
  上記において，性質P1 は Alice の不正が不可能であること（拘束性），P2 は Bob の不正が不可能であること（秘匿性）に対応している．
• コイン投げプロトコル
  この $\mathrm{BC}(b, r)$ を用いて，以下のようにコイン投げプロトコルを構成することができる．
  1. $A$ はランダムなビット $b \in \{0, 1\}$，乱数 $r$ を選び $X = \mathrm{BC}(b, r)$ を計算し，$X$ を $B$ に送る．
  2. $B$ はランダムなビット $c \in \{0, 1\}$ を選び $c$ を $A$ に送る．
  3. $A$ は $b \oplus c$ をコイン投げの結果とする．また，$A$ は $(b, r)$ を $B$ に送る．
  4. $B$ は $X = \mathrm{BC}(b, r)$ が成立するかどうかを検証する．成立するならば，$b \oplus c$ をコイン投げの結果とする (あらかじめ，値 $0$, $1$ がそれぞれどちらの勝ちかに対応するかを決めておく)．
• ビットコミットメントの構成
  ビットコミットメントは，一方向性関数があれば構成できることが示されている．その他の代表的な構成方法には，次のようなものがある．
  • $\mathrm{BC}(b, r) = g^b h^r \bmod p\quad (h = g^a)$
  • $\mathrm{BC}(b, r) = g^b\ ||\ r \bmod p$
  
  なお，上記のビットコミットメントは 1 ビットであるが，任意の $t$ ビットに拡張することができる．$t$ ビットの $x = (x_1, \ldots , x_t)\ (x_i \in \{0, 1\}, i = 1, \ldots , t)$ に対して，$\mathrm{BC}(x, r)$ を $(\mathrm{BC}(x_1, r_1), \ldots, \mathrm{BC}(x_t, r_t))$ の意味で用いれば良い．
  ビットコミットメントは，上記コイン投げプロトコルのほかにも電子入札や電子投票など多様な応用が考えられる暗号プロトコルである．

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

マルチパーティプロトコルとは，各参加者が持つ秘密情報を秘密に保持したまま，秘密情報から得られる値を参加者が協力して計算する方法である．

$n$ 人の参加者から構成されるネットワークにおいて，それぞれの参加者 $i$ が自分だけが知っている秘密情報 $x_i$ を保持しているとする．ある関数 $f$ が与えられたとき，各参加者は各自の持つ秘密情報を他人に明かさないまま $y = f(x_1, \ldots, x_n)$ を計算しようとする．このように，各参加者がネットワーク上で各自の持つ秘密情報を漏らさずに何らかの通信を行い，全員が $y$ の値を正しく得る機能を実現するプロトコルが，関数 $f$ に対するマルチパーティプロトコルである．

$n$ 人の参加者の中に不正を行う者が $t$ 人いるとしても，他人の秘密情報を盗むことも計算結果に擾乱を与えることもできないマルチパーティプロトコルは $t$‐安全であるという．

例として，複数の参加者が持つ秘密の情報の和を求めるプロトコルを考える． 以下の方法がある．

1. 信頼できるセンタを用いる方法
   信頼のおけるセンタが存在するならば，各参加者が持つ情報をセンタが集め和を計算し公開する．
2. 秘密分散共有法を用いる方法
   
   • 各参加者は自分の秘密値を全参加者に分割配布する．
   • 他の全ての参加者の分散情報を得た参加者はその和を計算する．
   • 全参加者は自分の求めた値を公開する．これらの値の和が求める値になる．

紛失通信

紛失通信 (Oblivious Transfer: OT)とは，通信相手に通信文が正しく伝達されたかどうかが不明な通信である． 送信者 $A$ が通信文 $m$ を受信者 $B$ に送るとき，1/2の確率で受信者 $B$ に伝わるが，伝わったかどうかを送信者 $A$ は知ることができない．

k-out-of-m 紛失通信とは，送信者 $A$ が持つ $m$ 個の情報のうち $k$ 個のみが受信者 $B$ に伝わるが，受信者 $B$ がどの情報を受け取ったかは送信者 $A$ は知ることができない通信である． このとき，受信者 $B$ は送られなかった情報が何であったかは知ることができない．

紛失通信は，暗号化・復号関数などを用いて実現することができる．1-out-of-2 OT プロトコルの例を示す．

• 1-out-of-2 OT
  $A$ がデータ $M_0$，$M_1$ を保有し，$B$ がビット $b$ を保有するとき，$B$ は $M_b$ を得ることはできるが，$\overline{M_b}$ を得ることはできず，かつ $A$ は $b$ を得ることはできないような特徴を持つプロトコルである．
  
  
  • $A$ 処理 1
    
    1. 暗号化・復号関数 $(\mathrm{Enc}, \mathrm{Dec})$ を選択する．
    2. ランダムにメッセージ $m_0$，$m_1$ を選択する．
    3. $\mathrm{Enc}$，$m_0$ および $m_1$ を $B$ に送る．
  • $B$ 処理 1
    
    1. ランダムに $r \in \{0, 1\}$ を選択する．
    2. ランダムにメッセージ $k$ を選択する．
    3. $A$ に $q = \mathrm{Enc}(k) \oplus m_r$ を送る．（$\oplus$ は XOR 演算）
  • $A$ 処理 2
    
    1. $k'[0] = \mathrm{Dec}(q \oplus m_0)$ を計算する．
    2. $k'[1] = \mathrm{Dec}(q \oplus m_1)$ を計算する．
    3. $(M_0 \oplus k'[0], M_1 \oplus k'[1])$ を $B$ に送る．
  • $B$ 処理 2
    $M_r \oplus k'[r] \oplus k$ より $M_r$ を取得する．

匿名通信路

一般に，ネットワーク(通信路)上を流れているメッセージを監視すると，そのメッセージが誰から送られてきたものかということは容易に知ることができる．例えば，インターネット上では，メッセージに送信者の IPアドレスが書いてあったり，IPアドレスは書いて無くても追跡できる場合がある． これに対して，匿名通信路は流れているメッセージを見ても送信者が全く特定できないようなネットワークである．

匿名通信路の応用例には，次のようなものがある．

• 電子投票
  インターネットなどの公衆回線を利用した電子投票では，投票された票から投票者が追跡できた場合，投票者のプライバシーが守られなくなる． 匿名通信路を導入すれば，送信者を特定できないという性質から投票者のプライバシーを守ることができる．
• 匿名投書
  ネットワーク越しに投書をする際に，投書者が判明すると後々不利益を被る場合がある． 匿名通信路を用いれば，誰が投書したかはわからなくすることができる．
• 電子商取引
  インターネット上などで取引をするとき，取引する双方が取引をしたという事実を隠したい場合がある． 匿名通信路を用いれば，どことどこのメーカが取引をしたかという事実を隠すことができる (匿名通信路は送信者を隠す仕組みであるが，真の受信者には送信者が誰であるかを明かすようにすれば，第三者だけに通信を秘匿することができる)．

• Mix-net
  匿名通信路を実現する方式に Mix-net がある．
  複数の送信者，複数の中継サーバ，および複数の受信者を仮定する． Mix-net では，以下に示す多重暗号を用いる．
  1. 送信元 $A$ から受信先 $B$ までの経路を決める．これを，$R_1, \ldots, R_n$とする．
  2. $A$ はメッセージ $m$ を $B$ の公開鍵 $P_B$ で暗号化し，さらに，$n$ 番目の中継サーバ $R_n$ の公開鍵 $P_n$ を用い，
     

     $X_n = \mathrm{E_{P_n}}(B\ ||\ \mathrm{E_{P_B}}(m))$

     と暗号化する．同様に，他の中継サーバに対しても

     $X_{n-1} = \mathrm{E_{P_{n-1}}}(R_n\ ||\ X_n)$

     を順次計算し，最終的に

     $X_1 = \mathrm{E_{P_1}}(R_2\ ||\ X2)$

     を得る．これを最初の中継サーバ $R_1$ に送る．
  3. 中継サーバ $R_1$ は，自分の秘密鍵で $X_1$ を復号し，次の中継サーバ $R_2$ とメッセージ $X_2$ を取り出し，中継サーバ $R_2$ へ $X_2$ を送る．
     他の中継サーバも同様の処理を繰返し，最終的な受信者 $B$ へ $\mathrm{E_{P_B}}(m)$ が届く．
  4. $B$ は，$\mathrm{E_{P_B}}(m)$ を復号し $m$ を得る．
  上記において，経路は送信者が動的に決めるので，各中継サーバは受信元の中継サーバと次の送信先の中継サーバしか分からないため，中継サーバの結託はできない． しかし，各中継サーバの前後の通信データを観察していれば，入力メッセージと出力メッセージの対応が分かり，これから送信者が追跡されてしまう．
  そのため，複数の送信者がいる場合，以下のようにメッセージをシャッフルすることが行われる．
  • 送信者が $l$ 人いるとき，各中継サーバは $l$ 個の暗号文を受信するまで待ち，メッセージの順番を置き換えてから，次の中継サーバに送るようにする．$n$ 台の中継サーバがそれぞれ独立にメッセージの置き換えを行う．
  このように，中継サーバが複数のメッセージをミックス(シャッフル)してかき混ぜることで，メッセージがどのように流れているかを隠すことができ，入力データと対応する出力データが関連付かないようになる． これらの中継サーバを直列に複数台接続すれば，そのすべてが結託するなどしない限り，送信者のプライバシーは保護される(一台でも正直な中継サーバがいれば送信者のプライバシーは保護できる)．
  
  Mix-net には満たすべき性質として次の3つがある．
  • 完全性
    Mix-net のすべての計算が正確に行われ，出力すべてが正しい結果である.
  • 通信路匿名性
    通信路を特定されず，送信者のプライバシーが守られる．
  • 頑健性
    Mix-net の中に不正なサーバ(データを改ざん，水増し，棄却などをするサーバ)がいたとしても， Mix-net から正しい出力を得られる． この性質が無ければ，不正者が Mix-net 内にいるとき，完全性と通信路匿名性も怪しくなる．
  
  この3つの性質の中でも頑健性の提供は Mix-net 構築でもっとも重要と言える．
  頑健性では Mix-net にある不正をどのように回避するかがポイントとなる． 頑健性を提供する方式には，次のようなものがある．
  • 不正サーバをすげ替える
    不正な処理を行うサーバを発見した場合，不正サーバを自動的にネットワークから切り離し，他のサーバと取り替える．この場合，不正が発覚した時点から，すべての処理をやり直す必要がある．
  • 不正サーバを無視する
    不正サーバを発見した時点で，そのサーバをネットワークから切り離し，他のサーバが協力して処理を続行する．
  
  頑健性を提供するには，不正な処理を発見するかそれに準ずる処理が必要となる． 例えば，不正なサーバを発見する処理としては，各サーバが処理をしたデータ一つ一つに対して，正しくシャッフルをしたという事実を証明させるという方式などがある． これは秘密のシャッフルを隠したままで，そのシャッフル処理が正当であったということを他者に証明するテクニックを用いる方式である(ゼロ知識証明)．
• Tor
  Tor（The Onion Router）は，TCP/IP における接続経路の匿名化を実現するための規格，及びそのリファレンス実装であるソフトウェアの名称である． Tor は，米海軍調査研究所 (NRL) が開発した通信システムをベースにオープンソース・コミュニティーが改良を加えて作成されている．
  Tor では，３つの Torノード（接続を中継するサーバ）をランダムに選択し，それぞれのノード間を暗号化しながら経由して目的のサイトにアクセスするので，アクセスログをたどろうとしても何重にも暗号化が施されているため逆探知ができない．また，１分おきに経路を変更するため同一人物によるアクセスであると思われるのを防ぐことができる (→ 匿名通信プロトコル (Tor))．

／