秘密分散方式

秘密分散方式
廣瀬勝一
廣瀬
秘密分散方式
1 / 20
内容
• しきい値法 (threshold scheme)
• 検証可能な秘密分散方式 (verifiable secret sharing (VSS) scheme)
• 一般の秘密分散方式
• しきい値暗号 (threshold cryptography)
廣瀬
秘密分散方式
2 / 20
(t, n) しきい値法
n 人の利用者の内の任意の t 人が秘密を復元できる．
t 人未満の利用者が結託しても秘密に関するいかなる情報も得られない．
1979 年に Blakley と Shamir が独立に提案した
• Blakley の方式はベクトル空間に基づく
• Shamir の方式は多項式補間に基づく
廣瀬
秘密分散方式
3 / 20
準備
n 人の利用者を U1 , U2 , . . . , Un とする
p は素数で，n < p
秘密 s は Zp の要素
各 Ui には di ∈ Zp が割り当てられる．なお，i ̸= j のとき di ̸= dj
例えば，Ui の ID を di として利用できる．
p と d1 , . . . , dn は公開
ディーラー D ̸∈ {U1 , U2 , . . . , Un } の存在を仮定する
D は秘密情報 s から部分情報 (share) si を計算し，Ui に配る
廣瀬
秘密分散方式
4 / 20
簡単な例
(1, n) しきい値法
1 ディーラー D は，各 1 ≤ i ≤ n について，si = s とする
2 D は安全な通信路を介して si を Ui に送る
(n, n) しきい値法
1 D は，各 1 ≤ i ≤ n − 1 について，si を無作為に選ぶ
2 sn = s − (s1 + · · · + sn−1 ) mod p
3 D は安全な通信路を介して si を Ui に送る
注意
• 「安全な通信路」は盗聴，改ざんのない通信路を意味する
• これらの方式では di は不要
廣瀬
秘密分散方式
5 / 20
Shamir の (t, n) しきい値法
1
D は，各 1 ≤ j ≤ t − 1 について，秘密かつ無作為に aj ∈ Zp を選び，
多項式 f (x) を以下のように定める
f (x) = s + a1 x + a2 x2 + · · · + at−1 xt−1 mod p
このとき，秘密 s について，s = f (0) である
2
D は安全な通信路を介して si = f (di ) を Ui に送る
任意の t 人の利用者 Ui1 , Ui2 , . . . , Uit は以下の式で s を復元できる
s=
t
∑
k=1
廣瀬
sik
∏
1≤ℓ≤t,ℓ̸=k
diℓ
mod p
diℓ − dik
秘密分散方式
6 / 20
検証可能な秘密分散法
各利用者は，自分の部分情報が正しいことを確認できる
• Feldman 1987
• Pedersen 1991
離散対数問題に基づく方式
廣瀬
秘密分散方式
7 / 20
Feldman の VSS (1/2)
p, q は素数で q | p − 1 を満たす．g を Z∗p の位数 q の元とする．
1
D は，各 1 ≤ j ≤ t − 1 について，秘密かつ無作為に aj ∈ Zq を選び，
多項式 f (x) を以下のように定める
f (x) = s + a1 x + a2 x2 + · · · + at−1 xt−1 mod q
2
3
D は，各 0 ≤ j ≤ t − 1 について，Gj = g aj mod p を計算して公開
する．ここで，a0 = s である
D は安全な通信路を介して si = f (di ) を Ui に送る
廣瀬
秘密分散方式
8 / 20
Feldman の VSS (2/2)
Ui は以下の合同式を確認することにより，自分の部分情報が正しいかど
うかを確認できる
g si ≡ g f (di )
2
+···+at−1 di t−1
2
t−1
2
t−1
≡ g s+a1 di +a2 di
≡ g s g a1 di g a2 di · · · g at−1 di
≡ G0 G1 di G2 di · · · Gt−1 di
≡ ((· · · ((Gt−1 di )Gt−2 )di · · · )G1 )di G0 (mod p)
この方式では，G0 = g s が公開されるので，離散対数問題が解けないと
いう仮定の下でのみ，s は安全
廣瀬
秘密分散方式
9 / 20
Pedersen の VSS (1/2)
p, q は素数で q | p − 1 を満たす．g, h を Z∗p の位数 q の元とする．
1
D は，各 0 ≤ j ≤ t − 1 について，秘密かつ無作為に aj , bj ∈ Zq を選
び，多項式 f1 (x), f2 (x) を以下のように定める．ただし，a0 = s で
ある．
f1 (x) = s + a1 x + a2 x2 + · · · + at−1 xt−1 mod q
f2 (x) = b0 + b1 x + b2 x2 + · · · + bt−1 xt−1 mod q
2
3
D は，各 0 ≤ j ≤ t − 1 について，Gj = g aj hbj mod p を計算して公
開する．
D は安全な通信路を介して si = f1 (di ), ri = f2 (di ) を Ui に送る
廣瀬
秘密分散方式
10 / 20
Pedersen の VSS (2/2)
Ui は以下の合同式を確認することにより，自分の部分情報が正しいかど
うかを確認できる
g si hri ≡ g f1 (di ) hf2 (di )
≡ g a0 +a1 di +a2 di
2
+···+at−1 di t−1 b0 +b1 di +b2 di 2 +···+bt−1 di t−1
h
2
2
≡ (g a0 hb0 )(g a1 di hb1 di )(g a2 di hb2 di ) · · · (g at−1 di
t−1
2
≡ (g a0 hb0 )(g a1 hb1 )di (g a2 hb2 )di · · · (g at−1 hbt−1 )di
2
≡ G0 G1 di G2 di · · · Gt−1 di
hbt−1 di
t−1
)
t−1
t−1
≡ ((· · · ((Gt−1 di )Gt−2 )di · · · )G1 )di G0 (mod p)
G0 = g s hb0 が公開されるが，s に関する情報は全く漏れない
廣瀬
秘密分散方式
11 / 20
一般の秘密分散法 (1/4)
U = {U1 , U2 , . . . , Un } を利用者の集合とする
定義（アクセス構造）秘密を復元できる U の部分集合の集合
例 (t, n) しきい値法のアクセス構造は，Γ = {P | P ⊆ U ∧ |P| ≥ t}
n = 4, t = 2 のとき


 {U1 , U2 }, {U1 , U3 }, {U1 , U4 }, {U2 , U3 }, {U2 , U4 }, {U3 , U4 }, 
{U1 , U2 , U3 }, {U1 , U2 , U4 }, {U1 , U3 , U4 }, {U2 , U3 , U4 },
Γ=


{U1 , U2 , U3 , U4 }
任意のアクセス構造 Γ は単調である，すなわち
P ⊆ P′ ∧ P ∈ Γ ⇒ P′ ∈ Γ
廣瀬
秘密分散方式
12 / 20
一般の秘密分散法 (2/4)
任意のアクセス構造 Γ はブール関数で表現できる
αΓ : {0, 1}n → {0, 1}
P ⊆ {U1 , U2 , . . . , Un } について，z P ∈ {0, 1}n を以下のように定める
{
1 Ui ∈ P のとき
P
zi =
0 Ui ̸∈ P のとき
αΓ は以下のように定義される
αΓ (z P ) = 1 ⇔ P ∈ Γ
廣瀬
秘密分散方式
13 / 20
一般の秘密分散法 (3/4)：アクセス構造を表すブール関数の例
U = {U1 , U2 , U3 , U4 } とする
• Γ1 = {{U1 , U2 }, {U1 , U3 , U4 }, {U2 , U3 , U4 }} とすると
αΓ1 (z1 , z2 , z3 , z4 ) = z1 z2 ∨ z1 z3 z4 ∨ z2 z3 z4 = z1 z2 ∨ (z1 ∨ z2 )z3 z4
• Γ2 を (2, 4) しきい値法のアクセス構造とすると
αΓ2 (z1 , z2 , z3 , z4 ) = z1 z2 ∨ z1 z3 ∨ z1 z4 ∨ z2 z3 ∨ z2 z4 ∨ z3 z4
∨ z1 z2 z3 ∨ z1 z2 z4 ∨ z1 z3 z4 ∨ z2 z3 z4
∨ z1 z2 z3 z4
= z1 z2 ∨ z1 z3 ∨ z1 z4 ∨ z2 z3 ∨ z2 z4 ∨ z3 z4
廣瀬
秘密分散方式
14 / 20
一般の秘密分散法 (4/4)
任意のアクセス構造 Γ について αΓ : {0, 1}n → {0, 1} は単調
定義（半順序関係）z = (z1 , z2 , . . . , zn ) ∈ {0, 1}n とする．
各 1 ≤ i ≤ n について，zi = 1 ⇒ zi′ = 1
のとき z ⪯ z ′ と表記する．
定義（単調ブール関数）ブール関数 α : {0, 1}n → {0, 1} について
z ⪯ z ′ ⇒ α(z) ≤ α(z ′ )
のとき，α は単調．
すべての単調ブール関数は AND 素子と OR 素子のみで計算できる
廣瀬
秘密分散方式
15 / 20
しきい値暗号
Desmedt 1987
• 利用者は秘密分散法で秘密鍵を共有している
• 秘密鍵を復元することなく，復号や署名などを行うことができる
廣瀬
秘密分散方式
16 / 20
しきい値 Diﬃe-Hellman 法 (1/3)
p, q は素数で，g は Z∗p の位数 q の元であるとする
Alice
Bob
秘密鍵
sA ∈ Zq
sB ∈ Zq
公開鍵
vA = g sA mod p
vB = g sB mod p
Diﬃe-Hellman 法で Alice と Bob が得る鍵は
K = g sA sB mod p = vB sA mod p
今，sA が Shamir の (t, n) しきい値法で共有されているとする
f (x) = sA + a1 x + a2 x2 + · · · + at−1 xt−1 mod q
さらに，i = 1, 2, . . . , n について，si = f (di )
廣瀬
秘密分散方式
17 / 20
しきい値 Diﬃe-Hellman 法 (2/3)
任意の t 個の部分情報 si1 , si2 , . . . , sit について
sA =
t
∑
k=1
sik
∏
∑
diℓ
mod q =
ck sik mod q
diℓ − dik
t
1≤ℓ≤t,ℓ̸=k
ここで
k=1
∏
ck =
1≤ℓ≤t,ℓ̸=k
diℓ
mod q
diℓ − dik
したがって
K = vB sA mod p = vB
∑t
k=1 ck sik
mod p =
t
∏
vB ck sik mod p
k=1
Uik のみが vB ck sik mod p を計算できる
廣瀬
秘密分散方式
18 / 20
しきい値 Diﬃe-Hellman 法 (3/3)
アルゴリズム
1
2
各 Uik は Kk = vB ck sik mod p を計算して他の利用者に配布する
∏
各 Uik は K = tk=1 Kk mod p を計算する
安全性
• sA は復元されない
• Kk = vB ck sik mod p から sik を得るのは困難（離散対数問題）
廣瀬
秘密分散方式
19 / 20
演習問題
1
t = 2 をしきい値とする Shamir 秘密分散の部分情報を持ち寄ったと
ころ，(1, 2), (2, 0), (3, 2) であった．秘密を復元せよ．なお，法は
q = 11 である．
廣瀬
秘密分散方式
20 / 20

Download Report