あっている自信、無。。。。
目標: これを書き終わる頃にはグループ署名の論文が読めていること。
群ってなんだよ
|
|
群の例
加法群
整数全体の集合を考えて、足し算についてみてみると 「2」と「3」を足し算すると「5」になる。
加法で群を作るので加法群と呼ぶ。
コンピュータを交えて考えると、非常に大きい値も含まれてしまうので上限値を作る。
はみ出たらその余りを取ることとする。
整数全体の集合を$\mathbb{Z}$で表すが、上限を設ける場合はこの様に書く。 例えば上限が100なら$\mathbb{Z}_{100}$である。
ちなみに$\mathbb{Z}/100\mathbb{Z}$とも書かれる様です。
例として一つ。$\mathbb{Z}_{100}$においては、89+15= 104 が100で割った余りを取るので、4になります。
乗法群
これも超えた分はそれの余りを使用することが多いです。
なので上限値を100とした場合はこのようになります。
$$ 13 * 9 = 17 $$
書き方としては加法群と区別をつけるために${\mathbb{Z}^{*}}_{100}$や${(\mathbb{Z}/100\mathbb{Z})}^{*}$が書かれます。
単位元
群には単位元と呼ばれる特別なモノがある。
これは他のモノと合体させたとしても、合体相手と同じものになってしまうようなものがある。
例えば加法群では0が単位元になる。
例えば、
$$ 13+0=13 $$
となるからである。
乗法群では1が単位元になる。
$$ 13*1=13 $$
逆元
群には逆元と呼ばれる特別なものもある。
あるモノxに対して、xと合体させると単位元になるようなモノをxの逆元と呼ぶ。
例えば加法群において、3の逆元は-3になる。
$$ 3-3=0 $$
になるからである。
ここで乗法群において、3の逆元は$\frac{1}{3}$ となる。
$$ 3*\frac{1}{3}=1 $$
になるからである。
ざっと調べた感じ逆元を表す時、モノの↑にバーをつける様子。
よし、ここまで行けば理解出来るはずだ。。。
早速ちょうど読んでた論文のゼロ知識証明部分の解説を試みてみる。
2018 9th International Conference on Information Technology in Medicine and Education
「Research on Online Quiz Scheme Based on Double-layer Consortium Blockchain」
さてこの論文が何かと言うと、クイズの解答の検証をブロックチェーンで行おうみたいな感じです。
ブロックチェーンには管理者の立場であるGroup Manager $manager$とGroup Memberで構成されており、解答を行っているGroup Memberを$member$とします。
$member$はGroup Managerや他のGroup Memberに解答を伝えず、解答を持っていることを証明したいです。
いざいくぞ
前提として
$q$ : 巨大な素数、全員に公開されている。
$results$ : クイズの答え
$h$ q乗根の有限巡回群の生成器 (公開)
生成器ってなんだよ
$$ x = hash(results) \in \mathbb{Z}_q $$
$hash$関数は全員が把握しているとし、$member$は問題を解くことで解答$x$を得たこととします。
$member$はランダムに群 ${\mathbb{Z}^*}_q$から1つ要素を選び、$r$とします。その後$ t = h^r \in \mathbb{C} $を計算して$t$を公開します。
$manager$はランダムに群 ${\mathbb{Z}^*}_q$から1つ要素を選び、$c$とします。 $manager$は$c$を公開します。
$member$は$ s \equiv xc + r \begin{eqnarray}\pmod{q}\end{eqnarray}$を計算して公開。
最後に公開された情報を使って、以下の式が成立するか確認を行います。成立すれば解答は正しいです。
$$ h^s = y^ct $$
$x$が異なっていても有限巡回群の要素$h$の不規則性から推測が難しいのが肝になっています。
これで$x$を伝えずに解答のあっている証明をすることが出来ました。