最初の固定例：(k,n)=(2,4)
この例には、秘密を持ち、シェアを作って配る人（ディーラー）と、4人の受取人が登場します。
① 配る人が秘密と乱数を用意する
ディーラーは秘密s=5を持っています。秘密とは別に、0〜12から同じ確率で乱数rを選びます。この固定例ではr=8です。
ディーラーは秘密と乱数を座標として並べ、点X=(s,r)=(5,8)を作ります。この点が、これから作る4本の直線に共通する交点になります。
② 配る人が各人の式を作る
GF(13)では0〜12を使い、計算結果を13で割った余りにします。たとえば12+2≡1 (mod 13)です。
ディーラーは、秘密sや乱数rの値を見ずに、条件を満たす係数a,bを選びます。その後、c=a s+b r (mod p)を計算して1本の式を作ります。この例ではp=13です。
a x₁ + b x₂ ≡ c (mod p)
シェアには、秘密sと乱数rを混ぜて計算した値cを入れます。a,bは混ぜるときに掛ける係数で、受取人ごとに係数の組を変えます。
この固定例では、係数(a,b)を#1:(1,3)、#2:(2,5)、#3:(4,2)、#4:(5,1)と決めています。#1などはシェアの識別番号で、aやbを計算するための数ではありません。
#1のb=3は、次の2条件を4組全体で満たすように、あらかじめ選んだ値です。3だけが正解というわけではありません。ここではk=2、法p=13の場合を説明します。
- 各組のbを0以外にする：どの秘密候補sにも、式を満たすrが1個ずつ残ります。秘密sの値によって選び方を変えず、rを0〜12から同じ確率で選びます（rを一様ランダムに選ぶ）。これにより、1枚のシェアから秘密sを絞れなくなります。
- どの2組も、一方に同じ数を掛けただけの組にしない：13で割った余りで比べます。こうすると2本の式が異なる条件になり、両方を満たす点が1つに決まります。
係数の選び方を具体例と式で確かめる
たとえば#1の(1,3)に対し、次の組に(2,6)を選ぶと2倍になってしまいます。右辺cを実際に計算してみます。
点X=(s,r)=(5,8)、係数(a,b)=(2,6)なので、a×s+b×r=5a+8b=5×2+8×6=10+48=58です。58=13×4+6より、13で割った余りは6です。したがってc=6となります。
式は2x₁+6x₂≡6 (mod 13)です。これは#1の式全体を2倍しただけなので、2枚集めても新しい条件が増えません。
実際の#2は(a,b)=(2,5)です。#1を2倍した(2,6)とは一致しません。
同じX=(s,r)=(5,8)から、a×s+b×r=5a+8b=5×2+8×5=10+40=50と計算します。50=13×3+11より、13で割った余りは11なのでc=11です。#2の式は2x₁+5x₂≡11 (mod 13)となります。
2本の式から秘密sを復元する
2本の式は、#1：x₁+3x₂≡3、#2：2x₁+5x₂≡11（どちらもmod 13）です。
#1の両辺を2倍すると、2x₁+6x₂≡6 (mod 13)です。ここから#2の式を引くと、x₁の項が消え、x₂≡6−11=−5≡8 (mod 13)となります。−5に13を足すと8なので、x₂=8です。
この値を#1に代入すると、x₁+3×8≡3 (mod 13)です。両辺から24を引くと、x₁≡3−24=−21≡5 (mod 13)となります。−21に13を2回足すと5なので、秘密s=x₁=5を復元できます。
#2に代入して「2で割る」求め方
同じx₂=8を#2に代入すると、11≡2x₁+5×8=2x₁+40 (mod 13)です。両辺から40を引くと、2x₁≡11−40=−29≡−3≡10 (mod 13)となります。
2と13は互いに素（共通の正の約数が1だけ）なので、2にはmod 13での逆数があります。2×7=14≡1 (mod 13)より、その逆数は7です。
両辺に7を掛けると、x₁≡7×10=70≡5 (mod 13)となり、同じ秘密s=5を得られます。合同式で「2で割る」とは、このように2の逆数を掛ける操作です。法と互いに素な数であれば、この割り算ができます。
法を素数にする理由
法pが素数なら、1〜p−1のすべての数がpと互いに素で、逆数を持ちます。だから、連立方程式を解く途中で0以外の係数で割る操作ができます。先ほどのmod 13で「2で割る」操作も、この性質を使っています。
法が合成数だと、0以外でも逆数がない数があります。たとえばmod 12では、3にどの整数を掛けても余りは0,3,6,9のいずれかで、1にはなりません。
#1へ代入する最初の求め方では、係数が1なので逆数を求める操作は不要です。#2へ代入する別の求め方では、2の逆数を使いました。ただし、法が素数でも、同じ条件を表す2本の式からは点を1つに決められません。係数の組にも、次の条件が必要です。
一般に、2組を(a,b)と(d,e)と書くと、a e−d bがmod 13で0以外なら、2本の式から点が1つに決まります。#1と#2では1×5−2×3=−1≡12なので条件を満たします。固定例の4組では、どの2組を選んでもこの値は0以外です。
係数をランダムに選ぶ必要はありません。固定例とは別に、番号から係数を決める方法もあります。k=2なら、0以外の異なる番号iに対して(a,b)=(1,i)とします。i=1,2,3,4なら(1,1),(1,2),(1,3),(1,4)となり、同じ2条件を満たします。
この規則をk=3へ広げると、係数は(1,i,i²)になります。1,i,i²,…を並べた行を集めた表を「ヴァンデルモンド行列」と呼びます。以降の設定において、この係数の作り方を採用する場合は「番号から作る（ヴァンデルモンド）」を選んでください。
係数は秘密や乱数の値に依存させずに決め、公開したり使い回したりできます。一方、乱数rは秘密を分け直すたびに、秘密とは独立に全範囲から同じ確率で選び直します。係数を固定することと、乱数rを固定することは別です。
#1ではa=1,b=3を使います。秘密と乱数を混ぜた1×5+3×8=29を13で割り、その余りc=3を求めます。シェアの中身は(a,b,c)=(1,3,3)です。
③ 配る人がシェアを渡す
ディーラーは各人に、その人用のa,b,cの組を1枚のシェアとして渡します。全員が法p=13を知っていれば、この3つの数から式を組み立てられます。秘密sや乱数r、点Xの座標は渡しません。
4人に配る4本の式（最初の固定例）
| 配るシェア |
シェアの中身 (a,b,c) |
式 |
|---|
| #1 |
(1,3,3) |
x₁ + 3x₂ ≡ 3 (mod 13) |
| #2 |
(2,5,11) |
2x₁ + 5x₂ ≡ 11 (mod 13) |
| #3 |
(4,2,10) |
4x₁ + 2x₂ ≡ 10 (mod 13) |
| #4 |
(5,1,7) |
5x₁ + x₂ ≡ 7 (mod 13) |
④ 受取人がシェアを持ち寄る
受取人が任意の2枚以上を持ち寄ると、式をすべて満たす点X=(5,8)が求まります。その第1座標が秘密s=5です。1枚だけではsの13候補がすべて残ります。
1枚では秘密を絞れない理由
#1のシェアからわかるのはs+3r≡3 (mod 13)です。(s,r)=(5,8)だけでなく、(0,1)でも(2,9)でもこの式を満たします。13個のどのsにも、式を満たすrがちょうど1個あります。
rを0〜12から同じ確率で選ぶと、どのsでも右辺c=3になる確率は1/13です。そのため、このシェアを受け取っても、どのsが選ばれた可能性が高いかは変わりません。s自体の選ばれ方を一様に変えるという意味ではありません。
ここでは法が13で、rに掛ける3が0以外なので、この対応が成り立ちます。たとえばrの係数が0の式x₁≡cなら、cから秘密sがわかります。秘密を隠せるかどうかは、式の形と乱数の選び方の両方に依存します。
この画面では、仕組みを学ぶためにディーラーの答えも示します。受取人にわかる範囲は、集めたシェアから残る候補として示します。
このように各sにrが1個ずつ対応するとき、rを秘密とは別に全範囲から同じ確率で選べば、シェアを受け取っても各sの選ばれやすさは変わりません。s自体を同じ確率で選ぶという意味ではありません。