Help us understand the problem. What is going on with this article?

Feldman VSS

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

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

調べた結果、はっきりしない部分:

  • 計算の各所においてmodulo pとqのどちらを使うべきかについて、wikiとSOで意見が違う
  • wikiに沿って作って動かなかった人がSOで質問していて、$P(x)$は$\bmod q$で、コミットメントの計算は$\bmod p$でやればOKという回答がある

設定

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

秘密の分散

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

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

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

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

秘密の復元

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

秘密のシェアの検証

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

$$
\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)}$が同じ値になれば、受け取ったシェアはディーラーが送ったものと同じものと言える。

参考資料

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

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
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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
ユーザーは見つかりませんでした