ΣプロトコルとSchnorr識別

Σプロトコルは3つのメッセージで構成されます。(1) コミット：証明者がランダムな値へのコミットメントを送信します。(2) チャレンジ：検証者がランダムなチャレンジを送信します。(3) 応答：証明者がチャレンジと秘密から計算した応答を送信します。検証者は証明を受理または拒否します。

証明者は秘密x（秘密鍵）を知っており、公開鍵はg^x mod pです（楕円曲線上では点X = x*Gです）。目標は、xを明かさずにxを知っていることを証明することです。これは離散対数の知識証明です。

(1) 証明者がランダムなrを選び、コミットメントR = r*Gを送信します。(2) 検証者がチャレンジc（ランダムな整数）を送信します。(3) 証明者が応答s = r + c*xを送信します。(4) 検証者がs*G == R + c*Xを確認します。正しければ受理します。証明者はxを知っており、応答sはxがなければ計算できません。

完全性：正直な証明者は常にs*G = r*G + c*x*G = R + c*Xを満たします。健全性：同じRに対して異なるチャレンジc、c'を使った2つのトランスクリプトからは、s、s'が得られ、x = (s-s')/(c-c')を復元できます。したがって、だます側は同じRに対して2つの有効な応答を生成できません。

シミュレーター（xを知らない）：ランダムなsとcを選び、R = s*G - c*Xと設定します。この(R, c, s)は、有効なトランスクリプトと同じ分布になります。検証者は、実際のトランスクリプトとシミュレーションされたトランスクリプトを区別できません。Schnorrは正直な検証者に対するゼロ知識性を持ちます。

Schnorrを非対話型にするには、検証者のチャレンジをc = Hash(R || message)に置き換えます。証明者は自分でcを計算して応答します。その結果、誰でも検証できる2要素の証明(R, s)が得られます。これがSchnorr署名方式です。

Sign(x, m): r ← random; R = r*G; c = Hash(R||m); s = r + c*x. Signature = (R, s). Verify: s*G == R + Hash(R||m)*X. コンパクトで（P-256では64バイト）、バッチ検証が可能であり、ROMで安全性が証明されています。Bitcoin Taproot（BIP-340）で採用されています。

C = r*G + v*Hです。ここでHは2つ目の独立な生成元です。乱数rを使って値vにコミットします。拘束性：異なるvに対して開示することはできません（離散対数の困難性によります）。秘匿性：Cは一様分布します。Schnorrベースの範囲証明やBulletproofsで使用されます。

x1 AND x2の知識を同時に証明するには、同じチャレンジを使って2つのSchnorrプロトコルを実行します（Fiat-Shamirによってチャレンジを共有します）。検証者は、両方のサブ証明が有効な場合にのみ受理します。これにより、1回の対話で複数の命題を証明できます。

どちらを知っているかを明かさずに、x1 OR x2の知識を証明します。一方の分岐ではシミュレーターを使って偽のトランスクリプトを計算し、両方の分岐にチャレンジを分割します。検証者には、実際のチャレンジの合計と一致する、どちらも有効に見える2つのトランスクリプトが示されます。これは「リング署名」と呼ばれます。

Schnorr ID：電子パスポート（PACEプロトコル）。Schnorr署名：Bitcoin Taproot、Monero（RingCTではSchnorr OR証明を使用）、Signal Protocol（X3DH鍵合意）。Pedersenコミットメント：Confidential Transactions、Bulletproofs、Zcash Saplingノート暗号化。

Schnorr識別プロトコルでは、最後の手順で検証者は何を確認しますか？

Σプロトコルは、コミット、チャレンジ、応答で構成されます。Schnorrは離散対数の知識を証明します。Fiat-Shamirにより非対話型になります（Schnorr署名）。次は、簡潔な非対話型証明を実現するzk-SNARKです。