シュノア署名

暗号学において、シュノア署名はクラウス・シュノアによって記述されたシュノア署名アルゴリズムによって生成されるデジタル署名である。これはその単純さで知られるデジタル署名方式であり、その安全性が特定の離散対数問題の扱いにくさに基づいている最初の方式の1つである。これは効率的であり、短い署名を生成する。^{[1]これは2010年2月に失効した}米国特許4,995,082によって保護されていた。

• 署名方式のすべてのユーザーは、離散対数問題が困難であると想定される、素数位数 、生成元 のグループ 、に同意します。通常は、 Schnorr グループが使用されます。${\displaystyle G}$${\displaystyle q}$${\displaystyle g}$
• すべてのユーザーは暗号ハッシュ関数 に同意します。${\displaystyle H:\{0,1\}^{*}\rightarrow \mathbb {Z} /q\mathbb {Z} }$

以下、

• 指数はグループ演算の繰り返し適用を表す。
• 並置は、合同クラスの集合に対する乗算、またはグループ演算の適用（該当する場合）を表します。
• 減算は合同類の集合上の減算を表す。
• ${\displaystyle M\in \{0,1\}^{*}}$、有限ビット列の集合
• ${\displaystyle s,e,e_{v},x,k\in \mathbb {Z} /q\mathbb {Z} }$、合同クラスの集合を法として${\displaystyle q}$
• ${\displaystyle y,r,r_{v}\in G}$。

• 許可されたセットから秘密署名キーを選択します。${\displaystyle x}$
• 公開検証キーは です。${\displaystyle y=g^{-x}}$

メッセージに署名するには、次の操作を行います。 ${\displaystyle M}$

• 許可されたセットからランダムに選択します。${\displaystyle k}$
• させて。${\displaystyle r=g^{k}}$
• とします。ここで は連結を表し、 はビット文字列として表されます。${\displaystyle e=H(r\parallel M)}$${\displaystyle \parallel}$${\displaystyle r}$
• させて。${\displaystyle s=k+xe}$

署名は、 のペアです。 ${\displaystyle (s,e)}$

注意してください。の場合、署名表現は 64 バイトに収まります。 ${\displaystyle s,e\in \mathbb {Z} /q\mathbb {Z} }$${\displaystyle q<2^{256}}$

• させて${\displaystyle r_{v}=g^{s}y^{e}}$
• させて${\displaystyle e_{v}=H(r_{v}\Parallel M)}$

その場合、署名は検証されます。 ${\displaystyle e_{v}=e}$

署名されたメッセージが検証されたメッセージと等しいかどうかは 比較的簡単にわかります。${\displaystyle e_{v}=e}$

${\displaystyle r_{v}=g^{s}y^{e}=g^{k+xe}g^{-xe}=g^{k}=r}$、したがって。 ${\displaystyle e_{v}=H(r_{v}\Parallel M)=H(r\Parallel M)=e}$

パブリック要素 : 、、、、、、、。プライベート要素: 、。${\displaystyle G}$${\displaystyle g}$${\displaystyle q}$${\displaystyle y}$${\displaystyle s}$${\displaystyle e}$${\displaystyle r}$${\displaystyle k}$${\displaystyle x}$

これは、正しく署名されたメッセージが正しく検証されることを示しているだけです。安全な署名アルゴリズムには、他の多くのプロパティが必要です。

密接に関連した署名アルゴリズムであるDSA、ECDSA、ElGamalと同様に、異なるメッセージの2つのSchnorr署名の秘密ノンス値を再利用すると、観察者は秘密鍵を復元できます。^[2] Schnorr署名の場合、これは単に値を減算する必要があります。 ${\displaystyle k}$${\displaystyle s}$

${\displaystyle s'-s=(k'-k)-x(e'-e)}$。

しかし、は単純に分離することができます。実際、 の値にわずかな偏りがあったり、 が部分的に漏洩したりしても、十分な数の署名を集めて隠し番号問題を解決すれば、秘密鍵を明らかにすることができます。^[2]${\displaystyle k'=k}$${\displaystyle e'\neq e}$${\displaystyle x}$${\displaystyle k}$${\displaystyle k}$

署名方式は、シュノアの識別プロトコル^{[4] [5]に}フィアット・シャミア変換^{[3]を適用することによって構築された。したがって、（フィアットとシャミアの議論によれば）が}ランダムオラクルとしてモデル化される場合、それは安全である。 ${\displaystyle H}$

その安全性は、が「ランダムプレフィックス原像暗号耐性」と「ランダムプレフィックス第二原像暗号耐性」であるという仮定の下、一般群モデルでも議論できる。 ^[6] 特に、衝突耐性である必要はない。 ${\displaystyle H}$${\displaystyle H}$

2012年、Seurin ^{[1] は}Schnorr 署名方式の正確な証明を提供しました。特に、Seurin は、Schnorr 型署名や Guillou–Quisquater 署名方式を含む一方向群準同型に基づくあらゆる署名方式に対して、フォーク補題を使用したセキュリティ証明が最良の結果であることを示しています。つまり、ROMDL 仮定の下では、あらゆる代数的還元は成功時間比の係数を失う必要があります。ここで、は「が 1 より著しく小さい」限り 1 に近い値を維持する関数です。ここで、はランダム オラクルに最大でクエリを実行して エラーを偽造する確率です。${\displaystyle f({\epsilon }_{F})q_{h}}$${\displaystyle f\leq 1}$${\displaystyle {\epsilon }_{F}}$${\displaystyle {\epsilon }_{F}}$${\displaystyle q_{h}}$

前述のプロセスは、 4 つのtビット署名でtビットのセキュリティ レベルを実現します。たとえば、128 ビットのセキュリティ レベルには、512 ビット (64 バイト) の署名が必要です。セキュリティは、グループに対する離散対数攻撃によって制限されます。この攻撃の複雑さは、グループ サイズの 平方根です。

1991年のシュノアのオリジナル論文では、ハッシュの衝突耐性は必要ないので、より短いハッシュ関数でも同様に安全である可能性があることが示唆されており、実際、最近の開発では、 3つのtビット署名でtビットのセキュリティレベルを達成できることが示唆されています。 ^{[6]そうすると、128ビットのセキュリティレベルには384ビット（48バイト）の署名のみが必要となり、これは}eのサイズをsビットフィールドの長さの半分になるまで切り捨てることで達成できます。

Schnorr署名は数多くの製品で使用されています。注目すべき使用法としては、Taprootアップデート後のビットコイントランザクション署名にsecp256k1楕円曲線を使用した決定論的Schnorr署名があります。 ^[7]

• DSSA
• エドDSA
• エルガマル署名方式

• RFC 8235
• BIP 340: secp256k1 の Schnorr 署名