この記事は，論文のうち，必要な部分を抜粋し和訳したものです。

The Winternitz One-Time Signature Scheme

このセクションではW-OTS\(^+\)について書きます。W-OTSのコアとなるアイデアは，ランダムな入力から始まる特定の数の関数の連鎖を使用することです。これらのランダムな入力は秘密鍵です。公開鍵は連鎖の最終の出力，つまり，連鎖の最後から構成されます。署名は，メッセージを各関数チェーンの一つの中間地にマッピングすることにより計算されます。以前のW-OTSのすべての変種は，単に使用される関数を反復した関数の連鎖（[BDE+11]の場合は関数族）によって構築されています。それとは対照的に，W-OTS\(^+\)では，使用されているハッシュ関数族に衝突耐性を要求することなく厳密なセキュリティ証明を可能にする，特別な反復モードを使用しています。いくつかの準備から始めます。そのあとW-OTS\(^+\)について話します。

Signature Scheme

ここで，いくつかの表記法を固め，適応型選択メッセージ攻撃のもとでデジタル署名方式と存在的偽造不可能性を定義します(EU-CMA)。 この論文では，\(x\)が一様分布を用いて集合\(\mathcal{X}\)からランダムに選択されるとき，\(x \overset{\$}{\gets} \mathcal{X}\)と書く。さらに log は \(\text{log}_2\)とします。

Digital Signature schmes.\(\,\,\,\,\,\) \(\mathcal{M}\)をメッセージ空間とします。デジタル署名方式Dss=(Kg, Sign, Vf)は，確率的多項式アルゴリズムの3つです。

• Kg(1\(^n\)) セキュリティパラメータ\(1^n\)が入力されると，秘密署名鍵skと公開検証鍵pkを出力する。

• Sign(sk, \(M\)) \(M \in \mathcal{M}\)ならば，\(M\)に対してskの下で署名\(\sigma\)を出力する。

• Vf(pk, \(\sigma\), \(M\)) \(\sigma\)がpkの下で\(M\)の有効な署名ならば1を出力する。

次のようになります。 \(\forall\) (pk, sk) \(\gets\) Kg(1\(^n\)) \(\,\,\),\(\,\,\) \(\forall\) (\(M\in \mathcal{M}\)) \(\,\,\):\(\,\,\) Vf(pk，Sign(sk,\(M\)),\(M\))=1。

EU-CMA Security.\(\,\,\,\,\,\) デジタル署名方式の標準的なセキュリティの考え方は，適応型選択メッセージ攻撃（EU-CMA）の下での存在的偽造不可能性（EU-CMA）であり，以下の思考実験を使用して定義されます。DSS(1\(^n\))とは，セキュリティパラメータ\(n\)を持つ署名方式を意味します。

Experiment.\(\,\,\,\,\,\) \(\text{Exp}^{\text{EU-CMA}}_{\text{Dss}(1^n)}(\mathcal{A})\)
　　　(sk,pk) \(\,\,\gets\,\,\) Kg(1\(^n\))
　　　(\(M\), \(\sigma\)) \(\,\,\gets\,\,\) \(\mathcal{A}^{\text{Sign(sk,}\cdot)} (\textbf{pk})\)
　　　\(\{(M_i,\sigma_i) \}^q_1\)を(,\(\cdot\))の問い合わせ／回答ペアとする
　　　(,\(M*\),\(\sigma\)*)=1かつ\(M^{*} \notin \{M_i\}^q_1\)ならば1を返す

上記の思考実験における攻撃者\(\mathcal{A}\)の成功確率については，次のように書きます。 \[ \text{Succ}^{\text{EU-CMA}}_{\text{Dss}(1^n)}(\mathcal{A}) = \text{Pr} \left[\textbf{Exp}^{\text{EU-CMA}}_{\text{Dss}(1^n)}(\mathcal{A})=1 \right] \] これを使用して，次のようにEU-CMAを定義します。

Definition 1 (EU-CMA).\(\,\,\,\,\,\) \(n,t,p \in \mathbb{N}\)，\(q=\text{poly}(n)\)，Dssをデジタル署名方式とする。 DssがEU-CMA安全とは，上記思考実験でSignへ\(q\)個の問い合わせをして，時間\(t\)以内に， 考えられるすべての攻撃者\(\mathcal{A}\)のうち，最大の成功確率\(\textbf{InSec}^{\text{EU-CMA}}(\text{Dss}(1^n);t,q)\)が\(n\)において無視できるとすると， \[ \text{InSec}^{\text{EU-CMA}}(\text{DSS}(1^n);t,q) \overset{def}{=} \underset{\mathcal{A}}{\text{max}} \{ \text{Succ}^{\text{EU-CMA}}_{\text{Dss}(1^n)}(\mathcal{A}) \} = negl(n) \] EU-CMA安全なワンタイム署名方式（OTS）は， 攻撃者のオラクルへの問い合わせの数が1に制限されている限り，すなわち\(q=1\)である限りEU-CMA安全なDssです。

W-OTS+

さてW-OTS\(^+\)について紹介します。以前のすべてのW-OTSの変種と同じように， W-OTS\(^+\)はセキュリティパラメータ\(n\in\mathbb{N}\)，メッセージ長\(m\)，そして時間とメモリのトレードオフを決定するWinternitzパラメータ\(w \in \mathbb{N}, w > 1\)によってパラメタライズされます。最後の2個のパラメータは次のものを計算するのに使用されます。 \[ l_1 = \left\lceil \frac{m}{\text{log}(w)} \right\rceil, \,\,\, l_2 = \left\lfloor \frac{\text{log}(l_1(w-1))}{\text{log}(w)} \right\rfloor + 1, \,\,\, l = l_1 + l_2 \] さらに，W-OTS\(^+\)は鍵空間\(\mathcal{K}_n\)で関数の族\(\mathcal{F}_n\,\,\{f_k:\{0,1\}^n \to \{0,1\}^n| k\in \mathbb{K}_n \}\)を使用します。読者は，圧縮無しの暗号学的なハッシュ関数だと考えてもらって大丈夫です。 \(\mathcal{F}_n\)を使って，次の連鎖関数を定義します。

\(c^i_k(x,\textbf{r})\)：入力値\(x\in \{0,1\}^n\)，イテレーションカウンタ\(i\in \mathbb{N}\)，鍵\(k\in \mathcal{K}\)，ランダム化要素\(\textbf{r}=(r_1,...,r_j)\in \{0,1 \}^{n\times j}(j\geq i)\)とすると， 連鎖関数は次のように働きます。\(i=0\)のとき，\(c\)は\(x\)を返します(\(c^0_k(x,\textbf{r})=x\))。\(i>0\)のとき，再帰的に定義します。 \[ c^i_k(x,\textbf{r}) = f_k(c^{i-1}_k(x,\textbf{r})\oplus r_i) \] つまり，各ラウンドで，関数は最初に中間値とビットマスク\(r\)のビットごとのXORをとり， その結果に対して\(f_k\)を評価します。の部分集合\(r_a,...,r_b\)として，\(\textbf{r}_a,b\)を書きます。\(b<a\)の場合\(\textbf{r}_{a,b}\)をからの文字列と定義します。パラメータ\(m\)，\(w\)，そして関数の族\(\mathcal{F}_n\)は既知であると仮定します。さて，W-OTS\(^+\)の三つのアルゴリズムについて記載します：

- \(\textit{鍵生成アルゴリズム}\,\,\,\,\,\) (Kg(\(1^n\)))：
単項のセキュリティパラメータ\(n\)を入力として，鍵生成アルゴリズムは\(l+w-1\)個の\(n\)ビットの文字列をランダムに一様に選択します。秘密鍵\(\textbf{sk}=(\text{sk}_1,...,\text{sk}_l)\)は，最初の\(l\)個のランダムなビット列から構成されています。残りの\(w-1\)個のビット列は，\(c\)のためのランダム化要素\(\textbf{r}=(r_1,...,r_{w-1})\)として使用されます。次に，\(\text{Kg}\)はランダムに一様にファンクションキー\(k \overset{\$}{\gets} \mathcal{K}\)を選択します。公開検証鍵\(\textbf{pk}\)は次のように計算されます。 \[ \text{pk} = (\text{pk}_0,\text{pk}_1,...,\text{pk}_l) = ( (\textbf{r},k), c^{w-1}_k (\text{sk}_1,\textbf{r}) , \cdots,c^{w-1}_k (\text{sk}_l,\textbf{r}) ). \]

- \(\textit{署名アルゴリズム}\,\,\,\,\,\) (Sign(\(M\),sk,))：
\(m\)ビットのメッセージ\(M\)，秘密署名鍵\(\textbf{sk}\)およびランダム化要素\(\textbf{r}\)を入力として，署名アルゴリズムはまず，\(M\)の\(w\)基底表現を計算します：\(M=(M_1...M_{l_1}) \,\,,\,\, M_i \in \{0,...,w-1 \}\)。したがって，\(M\)は自然数\(x\)のバイナリ表現として扱われ，次に\(x\)の\(w\)変数表現が計算されます。
次にチェックサムを以下のように計算します。 \[ C = \sum^{l_1}_{i=1}(w-1-M_i) \] そして，その\(w\)基底表現\(C=(C_1,...,C_{l_2})\)を計算します。\(C \leq l_1(w-1)\)より，\(C\)の\(w\)基底表現は，たかだか\(l_2\)です。 \(M\)と\(C\)の\(w\)基底表現の連結である\(B=(b_1,...,b_l)=M\,\,||\,\,C\)を設定します。 署名は次のように計算されます。 \[ \sigma = (\sigma_1,...,\sigma_l) = (c^{b_1}_k(\text{sk}_1,\textbf{r}),...,c^{b_l}_k(\text{sk}_l,\textbf{r})). \] チェックサムは，ある一つのメッセージに対応した\(b_i,0 < i \leq l\)が与えられたとき， 任意の他のメッセージに対応する\(b'_{i} < b_i\)が少なくとも一つあることを保証することに留意してください。

- \(\textit{検証アルゴリズム}\,\,\,\,\,\) (Vf(\(1^n\),\(M\),\(\sigma\),))：
バイナリ長\(m\)のメッセージ\(M\)，署名\(\sigma\)，そして公開検証鍵\(\textbf{pk}\)を入力として， 検証アルゴリズムは，上述したようにまず\(b_i,1\leq i \leq l\)を計算します。 それから以下のように比較されます。 \[\begin{align} \textbf{pk} & = (\textbf{pk}_0,\textbf{pk}_1,...,\textbf{pk}_l) \nonumber \\ & \overset{?}{=} ( (\textbf{r},k), c^{w-1-b_1}_k(\sigma_1, \textbf{r}_{b_1 + 1,w-1}),...,c^{w-1-b_l}_k(\sigma_l, \textbf{r}_{b_l + 1,w-1}) ) \nonumber \end{align}\]

比較が成立する場合はtrueを返し，そうでない場合はfalseを返します。
3つのアルゴリズムすべての実行時間は，\(f_k\)の\(lw\)個の評価によって決まります。 署名と秘密鍵のサイズは，\(|\sigma|=|\textbf{sk}|=ln\)ビットです。 公開鍵のサイズは\((l+w-1)n+|k|\)ビットで，ここで\(|k|\)は\(\mathcal{K}\)の任意の要素を表すために必要なビット数です。

参考文献

• W-OTS+ — Shorter Signatures for Hash-Based Signature Schemes
• [BDE$^+$11]:
  Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hulsing, and Markus Ruckert. On the security of the Winternitz one-time signature scheme. In A. Nitaj and D. Pointcheval, editors, Africacrypt 2011, volume 6737 of Lecture Notes in Computer Science, pages 363-378. Springer Berlin / Heidelberg, 2011.