Lamport

1979年の10月18日にLeslie Lamportによってワンタイム署名のコンセプトが発表された。

ほとんどの署名スキームはそのセキュリティの証明に，部分的に一方向性関数，典型的なハッシュ関数に頼っています。ランポート署名の美しさは，この署名がこれらの一方向性関数のセキュリティにだけ頼っているところ。

公開鍵 $ h(x)|h(y)$
秘密鍵 $ (x,y) $

とても単純なスキームとして，\(x\)，\(y\)を整数とすると，単一のビットへの署名は，
- もし0なら，\(x\)を公開する
- もし1なら，\(y\)を公開する

それを2度と署名に使わないこと。 もし複数のビットに署名したい場合はどうすればいいか？ できることは，署名したいメッセージを固定長の出力となるようにハッシング することです。例えば，SHA-256など。

そのとき，256個の秘密鍵のペアが必要になって，次のようになる。

公開鍵 $ h(x_0)|h(x_0), h(x_1)|h(x_2),...,h(x_{255}) | h(y_{255})$
秘密鍵 $ (x_0,y_0),(x_1,y_1),...,(x_{255},y_{255}) $

そしてもし，\(100110_2....\)に署名したい場合は，\((y_0,x_1,x_2,y_3,y_4,x_5,...)\)というように公開する。

詳細は，Qiitaにも取り上げられているので，そちらに譲る。

Winternitz OTS (WOTS)

Lamportの発表から数か月あと，スタンフォードの数学学科のRobert Winternitzが，\(h(x)|h(y)\)の公開の代わりに\(h^w(x)\)を公開することを提案した。

例えば，\(w=16\)として\(h^{16}(x)\)を公開鍵として公開する場合，\(x\)は秘密鍵。次のバイナリ\(1101_2\)に署名したい場合，\(h^9(x)\)を公開すればいい。

問題は，悪意のある人間が\(h^{10}(x)\)を検索するために，この署名とハッシュを見られることで，それゆえ有効な署名を偽造しうること。

これはメッセージの後ろに短いチェックサム（同様に署名する必要がある）を追加することで回避可能。

Variant of Winternitz OTS

長い長い年月のあと，2011年に，Buchmann et alがWinternitz OTSのアップデートを公開して，鍵でパラメータ化された族を利用して新しいWOTSの変種を紹介した。MACと呼ばれている。

MACで使用される鍵のリストが秘密鍵で，メッセージは何度MACを反復するかを指定することになる。以前の出力が鍵を置き換えるため固有の反復であり，常に同じ公開された入力を使用する。

メッセージ\(M=1011_2\)があり，WOTSの変種が3を基底とするメッセージとして動作するとする（実際には任意の基底\(w\)でも大丈夫）。\(M=(M_0,M_1,M_2)=(1,0,2)\)は\(102_3\)を表すとする。

これを署名するには，\((f^1_{sk_1}(x)=f_{sk_1}(x),\, f^0_{sk_2}(x)=sk_2 ,\, f^2_{sk_3}(x)=f_{\{f^1_{sk_3(x)}\}}(x) )\)を公開すればいい。

まだメッセージに署名が必要なチェックサムが適用されるが，詳細割愛。 チェックサムにより，公開鍵の中で\(M_2=2\)と知られていても関係がない。

直感的に，連鎖していくことで公開鍵により良いセキュリティを提供することになる。

Winternitz OTS+(WOTS+)

変種の発表の2年後，Hulsingだけで，署名サイズを短くし，以前のスキームのセキュリティを向上させるアップグレード版を公開した。これは，鍵付き関数族に加えて，連鎖関数を使用する。今度は，鍵は常に同じで，それは一つ前の出力が入力となる。また，一方向性関数が適用される前にランダム値（またはマスク）がXORされる。

入力\(x \in \{0, 1\}^n\)，反復カウンタ\(i\in \mathbb{N}\)，ランダム要素\(\bf{r}\)\(=(r_1,...,r_j) \in \{0,1\}^{n\times j}(j\geq i)\)とすると，連鎖関数は次のように働く。
\(i=0\)のとき，連鎖関数\(c\)は\(x\)を返す\((c_k^0(x,\textbf{r})=x)\)。
\(i>0\)のとき，連鎖関数\(c\)は再帰的に次のようになる。 \[ c_k^i(x,\textbf{r}) = f_k(c_k^{i-1}(x,\textbf{r}) \oplus r_i) \] \(f_k\)について，鍵空間\({\cal K}_n\)とすると，関数族\({\cal F}_n:\{f_k : \{0,1\}^{n} \to \{0,1\}^{n} | \,\, k\in {\cal K}_n \}\)を満たす。
要は，圧縮なしの暗号学的なハッシュ関数。

その他のOTSについて

他にもいろいろ提案されている。
- 1994，The Bleichenbacher-Maurer OTS
- 2001，The BiBa OTS
- 2002，HORS
- 2014，HORST, SPHINCS

PQCRYPTO ICT-645622によると，耐量子として，公開鍵署名に推奨されているものは，XMSSとSPHINCS-256。
（XMSSはステートフル署名，SPHINCSはステートレス署名）