Shamirの秘密計算 - ト部蛸焼のブログ

こんにちは．物工/計数 Advent Calendar 2019の2日目を担当する，計数工学科B4のト部蛸焼です．今日はShamirによって提案された秘密計算の手法をご紹介します．
adventar.org

導入
- 秘密計算とは
- 状況設定と方針
準備
- Lagrange補間
- 用語の定義
CEPSの導入
CEPSの正当性
CEPSの秘密性
まとめ
参考文献

🐙🍣🐙🍣🐙🍣🐙🍣🐙🍣

導入

🍣🐙🍣🐙🍣🐙🍣🐙🍣🐙

秘密計算とは

秘密計算とは，簡単に言えば「自分の持っている秘密の情報をほかの人に知られないまま目的の量を計算*1する」手法を研究する分野です．

秘密計算は認証・デジタル署名・秘密通信などと並んで暗号理論の一角をなす分野で，次のような場面での応用が期待されています．

電子投票
特許を申請する前に行う先行技術調査
秘密性の高い情報の研究

具体的な例を挙げます．いま，ある学生が所属学科の学生の平均体重のデータを研究に使いたくなったとします．彼はみんなの体重を聞き回ろうとしますが，すぐに「みんなは自分の体重を他人に教えたがらないだろう」と思い直します．果たして，学科のみんなが自分の持っている秘密の情報 (=体重) をほかの学生に知られないまま目的の量 (=平均値) を計算するなんてことは可能でしょうか．可能です．そう，秘密計算なら．

状況設定と方針

今回扱うShamirの秘密計算における状況設定は以下の通りです．

$n$ 人のプレイヤー $\mathsf{P}_{1}, \dots, \mathsf{P}_{n}$ がそれぞれ秘密 $x_{1},\dots,x_{n}$ をもっている*2．
体 $K$ への $n$ 変数関数 $F(x_{1},\dots,x_{n})$ の値を計算して結果を公開 (共有) する．
計算の過程では $x_{i}$ ( $i \in [n]$ *3 ) の値に関する情報は秘匿される*4．

以下では理解を優先して $K=\mathbb{R}$ とします*5．

体 $K$ には和と積の2つの演算があります．そのため，体 $K$ 上で秘密計算を行うためには，この2つの演算を “秘密に” 行う方法を考えればよいことになります．

Shamirは，そのために多項式を使いました．具体的には，秘密 $s$ を計算に使うときに，まずそれに対応する多項式 $f(X)$ を， $f(0) = s$ を満たすように一つ選びます．そして，その秘密を復元するピースとして $f(1), \dots, f(n)$ をプレイヤー $\mathsf{P}_{1}, \dots, \mathsf{P}_{n}$ にそれぞれ渡します．

核となる考えはこれだけです．この方法でうまくいくかはピンと来ないと思いますが，実はこれで $s$ の値を隠したまま， $s$ の値が関係する和や積が計算できます．

f:id:tobetakoyaki:20191121131233p:plain — 秘密を多項式 $f(X)$ に埋め込むイメージ

🐙🍣🐙🍣🐙🍣🐙🍣🐙🍣

準備

🍣🐙🍣🐙🍣🐙🍣🐙🍣🐙

ここではShamirの秘密計算を理解するための数学的な準備を行います．

Lagrange補間

Lagrange補間とは， $t$ 個の点が与えられたときに，それらすべての点を通る $t$ 次以下の多項式 $f(X) \in K[X]_{\le t}$ を計算する方法です．具体的には次の式で計算できます．

命題 $f(X) \in K[X]_{\le t}$ ， $C \subseteq K$ ，ただし $|C| = t+1$ とする．このとき，多項式 $f(X)$ は像 $f(C)$ から次の式で構成できる．
\begin{align}
f(X) &= \sum_{i \in C} f(i) \delta_{i} (X), \label{eq:lll} \\
\delta_{i} (X) &= \prod_{j \in C \setminus \{i\}} \frac{X-j}{i-j}.
\end{align}

この命題の証明は註に譲ります*6．

また， $r_{i} := \delta_{i}(0)$ として，ベクトル $\boldsymbol{r} = (r_{1} \, \dots \, r_{n})^{\top}$ をrecombination vectorと呼ぶことにします．

Lagrange補間を使うと， $t+1$ 個以上の点での値が分かれば元の多項式が復元できます．特に $X = 0$ での値も復元できます．

用語の定義

以下で， $n$ は秘密計算を行うプレイヤーの人数です．

定義 $a \in K$ に対して， $f(X) \in K[X]_{\le t}$ は $f(0) = a$ を満たすとする．このとき， $[a;f]_{t}$ を次で定義されるベクトルのこととする．
\begin{align}
[a;f]_{t} := \begin{pmatrix}
f(1) \\ f(2) \\ \vdots \\ f(n)
\end{pmatrix}.
\end{align}

次の命題が成立します．証明は容易です．ここではベクトル $[a;f]_{t}$ の演算がうまく体の演算に対応することと積の場合には多項式の次元が倍増することの2つが重要です．

命題 $a, b, \alpha \in K$ ， $f(X), g(X) \in K[X]_{\le t}$ とする．
1. $[a;f]_{t} + [b;g]_{t} = [a+b; f+g]_{t}$ .
2. $\alpha [a;f]_{t} = [\alpha a; \alpha f]_{t}$ .
3. $[a;f]_{t} * [b;g]_{t} = [ab; fg]_{2t}$ . ここで左辺の積は要素ごとの積を表す．

定義1. 値 $s \in K$ を共有 (share) するとは， $f(0) = s$ となる多項式 $f(X) \in K[X]_{\le t}$ を乱択して，各プレイヤー $\mathsf{P}_{j}$ に $s_{j} = f(j)$ を密かに送ることをいう．このとき， $s_{j}$ のことを秘密 $s$ のシェア (share) という．

2. プレイヤー $\mathsf{P}_{i}$ が $[a; f_{a}]_{t}$ を分配 (distribute) するとは，次の2つの手続きを行うこととする．

$f_{a}(0) = 0$ となる $t$ 次以下の多項式を乱択する．
各プレイヤー $\mathsf{P}_{j}$ に $f_{a}(j)$ を密かに送る．

3. プレイヤー全員が $[a;f_{a}]_{t}$ を保持 (hold) しているとは，プレイヤー全員が $t$ 次以下の多項式 $f_{a}$ に基づいて秘密 $a$ のシェアを獲得していること．

4. プレイヤー全員が $[a;f_{a}]_{t}$ と $[b;f_{b}]_{t}$ を保持しているとする．このとき，プレイヤー全員が $[a;f_{a}]_{t} + [b;f_{b}]_{t}$ を計算 (compute) するとは，各プレイヤー $\mathsf{P}_{j}$ が秘密 $a$ のシェア $f_{a}(j)$ と秘密 $b$ のシェア $f_{b}(j)$ から $f_{a}(j) + f_{b}(j)$ を計算することをいう．
$\alpha [a;f_{a}]_{t}$ を計算することや $[a;f_{a}]_{t} * [b;f_{b}]_{t}$ を計算することも同様に定義する．

いま定義した概念と演算回路を用いてShamirの秘密計算を実現する方法が，次に示すCEPS (Circuit Evaluation with Passive Security) *7です．

🐙🍣🐙🍣🐙🍣🐙🍣🐙🍣

CEPSの導入

🍣🐙🍣🐙🍣🐙🍣🐙🍣🐙

CEPSの仕様を以下に示します．

f:id:tobetakoyaki:20191123164536p:plain — CEPSの仕様

……といわれてもよくわからないので，次の例題で詳細を確認しましょう．

例題入力を $(x_{1}, x_{2}, x_{3}) = (2, 4, 3)$ として $F(x_{1}, x_{2}, x_{3}) = x_{3} \left( x_{1} + x_{2} \right)$ の値を秘密に計算する，3人のプレイヤーからなるCEPSの動きを記述せよ．ただし用いる多項式の次数は $t = 1$ とする．

1. 入力の共有
まず，各プレイヤーに $x_{1},x_{2},x_{3}$ のシェアを分配します．分配では多項式を乱択する必要がありました．ここでは次の $i_{1}(X), i_{2}(X), i_{3}(X)$ を乱択したとしましょう．
\begin{align}
i_{1}(X) &:= 2 + X, \label{eq:x1share}\\
i_{2}(X) &:= 4 - 2X, \label{eq:x2share} \\
i_{3}(X) &:= 3 + 2X. \label{eq:x3share}
\end{align}すると各プレイヤーに渡される $x_{1}, x_{2}, x_{3}$ のシェアは表1のようになります．

ちなみにこの表は，例えばプレイヤー $\mathsf{P}_{1}$ は $x_{1}$ について3， $x_{2}$ について2， $x_{3}$ について5という値を知っているということを表しています．いま読み取った値は各変数の本当の値 (=秘密の値) を復元するために使えるピースであり，一般には本当の値とは異なる値になります．

f:id:tobetakoyaki:20191123164639p:plain:w225

2. 計算段階
先に $z := x_{1}+x_{2}$ を計算します．表1から各プレイヤーは表2のように各変数について情報を持ちます．値をそのまま足すだけです．

f:id:tobetakoyaki:20191123164715p:plain:w300

次に $y = x_{3} z$ を計算します．先ほども述べたようにただ掛けただけでは秘密を埋め込んだ多項式の次数が2倍になってしまうので，それを避ける工夫がなされます*8．とはいえまずは値の掛け算をします．その計算結果は表3のようになります．

f:id:tobetakoyaki:20191123164744p:plain:w275

秘密を埋め込んだ多項式の次数を落とすため，次のように多項式を選び直します．

まずは各プレイヤー $\mathsf{P}_{i}$ が多項式 $f_{i}(X)$ を乱択します．ここでは以下を選んだとします．
\begin{align}
f_{1}(X) &:= 25-7X, \\
f_{2}(X) &:= 28-6X, \\
f_{3}(X) &:= 27+X.
\end{align}

次にプレイヤーが3人のときのrecombination vector $\boldsymbol{r}$ を計算します*9．
\begin{align}
\boldsymbol{r} = \begin{pmatrix}
3 \\ -3 \\ 1
\end{pmatrix}.
\end{align}最後に，プレイヤー全員が $\displaystyle \sum_{i=1}^{n} r_{i} [h(i); f_{i}]_{t}$ を計算します．こうするとなぜうまくいくのかは後で4. CEPSの正当性のところで示します．これで積のゲートの処理は終わりです．

結果的には表4のようなシェアを各プレイヤーは保持したことになります．なんだかうまくいってそうです．

f:id:tobetakoyaki:20191123164808p:plain:w300

3. 出力の復元
計算は終わったのであとは計算結果を復元する作業に入ります．

まずプレイヤー全員がほかのプレイヤーに自分のシェアを送ります．すると，結局はプレイヤー全員が $y$ の値について $y_{1} = 16, y_{2} = 14, y_{3} = 12$ というシェアを知った状況になります．あとは先に述べたLagrange補間を行えば正しい $y$ の値が復元できます．
\begin{align}
y = \sum_{i=1}^{3} r_{i} y_{i} = \begin{pmatrix}
3 & -3 & 1
\end{pmatrix} \begin{pmatrix}
16 \\ 14 \\ 12
\end{pmatrix} = 18.
\end{align}

🐙🍣🐙🍣🐙🍣🐙🍣🐙🍣

CEPSの正当性

🍣🐙🍣🐙🍣🐙🍣🐙🍣🐙

ここでは，特に2. 計算段階の積のゲートについて正しさを確かめます*10．具体的には「CEPSの仕様」で突然導入した多項式 $\displaystyle \sum_{i=1}^{n} r_{i} [h(i); f_{i}]_{t}$ が，0での値が $ab$ であるような $t$ 次の多項式であることを示します．

計算します．
\begin{align}
\sum_{i=1}^{n} r_{i} [h(i); f_{i}]_{t}
&= \left[ \sum_{i=1}^{n} r_{i} h(i); \sum_{i=1}^{n} r_{i}f_{i} \right]_{t} \\
&= \left[ h(0) ; \sum_{i=1}^{n} r_{i}f_{i} \right]_{t} \label{eq:recombine} \\
&= \left[ ab ; \sum_{i=1}^{n} r_{i}f_{i} \right]_{t}.
\end{align}なお，式\eqref{eq:recombine}の等号は，recombination vectorについて
\begin{align}
h(0) = \sum_{i=1}^{n} r_{i} h(i)
\end{align}が成り立つことによります．これで目標は達成されました．

🐙🍣🐙🍣🐙🍣🐙🍣🐙🍣

CEPSの秘密性

🍣🐙🍣🐙🍣🐙🍣🐙🍣🐙

ここではCEPSのプロトコルを行う過程で，プレイヤーが他の人の秘密の値を特定できないことを説明します．簡単のため*11，先ほどの例題の場合を考えます．さらに，特にプレイヤー $\mathsf{P}_{1}$ に注目し，自分の得ている情報から他の値の組み合わせを一意に定められるか否かを試します．なお，以下ではプレイヤー $\mathsf{P}_{1}$ にとって確定している値は青い字で表します．

まず， $x_{1} + x_{2}$ の計算についてです．この時点で $\mathsf{P}_{1}$ が得ている情報は表5で全てです．

f:id:tobetakoyaki:20191123164831p:plain:w300

変数 $x_{2}$ の値は例題によると本当は4でした．しかし，プレイヤー $\mathsf{P}_{1}$ はこの値を知りません．これを当てるために，とりあえずいろいろな数字で試し打ちをしてみます．すると例えば表6や表7のような結果が得られます．

f:id:tobetakoyaki:20191123164852p:plain:w600

これから分かるのは，プレイヤー $\mathsf{P}_{1}$ の持つ情報だけでは $x_{2}$ の値を3なのか (表6)，4なのか (例題)，5なのか (表7) を特定できないということです*12．よって $x_{2}$ の秘密は守られたといえます．

今度は $x_{3} \cdot z$ について確かめます．最終的な $y$ のシェアも含めた $\mathsf{P}_{1}$ の得ている情報は表8で全てです*13．

f:id:tobetakoyaki:20191123164920p:plain:w300

先ほどと同様に試し打ちをします．すると，表9や表10に示したものがあります．

f:id:tobetakoyaki:20191123164938p:plain:w600

ということは $x_{3}$ や $z$ の値の秘密性は担保されたことになります．

結局，プレイヤー $\mathsf{P}_{1}$ は他のプレイヤーの値の情報を入手できませんでした．これで秘密性が示されました．

🐙🍣🐙🍣🐙🍣🐙🍣🐙🍣

まとめ

🍣🐙🍣🐙🍣🐙🍣🐙🍣🐙

今回はCEPSと呼ばれるプロトコルを導入し，その正しさを検証しました．ところどころ註で述べましたが，CEPSの正当性や秘密性を数学的に証明するとなると，もっと複雑な手続きが必要となります．概して，暗号の分野では直観的に「安全だ」と判断することは簡単でも，それを数学的に証明しようとなると格段に難しくなります．これは今後の私の人生でやや不安なところでもあります．

ともかく，今回お伝えしたかったのは，

秘密計算という分野があること
実際に秘密計算を行う方法が存在すること

の2つです．なんとなくでもこれらが伝わっていれば幸いです．

稚拙で冗長な文章でしたが，ここまでお読みいただきありがとうございました．

明日の物工/計数 Advent Calendar 2019の記事もお楽しみに！

参考文献

Ronald Cramer, Ivan Bjerre Damgård, and Jesper Buus Nielsen. Secure Multiparty Computation and Secret Sharing. Cambridge University Press. 2015.

菊池亮, 五十嵐大. 秘密計算の発展 —データを隠しつつ計算する仕組みとその発展—. https://www.jstage.jst.go.jp/article/essfr/12/1/12_12/_pdf/-char/en. 2018. (参照: 2019年11月23日).

*1:この「計算」には単なる数値の演算だけでなく文字列の一致検索も含まれます．

*2:先の例だと各学生 $\mathsf{P}_{i}$ の体重の値が $x_{i}$ となります．

*3: $[n] := \{1,\dots,n\}$ とします．

*4:正確にはもう少し厳しい条件が課されます．

*5:実際に演算回路で計算を行うときには，体 $K$ は有限体を考えます．

*6:証明． $t$ 次の多項式には $t+1$ 個の係数があるが，いま， $|C| = t+1$ であるから， $C$ 上の点を全て通る多項式 $f(X)$ は一意に定まる． $\delta_{i} (X)$ はその定義式から \begin{align} \delta_{i}(j) = \begin{cases} 1 & (i=j), \\ 0 & (i \neq j). \end{cases} \end{align}したがって式\eqref{eq:lll}の右辺に $X=j$ を代入すると \begin{align} \sum_{i \in C} f(i)\delta_{i}(j) = f(j). \end{align}

*7:passive securityとは，秘密計算のプロトコルに対する攻撃者のモデルを指します．秘密計算では，攻撃者がプロトコルに従ったまま秘密を盗聴する場合 (passive modelまたはsemi-honest model) と，攻撃者がプロトコルから逸脱して秘密を改竄しうる場合 (active modelまたはmalicious model) の2つを考えます．今回はそのうち比較的条件が緩い前者のセキュリティモデルを考え，その枠組みで安全性を考えています．

*8:なぜ避ける必要があるのでしょうか．いま，この例から少し離れて，例えば $x_{1}^{N}$ を計算する場合を考えてみます．積を単純な掛け算で終わらせてしまうと，この1回の積の計算で秘密を埋め込んだ多項式の次数はもとの2倍になります．すると， $N > \log_{2} \dfrac{n}{t}$ 回だけこの積を繰り返すと，秘密を埋め込んだ多項式の次数 $2^{N} t$ はプレイヤーの人数 $n$ より大きくなってしまいます．これではLagrange補間によって多項式を復元することはできません．そのため，次数を2倍にしたまま放置してはいけないのです．

*9:この計算を具体的に示します．recombination vectorの $i$ 番目の成分 $r_{i}$ は \begin{align} r_{i} = \delta_{i}(0) = \prod_{j \neq i} \frac{0-j}{i-j} \end{align}で与えられるので，次のようにして成分の値が求まります． \begin{align} r_{1} &= \frac{(-2)(-3)}{(1-2)(1-3)} = 3, \\ r_{2} &= \frac{(-1)(-3)}{(2-1)(2-3)} = -3, \\ r_{3} &= \frac{(-1)(-2)}{(3-1)(3-2)} = 1. \end{align}

*10:厳密には「すべてのプレイヤーが，与えられた入力に対して意図される正しい出力を，確率1で得られる」ことを示す必要があります．この性質はperfect correctnessと呼ばれます．プロトコルの途中ではたくさん乱数を選びます．そのどの選び方をしてもプロトコルは正しく機能しますよ，というのがperfect correctnessです．ちなみにここでの「perfect」は確率1で成り立つことを，「correctness」はプロトコルが正しく機能することを表しています．

*11:この部分の話を厳密にしようと思うとかなり厄介ですが，その流れだけここに簡単に記します．そもそもここでいう秘密性とは，perfect privacyという「 $t$ ( $< n/2$ ) 人以下の邪悪なプレイヤーからなる集合を $C$ としたとき，プロトコルの実行過程から $\{x_{j}, y_{j}\}_{\mathsf{P}_{j} \in C}$ 以上の情報を得られないこと」を意味します．その下で，まず，プロトコルを実行して分かる情報を整理します．そして「シミュレーター」と呼ばれるこのプロトコルを仮想的に再現する機構を構築して，実際にプロトコルを行って得られる情報と，そのシミュレーターの出力とを比較します．もし，この2つがある意味で一致すれば確率的に安全だと評価します．