Schnorr signature
Prover は Verifier に Prover の pubkey v に対応する秘密鍵 s を知っていることを証明したい
Prover は乱数 r から $ x = α^{r} である x を生成する。Verifier は乱数 e を生成する。Prover は $ y = r + se を生成する。$ x' = α^{y}v^{e} = α^{y}(α^{-s})^{e} = α^{y - se} = rG = xであれば、Prover は正しい s を知っている。
Prover は$ x = α^{r} = α^{y}v^{e} になるような $ y = r + se を見つけるのが仕事、という感じか
楕円曲線においては sG = rG + eP が示せるか？と問われている
$ x = α^{r},$ y = r + se であれば、$ x = α^{y}v^{e} である
e が事前にわかっていれば、$ x = α^{r}v^{e} $ y = r とすることで、s がわからなくても成り立つ x,y を作れてしまう。
楕円曲線の場合
$ x = rG - eP, $ s = rとすると
$ x' = sG - eP = rG - eP = x となり、p がわからなくても署名がつくれる
ここで $ e = Hash(x) とすることで、直前に行ったように e に応じて x を変更することができない。
説明２
$ sG = R + eP となるような $ s = r + ep を pを知らずに見つけるのは難しい。
p が分かれば、$ e = H(sG - epG, m) = H((s-ep)G, m)なので
$ s - ep = r とすれば、$ s = r + ep を示すことができる
nonce の使い回しはダメ
Difined at BIP340 for bitcoin usage schnorr
code:shell
e = H(m,R+P) とあるが H(m,R+eP)と考えると良いと思う つまり H(m,kG+edG)
s = k + ed
s,R が署名
R=kG, P=dG
このとき
code:shell
s = k + ed(この関係性を制限として導入することで e に以下のような制約がかかる)
sG = kG + edG
e = H(kG+edG) = H(m,sG)
このとき、秘密鍵dを知らずに上記を満たす e を見つけるのは困難
e は Hash値であるがe自身に依存しているため。ただし、d がわかるのであれば、任意のsによりeを算出し、s=k+edを満たすkを見つけるのは容易である。
https://www.youtube.com/watch?v=XKatSGCZ-gE
schnorr の詳しい説明はない。schnorr の性質とその応用が主な話。
schnorr はシンプル？
署名に加法準同型がある？
マルチシグが比較的かんたんに実現できる
rogue-key attack 対策が必要
schnorr を破れる = 離散対数問題を解決することらしい
ECDSA は違うらしいがなぜ？
コントラクトに対応する一つの秘密鍵を生成できる
Adaptor signature
ECDSA にはセキュリティプルーフがないけど shnorr にはあるらしい https://youtu.be/YSUVRj8iznU?t=428
Pros
batch verifiability
lineariy
署名の和は、キーの和の署名
https://youtu.be/2WbSGO70-ig?t=450