同一の公開鍵，秘密鍵から1つ以上の署名をするにはどうすればいいでしょうか。

この記事では，ハッシュベース署名方式がどのように構築されるか確認するのが最終目標です。

One-time Signatures(OTS)だけでなくFew-times signatures(FTS)でも可能です。

HORS

HORSは，2002年にReyzin親子によって発表されたBiba(Bins and Balls)を更新したものから作られています。

まず初めに，OTSのように一方向性関数に基づいて秘密鍵となる整数のリストを生成します。そしてそのあとそれぞれについてハッシングし，公開鍵を生成します。

ただし，署名するとき，メッセージ\(m\)に対応したインデックスのリストを与えるための選択関数\(S\)が必要となります。

次の例では，パラメータ\(t=5\)，\(k=2\)として進めます。 このとき，メッセージ\(m\)の小数値が10より小さくなるように署名できます。 また，（選択関数\(S\)は2つのインデックスを出力するので）秘密鍵の長さは5であり，署名の長さは2となります。

良い関数（全単射関数）\(S\)を使用すると，秘密鍵から生成される同一の要素で二つのメッセージに署名することは不可能です。しかし，その2つの署名のあとは，新しいものを偽造するのはかなり簡単なはずです。2個目に構築するのはHORS署名方式と呼ばれるものです。これは，一方向性関数の代わりに"サブセット・レジリエント"関数に基づいています。選択関数\(S\)は，\(H(m_2) \subseteq H(m_1)\)となるような2つのメッセージ\(m_1\)，\(m_2\)を見つけることが不可能である関数\(H\)に置き換えることができます。

それよりも，複数回署名可能な方式にしたい場合，署名者が\(r\)個の署名を与えたとき，\(H(m') \subseteq H(m_1) \cup \cdots \cup H(m_r)\)となるメッセージ\(m'\)を見つけることは不可能であるべきです。これが，実際には"サブセット・レジリエント"の定義となります。

選択関数\(H\)は，攻撃者が多項式時間で，前の式を確認できる\(r+1\)個のメッセージの集合を（たとえ小さな確率であっても）見つけられない場合，r-サブセット・レジリエントです。 定義に関する部分をそのまま引用します。

Let \(\mathcal{H}=\{H_{i,t,k} \}\) be a family of functions, where \(\{H_{i,t,k} \}\) maps an input of arbitrary length to a subset of size at most \(k\) of the set \(\{0,1,\cdots,t-1 \}\).(Note that for each \(t\) and \(k\), contains a number of fuctions, which are indexed by \(i\)). Moreover, assume that there is a polynomial-time algorithm that, given \(i, 1^t,1^k\) and \(M\), compute \(H_{i,t,k}(M)\).

Definition 1. We say that \(\mathcal{H}\) is \(\it{r-subset-resilient}\) if, for every probablistic polynominal-time adversary A,
\[ \underset{i}{\text{Pr}} [ (M_1,M_2,...,M_{r+1}) \gets A(i,1^t,1^k) \\ \text{s.t.} \,\, H_{i,t,k}(M_{r+1})\subseteq \underset{j=1}{\overset{r}{\cup}} H_{i,t,k}(M_j) ] < negl(t,k). \] Fix a distribution \(D\) on the space of all inputs to \(H\) (i.e., on the space of messages).

しかし，ここでは選択関数は全単射ではないので，元に戻すのは難しいのです。 したがってメッセージの一つ前の署名を知っていても，どのメッセージがそれらのインデックスを使用するのかわかりません。

これは，理論上はランダムなオラクルを使用して，実際にはハッシュ関数を使用して行われます。これが，HORS(=Hash to Obtain Random Subset)と呼ばれる所以です。

他にも選択関数はあります。 メッセージ\(m\)を署名するために，次の手順をふみます。

  1. \(h=Hash(m)\)
  2. \(h\)を\(h_1,...,h_k\)に分割する
  3. それぞれの\(h_j\)を整数\(i_j\)と解釈する
  4. 署名は\(sk_{i_1},...,sk_{i_k}\)となる