2
$\begingroup$

From one-time hash-based signature, one can convert it into 2^d time signature by using Merkle hash tree.

However, it seems to be a trick that enables multi-time signing.

My question is: is there any use case for a signature scheme that can only be used to sign for a fixed number of time (punch/redeem card)?

$\endgroup$
2
  • $\begingroup$ The title asks one question (why would we use a signature method that is limited to signing $d$ messages); the body asks another (how could we use a signature method that is limited to a certain amount of time). Which do you really mean to ask? $\endgroup$
    – poncho
    Mar 7, 2022 at 3:51
  • $\begingroup$ I fixed the title a bit $\endgroup$ Mar 7, 2022 at 6:04

3 Answers 3

2
$\begingroup$

My question is: is there any use case for a signature scheme that can only be used to sign for a fixed number of time (punch/redeem card)?

Given our druthers, we would prefer a signature scheme that can be used an arbitrary number of times; the limits on existing schemes are of the form "if you go above this limit, you reduce (or eliminate) the security properties you get" - we have no particular reason to prefer that.

However, we put up with limits (and in the case of stateful hash based schemes, comparatively small limits) because:

  • Those schemes may have other properties that we would like. In the case of hash based schemes, we get the property of cryptographical security - the security of the schemes rest on the cryptographical strength of the hash function and nothing else. Any signature system which first hashes the message and then works with the hash must assume the cryptographical strength of the hash function - a hash based scheme makes no other assumption.

  • Sometimes the user knows a reasonably small limit on the number of signatures he will generate. For example, if the user knows that the private key will reside on a single signer, that signer cannot possibly generate more than 1000 signatures per second, and that after one year ($< 2^{25}$ seconds) he will discard the private key (and generate a fresh one), then he knows that he cannot ever sign more than $2^{35}$ messages with the same public key - hence, a stateful hash based scheme with a limit of $2^{35}$ messages would be a possible option.

$\endgroup$
1
$\begingroup$

Every signature scheme can safely sign without limitation. In some, a given private key can only safely sign a more or less severely limited number of times.

Such limitation is not enforced by something mathematical in the scheme: the holder of the private key material could apply what they did to the first signed message to any number of other messages, at the price of making the scheme insecure. If the signing limitation is enforced, that's by the signing device/software which changes state at each signature. Such limitation can be added to a signing device independently of the signature schme, and that's common, e.g. to limit the consequences of a theft of the signing device.

There are many use cases where we can live with what amounts to a limitation: often, the number of signatures a given private key needs to make can be bounded up, or when a key can be replaced with a fresh one when approaching some usage threshold. For example, the signing key for legal documents in a small company might be used less than 100 times in it's (e.g. two years) lifespan.

Limitations can even be turned into a marketing advantage: certificate issuance companies might love an excuse to be able to sell different certificate grades according to key usage.

$\endgroup$
0
$\begingroup$

Arguably, all extant signature schemes can only be used a finite number of times. For example, using the Ed25519 more than $2^{126}$ times with the same signing key runs a high risk of repeating an ephemeral key and compromising the signing key (using it $\ell+1$ times guarantees it).

Likewise in practice the signatures used in X.509 certificates which are ubiquitous on the Internet come with a expiry after which they should no longer be used.

With hash tree based signatures such as SPHINCS, the usage limitations are a bit more severe and more likely to impinge on typical usage. For high use signature schemes, this would involve more key rotation/refreshment. It is however perfectly possible for the last use of limited used signature scheme to sign and endorse a new verification key rather than update long term signature stores. There is the added over head of potentially having to validate a string of such signatures to get to the current verification key, but it's still potential use case.

$\endgroup$
2
  • 1
    $\begingroup$ I don't immediately see how an (accidental and highly unlikely) collision in ephemeral keys/nonces among say $2^{64}$ Ed25519 signatures with the same private key could be identified (a prerequisite to being exploited, it seems), much less among $2^{126}$ where that becomes a real possibility. $\endgroup$
    – fgrieu
    Mar 7, 2022 at 8:30
  • $\begingroup$ I agree that this is finite in the sense of not infinite rather than not infeasible, but provided that one believes that there is not a hard limit on computational resources over time, it still argues for a finite lifetime for signing keys for extant signing algorithms. $\endgroup$
    – Daniel S
    Mar 7, 2022 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.