MENU

IT導入のヒントブログ IT BLOG

【参加レポート】福岡ブロックチェーン勉強会#42(ブロックチェーンを支えるアルゴリズム) (その2)(Schnorr 署名編)

こんにちは、スミリオンの長嶋です。
以下の勉強会に参加してきましたので、内容をレポートします。(その2)

 
福岡ブロックチェーン勉強会#42(ブロックチェーンを支えるアルゴリズム) の参加レポート続きです
https://gbec.connpass.com/event/158117/
 
今回は、ブロックチェーンを支えるアルゴリズムと題し、「ECDSA」と「Schnorr 署名」について、中城さんに説明して頂きました。
「ECDSA」については前回のレポートご覧ください。
 
【参加レポート】福岡ブロックチェーン勉強会#42(ブロックチェーンを支えるアルゴリズム) (その1)(ECDSA編)
https://www.smillione.co.jp/staffblog/2019/12/04/blockchain-seminar42-01/
 
今回は「Schnorr 署名」についてレポートします。
 

Schnorr 署名について

Schnorr 署名については、以下のサイトなどをベースに説明して頂きました。
https://blog.visvirial.com/articles/721
Schnorr(シュノア)署名はこうした電子署名方式の一つであり、1989年ごろに C.P.Schnorr 氏により発明されました。
しかしながら発明と時を同じくしてアメリカ国立標準技術研究所 (NIST) により DSA が提唱されたことや、
2008年まで Schnorr 自身の取得した特許により保護されており自由に利用できなかったなどの政治的な理由で
あまり利用されて来ませんでした。
しかしながら理論的側面だけに注目すると他のどの電子署名方式と比較しても計算が単純で分かりやすく、 またセキュリティ的な根拠もしっかりしていることなどから近年注目を集めているそうです。(上記のページから引用)
 
もろもろの説明の後にSchnorr 署名の数式の説明にはいりました。
 
Schnorr 署名の動作原理を端的に表すのは以下の式です。

記号の定義は以下になります。

 
この式をよく見ると変数 e が式の両辺に現れており、関数に対する入力が出力にも依存するような「自己言及型」の式となっています。 ハッシュ関数には一方向性がありますので、入力の “e” と出力の “e” がたまたま一致するように選ぶのは一見すると極めて難しそうです。
もし適当に y と e の値をランダムに選んできたとすると、ハッシュ関数の出力値 e’ は e とはほぼ独立に定まるランダムな値であり、 e の値とハッシュ関数の出力値 e’ がたまたま一致するという奇跡が起きない限りこの式を満たすような変数ペア (y, e) を見つけることはでなさそうです。
Bitcoin をご存じの方は Proof-of-Work (PoW) で目的のハッシュ値を見つけることを想像すると、これがいかに困難なのかが分かるのではないでしょうか。(上記のページから引用)
 
ここまでの説明で、中城さんが参加者から怒涛のように質問攻めにあっていましたが、この数式を満たす変数ペア (y, e) は奇跡に近いとか、こんな数式は成立しないとか、いろいろな意見が飛び交っていました!
 
 
 
で、ここから種明かし?(数式の証明)が始まります。。。。
 
秘密鍵 s を知っているとこの式をみたすような変数ペア (y, e) を魔法のように見つけることができてしまうのです。 トリックは、公開鍵 p が整数 g と秘密鍵 s を用いて p=gs と表せることです。 これを用いて上の式の右辺を書き換えると(上記のページから引用)

 
と変形することができます。 このように指数部分を共通化することができると何が嬉しいかというと、 r := (y + se) の値は変えずに、y と e の値の配分のみを変えることで e の値を自由に調整できます。 従ってあとはハッシュ関数の出力値と e が一致するように調整を行えば上の方程式をみたす変数ペア y, e を見つけることができます(上記のページから引用)
 

アルゴリズム

以下に Schnorr 署名の電子署名アルゴリズムを示します。(上記のページから引用)

署名作成

q をある巨大な素数とし、g を q と互いに素な整数とする。 また m を署名対象のメッセージ(ビット列)、整数 s を秘密鍵、H(⋅;⋅) をハッシュ関数とする。
 

 
ここで求めた (y, e) を電子署名として出力する。
 
説明はここまででしたが、変数ペア (y, e) を簡単に求めることが出来る結果については、参加全員唖然としていました。
中には、狐につままれたようと表現した方もいました。
分かってしまえば、何ともないですが、最初の式を見たときはどう証明するのかは本当に???でした。
 
今回は、タイトル通り「ブロックチェーンを支えるアルゴリズム」と言うことで、「ECDSA」と「Schnorr 署名」を理解することが出来ました。
また少しブロックチェーンの理解が深まったかなって思います。
次回からも継続的にGBECが主催する勉強会に参加し、ブロックチェーンを勉強していきたいと思います。
 
では、また
 
 
■参考資料
Schnorrベースのマルチシグネチャスキーム「MuSig」
https://techmedia-think.hatenablog.com/entry/2018/01/25/125426