Shamirの秘密分散とラグランジュ補間の関係をわかりやすく整理する

はじめに

前回のポストでは、「使いたいが外に出せない」データを扱う技術として、秘密分散と秘密計算をまとめて紹介しました。データを投入する時点でシェアに分けるのが秘密分散、分けたまま計算するのが秘密計算、という対の関係です。

今回はこのうち秘密分散のほうを掘り下げます。調べていると必ず出てくる「Shamirの秘密分散法」と「ラグランジュ補間」が、どう繋がっているのかを整理します。

この記事の内容は次のとおりです。

秘密分散とは、1つの秘密情報を複数のシェア（断片）に分割し、一定数以上のシェアが集まったときだけ元の秘密を復元できるようにする技術です。(k, n)しきい値法と呼ばれ、以下の2つのパラメータで構成が決まります。

例えば(2, 3)の場合、3人にシェアを配り、そのうち2人が集まれば復元できます。前回の記事で図にしたのは、全員分が揃わないと復元できない単純な形でしたが、こちらは「何人集まればよいか」を設計できる方式です。

Shamirの秘密分散法の核心は、秘密情報を多項式の定数項として埋め込むという発想です。

秘密情報をsとすると、ディーラー（分散する人）は次のようなk-1次多項式をランダムに作ります。

f(x) = s + a1・x + a2・x^2 + … + a(k-1)・x^(k-1)

そして、各参加者i（i = 1, 2, …, n）に対して、点(i, f(i))をシェアとして配ります。参加者はx座標（自分の番号）とy座標（計算結果）のペアを1つ持つだけで、多項式の中身は知りません。

なお実際の実装では、この計算を実数ではなく有限体（十分大きな素数pによる剰余）の上で行います。実数のままだとシェアの大きさから秘密の範囲が推測できてしまい、後述の「情報理論的に安全」が成り立たないためです。

多項式には、次の性質が数学的に保証されています。

k-1次多項式は、異なるx座標を持つk個の点が与えられれば、ただ一つに定まる。

逆に言えば、k個未満の点しかなければ、その次数の多項式は無数に存在し得ます。この「一意に定まる／定まらない」の境界が、そのまま秘密分散の閾値kに対応します。

「情報理論的に安全」というのは、計算能力をいくら積んでも破れない、という意味です。候補が無数にあって、そのどれもが等しくあり得るので、総当たりしても絞り込めません。

「k個の点から、それらを通るk-1次多項式を具体的に計算する」ための道具がラグランジュ補間です。

k個の点(x1, y1), …, (xk, yk)が与えられたとき、ラグランジュ補間は次の式でその多項式を構築します。

一見複雑ですが、やっていることはシンプルです。各項の分数部分は「x = xiのときに1、それ以外のxjのときに0になる」ように作られた基底多項式で、これにyiを掛けて全部足し合わせると、ちょうど全ての点を通る式が出来上がります。

秘密分散の復元では、この式にx = 0を代入するだけで済みます。

つまり復元処理は、集めたk個のシェアをラグランジュ補間の公式に当てはめてx = 0の値を計算するだけ、ということになります。

次数が低いほどイメージしやすいので、具体例で見てみます。

まずk = 2（1次式、直線）の場合です。秘密をs = 1234、乱数をa1 = 56とすると、多項式はf(x) = 1234 + 56xになります。3人に配るシェアは次の3点です。

図の読み方: 3つのシェアは、同じ1本の直線の上に並んでいます。直線は2点あれば1本に決まるので、誰と誰の組み合わせでも2人揃えば直線が引けて、そのy切片が秘密です。逆に1点だけでは、そこを通る直線は無数に引けるので、秘密はどんな値でもあり得ます。

実際に参加者1と参加者3のシェアから復元してみます。ラグランジュ補間の式にx = 0を入れるだけです。

s = 1290 × (0-3)/(1-3) + 1402 × (0-1)/(3-1)
  = 1290 × 1.5 − 1402 × 0.5
  = 1935 − 701
  = 1234

参加者2を飛ばしても、きちんと元の1234に戻りました。

次にk = 3（2次式、放物線）の場合です。2点だけでは、その2点を通る放物線は無数に存在します（曲がり方の自由度が残るため）。3点目が揃って初めて、放物線がただ1本に確定します。

次数を上げるほど、復元に必要な点の数（＝結託しないと秘密が漏れない人数）も増えていきます。kは「何人が結託したら秘密が漏れるか」を決めるパラメータでもある、ということです。

概念	役割
Shamirの秘密分散法	秘密を多項式の定数項に埋め込み、各参加者に多項式上の点を配る方式
ラグランジュ補間	集めた点から元の多項式を復元し、`f(0)`を求めるための計算手法
閾値`k`	多項式の次数+1。これだけの点が集まれば数学的に多項式が一意に定まる

Shamirの秘密分散は「多項式はk個の点で一意に定まる」という数学的性質をセキュリティの根拠にしており、ラグランジュ補間はその一意な多項式を実際に計算する手段、という関係で整理すると理解しやすいと思います。