Digital Signature Scheme Count

Question

My question is How I will be able to count digital signature Scheme that can sign many documents with one private key. There are signature scheme as long as exists private keys in the keys spaces? or There are signature scheme as long as exists methods than RSA, DSA, ECDSA, Hash-Based signature schemes, etc? I am doing this question because I want understand

this paragraph of my lecture

Hash-based digital signature schemes which are presented in this chapter offer a very interesting alternative. Like any other digital signature scheme, hash-based digital signature schemes use a cryptographic hash function. Their security relies on the collision resistance of that hash function. In fact, we will present hash-based digital signature schemes that are secure if and only if the underlying hash function is collision resistant. The existence of collision resistant hash functions can be viewed as a minimum requirement for the existence of a digital signature scheme that can sign many documents with one private key. That signature scheme maps documents (arbitrarily long bit strings) to digital signatures (bit strings of fixed length). This shows that digital signature algorithms are in fact hash functions. Those hash functions must be collision resistant: if it were possible to construct two documents with the same digital signature, the signature scheme could no longer be considered secure. This argument shows that there exist hash-based digital signature schemes as long as there exists any digital signature scheme that can sign multiple documents using one private key

Answer 1

I suppose this is a terminology question. "A digital signature scheme which can sign many documents with one private key" means something like this:

• There are some sets $M$ (the "message space", often the set of bitstrings of any length, or some useful subset thereof), $K_{pub}$, $K_{priv}$ (the public and private "key spaces") and $S$ (the signature space).
• There is a tuple of (probabilistic and efficiently computable) functions $(g, s, v)$.
• $g : \varnothing \to K_{pub} \times K_{priv}$ ($g$ generates a random key pair).
• $s : M \times K_{priv} \to S$ ($s$ signs a message, i.e. generates a signature from the private key and message)
• $v : M \times K_{pub} \times S \to \{\mathsf{true}, \mathsf{false}\}$ ($v$ verifies a signature)
• If $(y, x) = g()$ and $m \in M$, then $v(m, y, s(m, x)) = \mathsf{true}$ (or at least with overwhelming probability).

Normally we also want that the scheme is secure, which then adds some more properties:

• Given $y$ (the public key) and a message $m$, without knowledge of $x$ it is hard to create a $\sigma \in S$ such that $v(m, y, \sigma) = \mathsf{true}$, even if some (or even many) other $(m', \sigma')$ are known, or even signatures to other messages can be requested. (This is known as "universal forgery".)

• It should even be hard to create any message $m \in M$ and $\sigma \in S$ such that $v(m, y, \sigma) = \mathsf{true}$ (other than the $m'$s which were given/queried as examples). (This is known as "existential forgery".)

(There are also variants of this definition where the number of documents which can be signed with each key before the security gets lost is limited, but these obviously are not "signature schemes which can sign many documents with one key".)

Usually there also is some formalization of "hard", often with a security parameter.

---

Similarly, we have the term of "hash function", something like that:

• There is a message space $M$ (usually the set of bitstrings of any length, or some useful subset thereof) and a hash space $H$ (usually the set of bitstrings of some fixed length).
• There is a function $h : M \to H$.

The "collision resistance" property then is something like

• It is hard to find $m_1, m_2 \in M$ with $h(m_1) = h(m_2)$.

---

The "there exists a digital signature scheme which ..." in the quoted lecture extract supposedly means as much as "there exists a secure signature scheme which ...".

We already know that there are signature schemes (RSA, DSA, ECDSA, ...), but it is not proven if they are actually secure. (We sure hope so, and nobody did break them publicly yet, but it might not actually be possible to prove anything, or it might be that there is no secure signature scheme at all.)

We also don't know if there exist any actually collision-resistant hash function. We have some candidates (like SHA-2), and some previous candidates which proved to actually be not collision resistant (MD4, MD5).

---

The argument then is:

• If there is any secure signature scheme (for multiple documents with each key), then there has to be a collision-resistant hash function.

  (The idea is that you actually can use the signature scheme as a hash function by using a fixed key, and the signature scheme is not secure if you can find two messages with the same signature (i.e. a hash collision). I think this doesn't actually follow from my security properties mentioned above, so maybe your lecture used some other security definition.)

• Also there will be shown (in the following paragraphs/pages of your text) that from any collision-resistant hash function you can build a secure hash-based signature scheme.

• So it follows: If there is any secure signature scheme (which can sign many messages) at all, then there is a secure hash based signature scheme.

Answer 2

Thanks by your reply, Your reply is equal than the author.

You are right, the sentence is a bit misleading, sorry for that. The point is the following. From a theoretical point of view, the minimal requirement for the existence of a digital signature scheme is the existence of any one-way function. However, if you take a praxis oriented point of view, the minimal requirement is the existence of an efficient collision resistant hash function. The reason is the handling of arbitrary length inputs: The core of a signature scheme is a signature scheme that signs messages of a fixed length. Then, a hash function is used to handle messages of arbitrary length. In theory, we can extend the input length of a digital signature scheme using so called "universal one-way hash functions" (UOWHF), also called target-collision resistant hash functions. Sadly, there exist no practical UOWHF for several reasons and therefor this does not work in practice. So, in practice we need a collision resistant hash function to allow for arbitrary length inputs. Hence, one could state that the minimal PRACTICAL requirement for the existence of an efficient signature scheme that can sign messages of arbitrary length is the existence of an efficient collision resistant hash function. This is independent of the numbers of message that can be signed using one key pair, i.e. this also holds for one-time signature schemes.