はじめに
署名方式を用いる際に，「署名したいメッセージをハッシュ関数にかけて得られたダイジェストへ署名を付与する」という運用方法（Hash-and-Sign）をとることがしばしばあります．
Hash-and-Signは，任意長のメッセージに対して署名を施すために，当たり前のように用いられる方法ですが，その安全性は保障されているのでしょうか？
実は，Hash-and-Signに関しては「その構成要素であるハッシュ関数と（固定長メッセージ）署名方式が"十分安全"であれば，"十分安全"である」ということが，暗号学的に証明できます．本稿では，Hash-and-Signの（暗号学的）安全性証明について解説します．
準備
negligible function（無視できる関数）
非負整数から実数への関数$\epsilon$がnegligibleであるとは，
任意の$c > 0$に対して，ある$k > 0$が存在して，任意の$n \geq k$について，$\epsilon(n) < 1 / n^c$
であることを言います．
例えば，指数関数の逆数（の非負整数への制限）$\exp(-n)$はnegligible関数の例です．
関数$\epsilon$がnegligibleであることを，$\epsilon(n) \leq negl(n)$と表記します．
$f(n) \leq negl(n), g(n) \leq negl(n)$ならば，$f(n) + g(n) \leq negl(n)$となります．
衝突困難ハッシュ関数の定義
$n$をセキュリティパラメータ（暗号の安全性を司るパラメータ）とします．
ハッシュ関数族$ \mathcal{H} = \{H_k : \{0,1\}^* \to \{0, 1\}^n \mid k \in \{0,1\}^n \}$が衝突困難であるとは，
任意の多項式時間アルゴリズム$A$に対して，
$\Pr[k \leftarrow \{0, 1\}^n, (x_0,x_1) \leftarrow A(k) ; x_0 \neq x_1 \wedge H_k(x_0) = H_k(x_1)] \leq negl(n)$
であることと定義します．
直観的には，「どのような多項式時間アルゴリズム（攻撃者）であっても，ハッシュ関数の出力を衝突させるような相異なる入力の対を見つけることは，（セキュリティパラメータを十分大きくとると）事実上できない」ということを定式化していると言えます．
署名方式の定義と安全性
（固定長メッセージ）署名方式の定義
次のアルゴリズムの3つ組$\Omega = (Gen, Sign, Verify)$が次の要件を満たすとき，
$\Omega$を（固定長メッセージの）署名方式と呼びます．
- $Gen(1^n)$ : $1^n$を入力として，検証鍵と署名鍵の組$(vk, sk)$を出力します．
- $Sign(sk, m)$：固定長メッセージ$m \{0,1\}^\ell$と署名鍵$sk$を入力として，署名$\sigma$を出力します．
- $Verify(vk, m, \sigma)$ ：検証鍵$vk$，メッセージ$m$と署名$\sigma$を入力として，ブール値$0/1$のいずれかを出力します（1が受理，0が拒否を表します）．
署名方式に求められる機能とは，「署名鍵を持つ者のみが（任意のメッセージに対して）正しい署名を生成することが出来る」ことです．ここでいう”正しい”署名とは，検証鍵を用いた検証処理に通る（$1$を出力する）ことを意味します．
翻って考えると，署名方式$\Omega$に対する"攻撃"とは「署名鍵を持たないものによる（検証をパスする）署名の偽造」に他なりません．
さて，方式に対する攻撃と安全性のモデルを考えるにあたって，”攻撃者の能力”と求める”安全性の強度”について定める必要があります．
攻撃者の能力として，署名オラクルにアクセスできる（攻撃者が選んだメッセージに対して，正しい署名を得ることができる）ことを仮定することが一般的です．この仮定は（署名鍵を持っていない）攻撃者が正しい署名を得ることができるという強いものですが，この状況であっても安全であれば署名方式として高い安全性を持つと言えます．この攻撃を選択文書攻撃（Chosen Message Attack, CMA）と呼びます．
安全性の強度としては，「どのようなメッセージに対しても，署名鍵なしでは正しい署名を生成できない」ということが要求されることが一般的です．この安全性を存在的偽造困難性（Existential UnForgeability, EUF）と呼びます．
EUF-CMA安全性
署名方式$\Omega = (Gen, Sign, Verify)$に対する攻撃者$F$について，次の施行$CMA_{\Omega, F}(n)$を定めます．ここで，$F$は署名オラクル$Sign(sk, \cdot)$へ$t = t(n)$（$n$についての多項式）回問い合わせる（メッセージに対する署名を得ることが出来る）と仮定します（この状況を$F^{Sign(sk, \cdot)}$と書くこともあります）．
- 試行$CMA_{\Omega, F}(n)$：
- $(vk, sk) \leftarrow Gen(1^n)$
- $i = 1,\ldots, t$について，$m_i \leftarrow F(vk)$，$\sigma_i \leftarrow Sign(sk, m_i)$（ここで，$F$は$sk$を見ることはできないことに注意）
- $(m, \sigma) \leftarrow F^{Sign(sk, \cdot)}(vk)$．ただし，$m \neq m_i (i = 1,\ldots,t)$とする．
- return $Verify(vk, m, \sigma) = 1$
この試行は，「署名の偽造を企む（署名オラクルにアクセス可能な）攻撃者$F$が検証に通るようなメッセージと署名の組を偽造する」というゲームです．ただし，署名オラクル問い合わせたメッセージを出力とすることは出来ません．
署名方式$\Omega = (Gen, Sign, Verify)$がEUF-CMA安全（Existential UnForgebility under Chosen Message Attack; 選択文書攻撃に対して存在的偽造困難）であるとは，
任意の多項式時間アルゴリズム$F$に対して，$\Pr[CMA_{\Omega, F}(n) = 1] \leq negl(n)$
であることと定義します．
直観的には，「署名オラクルにアクセスできるいかなる攻撃者であっても，署名鍵なしではいかなる偽造署名も（現実的には）作り出せない」ことを意味します．
Hash-and-Sign型署名方式
定義
ハッシュ関数と（固定長メッセージ）署名方式$\Omega = (Gen, Sign, Verify)$を用いて，
任意長メッセージ署名方式$\Omega' = (Gen', Sign', Vefity')$を次のように構成します．
- $Gen'(1^n)$: $(vk, sk) \leftarrow \Omega.Gen(1^n), k \leftarrow \{0, 1\}^n, vk' := (vk, k), sk' := (sk, k)$として，検証鍵と署名鍵の組$(vk', sk')$を出力します．
- $Sign'(sk', m')$: $m' \in \{0, 1\}^*$に対して，$\sigma' \leftarrow \Omega.Sign(sk, H_k(m))$を出力します．
- $Verify'(vk', m', \sigma')$ : $\Omega.Verify(vk, H_k(m'), \sigma')$を出力します．
単に，メッセージをハッシュにかけて署名している点（加えて検証鍵，秘密鍵にハッシュ関数のパラメータが含まれている点）のみが，もともとの固定長メッセージ署名方式との差分であることがわかります．
EUF-CMA安全性
一見安直な構成にも見える上述の任意長メッセージ署名方式が（構成要素である）固定長メッセージ署名方式とハッシュ関数が安全であれば，安全な署名方式であることが証明できます．
主張
$\Omega = (Gen, Sign, Verify)$を固定長メッセージ署名方式であって，EUF-CMA安全であるとします．また，ハッシュ関数族$ \mathcal{H} = \{H_k : \{0,1\}^* \to \{0, 1\}^n \mid k \in \{0,1\}^n \}$が衝突困難であるとします．このとき，上述の構成による任意長メッセージ署名方式$\Omega'$はEUF-CMA安全です．
安全性証明
$\Omega'$に対する任意の（多項式時間）攻撃者を$F$とします．
$F$は次の安全性ゲーム（試行）を行います．
- 試行$CMA_{\Omega', F}(n)$：
- $(vk', sk') \leftarrow Gen(1^n)$
- $i = 1,\ldots, t$について，$m_i \leftarrow F(vk)$，$\sigma_i \leftarrow Sign'(sk', m_i)$
- $(m, \sigma) \leftarrow F^{Sign'(sk', \cdot)}(vk)$
- return $m \neq m_i (i = 1,\ldots,t) \wedge Verify'(vk', m, \sigma) = 1$
この試行の中で起きうる事象$coll_{\Omega', F}$を次で定めます（この事象は実際に起きなくても構わず，ここではただ単に名前を付けているだけです）．
- 事象$coll_{\Omega', F}$：「攻撃者$F$が署名オラクルに問い合わせたあるメッセージ$m_i$について，$H_k(m) = H_k(m_i)$となる」
つまり$coll_{\Omega', F}$とは，「$F$がたまたまハッシュ関数$H_k$の衝突ペアを（最終的な出力メッセージとオラクルに問い合わせたメッセージのいずれかの組として）見つけてしまった」という事象を表しています．
さて，この定義した事象$coll_{\Omega', F}$によって，$F$の偽造成功確率（=$CMA_{\Omega', F} = 1$となる確率）を分解します．
\begin{align}
\Pr[CMA_{\Omega', F} = 1] &= \Pr[CMA_{\Omega', F} = 1 \wedge coll_{\Omega', F}] + \Pr[CMA_{\Omega', F} = 1 \wedge \neg coll_{\Omega', F}] \\
&\leq \Pr[coll_{\Omega', F}] + \Pr[CMA_{\Omega', F} = 1 \wedge \neg coll_{\Omega', F}]
\end{align}
右辺の2つの項がそれぞれneglであることを示すのが証明の戦略です．第1項をハッシュ関数の衝突困難性，第2項を元々の固定長メッセージ署名方式のEUF-CMA安全性を用いて片付けていきます．
まず第1項から見ていきます．
補題1
$\Pr[coll_{\Omega', F}] \leq negl(n)$
証明
$F$を用いてハッシュ関数族$\mathcal{H}$に対する攻撃者$C$（衝突ペアの算出アルゴリズム）を構成します．
- 攻撃者$C(k)$：
- 初期設定として$Q := \{\}$（空集合）とし，$(vk, sk) \leftarrow \Omega.Gen(1^n)$を起動します．
- $vk' := (vk, k)$を入力として，$F$を起動します：
- もし，$m_i$を$F(vk')$が署名オラクルへ問い合わせた場合，$C$は次を行います：
- $Q$を$Q \cup \{m_i\}$へ更新し，$\sigma_i \leftarrow \Omega.Sign(sk, H_k(m))$を$F$へ返します．
- $F$が偽造ペア$(m, \sigma)$を出力し終了したとき，$C$は次を行います：
- $m' \in \{m' \in Q \mid m' \neq m, H_k(m') = H_k(m) \}$を検索し，ペア$(m, m')$を出力し，停止します．
- もし，$m_i$を$F(vk')$が署名オラクルへ問い合わせた場合，$C$は次を行います：
この攻撃者$C$が衝突ペアを見つける確率，すなわち，
$\Pr[k \leftarrow \{0, 1\}^n, (m,m') \leftarrow C(k) ; m \neq m' \wedge H_k(m) = H_k(m')]$
は，事象$coll_{\Omega', F}$が発生する確率と等しい（2つの事象が等価である）ことがわかります．
すなわち，
$\Pr[coll_{\Omega', F}] = \Pr[k \leftarrow \{0, 1\}^n, (m,m') \leftarrow C(k) ; m \neq m' \wedge H_k(m) = H_k(m')]$
となりますが，右辺はハッシュ関数の衝突困難性から$negl(n)$です．
よって，$\Pr[coll_{\Omega', F}] \leq negl(n)$が従います．
次に第2項が$negl$であることを示します．
補題2
$\Pr[CMA_{\Omega', F} = 1 \wedge \neg coll_{\Omega', F}] \leq negl(n)$
証明
$F$を用いて，もともとの固定長メッセージ署名方式$\Omega$に対する攻撃者$A$を構成します．
- 攻撃者$A(vk)$：
- $k \leftarrow \{0, 1\}^n$
- $vk' := (vk, k)$を入力として，$F(vk')$を起動します：
- $F$が署名オラクルへ$m_i$を問い合わせたとき，$A$は次を行います．
- $A$のアクセスできる（$\Omega$についての）署名オラクルへ，$H_k(m_i)$を問い合わせ，$\sigma_i \leftarrow \Omega.Sign(sk, H_k(m_i))$を$F$へ返す．
- $F$が署名オラクルへ$m_i$を問い合わせたとき，$A$は次を行います．
- $F$が偽造ペア$(m, \sigma)$を出力して停止したとき，$A$は次を行います．
- $(H_k(m), \sigma)$を出力して，停止します．
この$A$の偽造成功確率（試行$CMA_{\Omega, A}$が$1$となる確率）を考えます．
$\Pr[CMA_{\Omega, A} = 1] = \Pr[\forall i, H_k(m) \neq H_k(m_i) \wedge \Omega.Verify(H_k(m), \sigma, vk) = 1]$
となります（$A$は偽造ペアのメッセージとして，$H_k(m)$を出力していることに注意）．
さて，ここで任意長メッセージ署名$\Omega'$の（検証アルゴリズムの）構成より，
$\Omega'.Verify'(m, \sigma, vk') = \Omega.Verify(H_k(m), \sigma, vk)$
でした．また，$\forall i, H_k(m) \neq H_k(m_i)$であるとは，事象$coll_{\Omega', F}$の余事象に他なりません．
よって，上記の確率$\Pr[CMA_{\Omega, A} = 1]$は，
\begin{align}
\Pr[CMA_{\Omega, A} = 1] &= \Pr[\forall i, H_k(m) \neq H_k(m_i) \wedge \Omega.Verify(H_k(m), \sigma, vk) = 1] \\
&= \Pr[\neg coll_{\Omega', F} \wedge \Omega'.Verify'(m, \sigma, vk') = 1] \\
&= \Pr[\neg coll_{\Omega', F} \wedge CMA_{\Omega', F} = 1]
\end{align}
ここで，左辺は固定長メッセージ署名方式$\Omega$のEUF-CMA安全性より$negl(n)$です．
よって，$\Pr[CMA_{\Omega', F} = 1 \wedge \neg coll_{\Omega', F}] \leq negl(n)$が従います．
補題1と補題2を合わせて，$\Pr[CMA_{\Omega', F} = 1] \leq negl(n)$が示されました．
すなわち，任意長メッセージ署名$\Omega'$はEUF-CMA安全な署名方式です．
まとめ
本稿では，衝突困難性をもつハッシュ関数とEUF-CMA安全な（固定長メッセージ）署名方式を用いて，Hash-and-Signによって構成された任意長メッセージ署名方式がEUF-CMA安全であることの証明を紹介しました．
この証明では，プロトコルの具体的な構成に一切ふれることなく，その仕様と安全性のみから新たなプロトコルの構成法およびその構成の安全性を示しています．
このような一般的なプロトコル構成の議論は暗号学の重要な側面であり，一般的なプロトコル変換の手法を具体的な方式に落とし込むことで，別の具体的なプロトコルを（安全性を保障しつつ）構成するということも度々行われます（藤崎・岡本変換やFiat-Shamir変換などが好例と言えます）．
本稿で紹介したHash-and-Signは，そのような一般的なプロトコル変換とその安全性帰着の良い例の1つです．
参考文献
暗号理論教室 デジタル署名：https://w.atwiki.jp/cryptospace/pages/26.html#id_ca3e4278
I240 暗号理論 2019 公開鍵暗号と署名（１）：https://www.jaist.ac.jp/~fujisaki/2019/I240-2019-9.pdf
デジタル署名の証明可能安全性：https://www.ieice.org/~isec/event/isec050517/isec05051703.pdf