暗号応用技術

秘密計算

秘匿計算，依頼計算 (代理計算)

利用者 A が秘密に保持している情報 $x$ に関する計算 $f(x)$ を $x$ を知らせないで他の実行者 B に行わせる方式を秘匿計算という．署名対象データの内容を伏せたまま署名を行わせるブラインド署名も秘匿計算の一種である．

特に，依頼者 A が秘密に保持している情報 $x$ に関する計算 $f(x)$ を $x$ を知らせないで他の実行者 B に効率的に行わせる方式を依頼計算(Server-aided computation)という．計算能力の低い A が高い計算能力を持つ B に計算を依頼し結果を得るものである．

RSA暗号の依頼計算
RSA暗号の公開鍵を $(e, n)$，秘密鍵を $d$ とし，依頼者 A は $d$ を秘密にしたまま $x^d \bmod n$ を実行者 B に計算させる手順を示す．
1. A はランダムに $D=(d_1,\cdots,d_r)$，$G=(g_1,\cdots,g_r)$，$H=(h_1,\cdots,h_r)$ を定める．ここで，$r$ は適当な整数，$d_i \in Z_n$，$g_i \in \{0, 1\}$， $h_i \in \{0, 1\}$，Weight$(G) \le r$，Weight$(H) \le r$ である．Weight$(G)$ は $G$ のハミング重み ($\sum_{i=1}^r g_i$) である．
  
  $d \equiv gh\ (\bmod\ \lambda(n)),$
  
  $g \equiv d_1g_1 + \cdots + d_rg_r\ (\bmod\ \lambda(n)),$
  
  $h \equiv d_1h_1 + \cdots + d_rh_r\ (\bmod\ \lambda(n))$
  ここで，$\lambda(n) = LCM(p-1)(q-1),\ n= pq$ である．
2. A は，($n, D, x$) を B に送る．
3. B は，$Z=(z_1,\cdots,z_r)$，$z_i=x^{d_i}\ \bmod\ n$ を計算して $Z$ を A に送る．
4. A は，以下の計算を行い，$u$ を B に送る． $u=(\prod_{i=1}^r z_i^{g_i})t\ \bmod\ n\ (=x^gt\ \bmod\ n)$
5. B は，$V=(v_1,\cdots,v_r)$，$v_i=u^{d_i}\ \bmod\ n$ を計算して $V$ を A に送る．
6. A は，以下の計算を行う． $y=(\prod_{i=1}^r v_i^{h_i})t^{-h}\ \bmod\ n\ (=u^ht^{-h}\ \bmod\ n = x^d\ \bmod\ n)$
上記の手順により，A は何回かの積と剰余算によりべき乗剰余演算が行える．
ペアリング代理計算
IDベース暗号で用いられる楕円ペアリング演算を代理計算サーバを使って代理計算する．
楕円点 $P$，$Q$ のペアリング演算 $e(P, Q)$ を代理計算する手順は次のとおりである．
1. クライアントは，$a, b \leftarrow \{0, 1\}^n$ を選び， $P' = aP, Q' = bQ$ を計算し，$P$'，$Q'$ を代理計算サーバへ送る．
2. 代理計算サーバは，ペアリング演算 $e(P', Q')$ を行い結果をクライアントに返す．
3. クライアントは $(ab)^{-1}$ を計算する．
4. クライアントは，
  $e(P', Q')^{(ab)^{-1}} = e(P, Q)$
  を計算する．
上記の手順により．次のメリットがある．
- クライアント側のペアリング演算を，楕円スカラー倍，有限体上のべき乗演算に置き換えることができる．
- $a$，$b$ は，セキュリティパラメータ長程度の長さで構わないため，通常の楕円スカラー倍よりも平均的に高速に計算できる．
- 処理 2. と処理 3.は並行して行うことができる．

代理計算 (自己訂正器)

自己訂正とは
ある関数 $f$ を計算すると称するブラックボックス $F$（その出力は必ずしも正しいとは限らない）が与えられたとき, $F$ を使って任意の入力 $x$ に対して $f(x)$ を正しく計算する．
基本的なアイデア
対象関数の特性（準同型性）を用いて $x$ を隠蔽しつつ $F$ を多数回呼び出し, $F$ の出力から計算される分布から最頻値を取り出すことで $f(x)$ の値を推定する．

準同型関数： $f(ab) = f(a) f(b)$
1. ある $h$ を選び，$y = f(h)$ とする．また，$s$，$a$ をランダムに選ぶ．
2. $z_1 = F(h^s x)$，$z_2 = F(h^s x^a)$ を計算する (代理計算)．
3. $Z(1) = z_1 y^{-s} = f(h^s x) f(h)^{-s} = f(x)$
  $Z(a) = z_2 y^{-s} = f(h^s x^a) f(h)^{-s} = f(x)^a$
4. $Z(a) = Z(1)^a$ ならば，$F$ は正しいと判断する．

秘密計算プロトコル

秘密計算
$a$，$b$ の暗号文 $E(a)$，$E(b)$ が与えられたとき，分散された秘密情報を保有する複数の装置が計算に協力することで，$a$，$b$ を知ることなく$a + b$ の暗号文 $E(a + b)$，および $a \times b$ の暗号文 $E(ab)$ を求めることができる方式である．
$0$ または $1$ からなる入力の数値が暗号化された状態のまま，それらの数値の加算および乗算の結果(の暗号文) を求めることができれば，基本論理演算(NOT，AND，OR，NAND，NOR)は，加算と乗算から求められる．すなわち，入力の数値が暗号化された状態のまま任意の関数(論理式)の値を計算できることになる．
暗号化・復号
基本となる 1ビットの暗号化・復号演算を定義する．以下では，楕円演算ベースで定義するが，他の演算系でも良い．
$G$ を有限体上で定義された楕円曲線上の有理点からなる群とする．点 $P$ を $G$ の元とし，$G$ の位数を $n$ とする．また，秘密鍵 $x \in \{1, \ldots, n\}$ に対して $Q = xP$ (楕円 $x$ 倍算)を公開鍵とし，($G$, $n$, $P$) を公開情報(システムパラメータ)とする．
このとき，平文 $a \in \{0,1\}$ を暗号化する暗号関数 $E$ を次のように定義する． \[ E(a, r) = (A, B) = (rP, (r + a)Q). \] ここで $r$ は $1$ 以上 $n$ 以下の乱数である．
復号処理は \[ xA = \left\{ \begin{array}{ll} B & \quad (a = 0)\\ B - Q & \quad (a = 1) \end{array}\right. \] が成り立つことから，秘密鍵 $x$ を用いることで $E(a, r)$ を復号できる．すなわち，$xA = B$ であれば復号結果は $0$ であり，$xA = B - Q$ であれば復号結果は $1$ である．
- 加算 (ADD)
  $a$，$b$ の暗号文 $E(a, r)$，$E(b, s)$ から $a + b$ の暗号文を計算することができる．
  $a,b \in \{0, 1\}$ の暗号文 $E(a, r)$，$E(b, s)$ から $a + b$ の暗号文は次のように求められる． \[ E(a,r)+E(b,s) = ((r+s)P, (r+a+s+b)Q) \] が成り立つことから，$a + b$ の暗号文は \[ E(a+b, r+s) = E(a,r)+E(b,s) \] となる．
  暗号文 $E(a, r)=(A_1,B_1)$，$E(b, s)=(A_2,B_2)$ の加算に対する復号結果は，秘密鍵を $x$ として \[ x(A_1+A_2) = B_1+B_2-mQ \] を満たす $m$ が $a + b$ である．
プロトコル
秘密計算のプロトコルには，次のようなものがある．
- マルチパーティプロトコル
  2つの暗号文から平文の排他的論理和(XOR)を求めるプロトコルである． NOT，AND，OR，NAND，NORを表す基本論理関数は，ADDとXORを用いて計算可能である．
  集計，最頻値，平均値，分散などの統計計算に必要な演算をこれらの基本論理関数を組合せて実現することができる．
- YAO プロトコル
  $n$ ビットの入力回路関数 $f$ と入力暗号文から，暗号文を復号することなく入力回路関数 $f$ の出力値を計算するプロトコルである．
  最大値，中央値，集計，最頻値等の統計計算回路を入力とすることにより，暗号データに対して統計計算を行うことができる．
秘密計算プロトコルの応用
入力データを秘匿したまま任意の論理演算が可能なことから，次のような応用が考えられる．
- アンケート結果分析
  複数の情報提供クライアントからアンケート情報を収集し，その提供情報を秘匿したまま統計情報を取得する．
- マーケティング分析
  インターネットユーザに暗号化した属性情報を保持させ，サイトアクセス時に暗号化した属性情報を提示させることによりプライバシを保護した統計解析を行う．暗号化したままの属性情報に対して秘密計算を用いることで，個別の属性情報を開示することなく統計解析を行える．