Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@kzee

Feldman VSS

シャミアの秘密分散法に、シェア検証の仕組みを加えたもの。ざっくり言うと:

  • 秘密を持っているディーラーが、複数の参加者に秘密をシェアという形で分散して配布する
  • しきい値以上のシェアが集まると秘密を復元することが出来る
  • 各参加者は、受け取ったシェアが正当なことを検証できる

設定

意味
しきい値 $t$
$q$ $\,p\,$で$\,q-1\,$が割り切れる素数
$g$ ジェネレーターの元
$p$ ジェネレーターの位数(素数)
$s$ 秘密 $\in \,\mathbb{Z}_q\,$
$P_i$ 参加者

秘密の分散

  1. ディーラーが、$\,t-1\,$次の多項式$\,P(x)\,$を以下の形でつくる

    • $P(0)=s$
    • $1$次以降の係数はランダムに $\,\mathbb{Z}_q\,$から選ぶ
    P(x) = a_{t-1}x^{t-1} + a_{t-2}x^{t-2} + ... + a_1x^1 + s 
    
  2. 各参加者$\,P_i\,$に、$P(i) \bmod q$の値を送る。e.g. $P(2) = a_2(2)^2 + a_1(2)^1 + s \bmod q$

  3. ディーラーが、$\,P\,$の全ての係数$\,a_i\,$に対して、コミットメント$\,c_i = g^{a_i} \bmod p\,$を計算する

  4. 各参加者に対して、全てのコミットメントを送る。

秘密の復元

$t$以上のシェアを集めて、多項式補間を使って$\,s\,$を復元する。
$t$未満のシェアでは復元不可。

秘密のシェアの検証

参加者$\,P_i\,$は、受け取ったシェア$\,P(i)\,$の値が正しいかを、全参加者分のコミットメントを使って検証できる。
コミットメントと検証では、位数がpの巡回群を使っているので、$\bmod p$を使う。

$$
\prod_{j=0}^{t} c_j^{i^{j}} = \prod_{j=0}^{t} g^{a_ji^j} = g^{\sum_{j=0}^t a_ji^j} = g^{P(i)} \bmod p
$$

なので、$\prod_{j=0}^{t} c_j^{i^{j}}$と、$g^{P(i)}$が同じ値になれば、受け取ったシェアはディーラーが送ったものと同じものと言える。

mod p と mod q

コミットメントと検証では、位数がpの部分群を使っているので、$\bmod p$、その他の部分では$\bmod p$を使う。
q-1を割り切れる素数pを使うと、離散対数問題を解くのが難しくなるので、そういうpを使っているということらしい。

参考資料

https://en.wikipedia.org/wiki/Verifiable_secret_sharing#Feldman.E2.80.99s_scheme
https://crypto.stackexchange.com/questions/6637/understanding-feldmans-vss-with-a-simple-example

0
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
kzee
話半分で聞いてください

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?