デジタル署名の定義

デジタル署名の概要 (Overview of Digital Signature) 🔗

BobがAliceへメッセージを送るとき、Aliceは、そのメッセージが本当にBobから来たものかを確認する必要があります。

\rightarrow

デジタル署名

を使います。

Bobの秘密鍵がなければ、誰もBobの署名を生成できません。

送信元（Bob）とデータの完全性（メッセージ）の両面で認証します。

デジタル署名方式は、次の三つの多項式時間アルゴリズムで構成されます。

KeyGen
( $\lambda$ $λ$ ) $\rightarrow$ $\to$ (pk, sk)：鍵生成アルゴリズムです。
- セキュリティパラメーター $\lambda$ を入力し、公開鍵(pk)と秘密鍵(sk)を生成します。
Sign
(sk, m) $\rightarrow$ $\to$ $\sigma$ $σ$ ：署名アルゴリズムです。
- 秘密鍵(sk)とメッセージ(m)を入力し、デジタル署名( $\sigma$ )を生成します。
Verify
(pk, m, $\sigma$ $σ$ ) $\rightarrow$ $\to$ {0, 1}：検証アルゴリズムです。
- 公開鍵(pk)、メッセージ(m)、デジタル署名( $\sigma$ )を入力し、署名が有効かを検証します。
- 有効であれば1、そうでなければ0を返します。

正当性

：検証アルゴリズムは、次の条件を満たさなければなりません。

チャレンジャー

C

と攻撃者

A

の間のゲームを考えます。

Setup： $C$ がKeyGen( $\lambda$ )を実行して $(pk, sk)$ を生成し、公開鍵 $pk$ を $A$ へ渡します。
Signing Queries： $A$ $A$ は、メッセージ $M_i$ $M_{i}$ について、多項式回の署名クエリを要求します。
- 各 $M_i$ について、 $C$ は $\text{Sign}(sk, M_i) → \sigma_i$ を実行して署名 $\sigma_i$ を生成し、 $A$ へ返します。
Output： $A$ $A$ が $(M, \sigma)$ $(M, σ)$ を返します。
- $M$ は $C$ が署名していないメッセージであり、 $A$ が署名を要求したメッセージとは異なります。
- $A$ が $M$ に対する有効な署名 $\sigma$ を生成できた場合、 $A$ の成功です。

A

の成功確率は、次のように定義します。

この署名方式は、適応的選択メッセージ攻撃（Adaptive Chosen Message Attack）に対して、強い偽造不可能性を持ちます。

多項式時間の攻撃者

A

が上のゲームに成功する確率が無視できるほど小さければ、その署名方式は強く

偽造不可能

です。