Security of Signature Schemes in the Multi-User Setting

Question

I've often read about the security of a signature scheme in the multi-user setting Link1 Link2, but I couldn't find a real definition. I would like to be sure that I understand it correctly. So my question is: If we consider Def 1, would Def 2 make sense for the multi-user setting?

Def 1: The signature scheme yields k-bits of security in the single-user setting if the probability that an attacker can forge a signature is at most $t/2^k$ and this holds for $t \leq 2^k$.

Def 2: The signature scheme yields k-bits of security in the multi-user setting if the probability that an attacker who is given N public keys can forge a signature for any of the N public keys is at most $t/2^k$ and this holds for $t \leq 2^k$.

Answer 1

Reduction from multi-user to single-user

First, please notice that there is a reduction between the multi-user security and the standard single-user security for signature scheme: it was proven in 2002 by Galbraith, Malone-Lee, and Smart (GSM) that for any signature system, attacking the scheme in the multi-user setting with $N$ public-keys cannot increase the attacker's success ratio (which is the quotient of its success probability and its running time) by a factor more than $N$ compared to attacking the scheme in the single-user setting.

This is a strong result, using your notation it roughly means that in the MU setting your bound is bounded by $\frac{Nt}{2^k}$ is you have $\frac{t}{2^k}$ in the SU setting. BUT we do not know any practical attack that achieve such a bound for signature schemes. Notice that if it were the case, if we had a large N such as 2^32 for example, the impact on the security of the signature schemes would be huge!

We typically prefer tighter reductions.

---

Notice that attacks against signature schemes in a multi-user setting are not to be mixed with attacks against MACs in that setting, which are not necessarily as good as signature schemes as discussed in the excellent "Another look at Tightness" paper by Chatterjee, Menezes and Sarkar and its sequel "Another look at Tightness II". Both are excellent reads on these kind of issues.

---

I recommend you to also read the "Security of Signature Schemes in a Multi-User Setting" by Menezes and Smart from 2004, as it is concerned with security definitions in the MU setting for signature schemes:

we argue that the well-accepted security definition for signature schemes (existential unforgeability against adaptive chosen-message attacks) by Goldwasser et al. [18] is not adequate for the multi-user setting. Fortunately, it appears that this definition can easily be extended to account for these attacks in the multi-user setting.

They also are concerned with the so-called "Key Substitution Attacks" which are covered by their definitions.

Most notably (emphasis mine):

In Section 2.2, we argued that an adversary of a signature scheme in the multi-user setting is successful if it produces an existential forgery or a key substitution. In either case, the attack is against one particular public key. Therefore, it suffices to consider the multi-user setting in which there is initially only one public key. This is without loss of generality because the adversary attacking one entity can simulate the other entities by picking their public keys so that it knows the corresponding private keys.

Obviously also, an adversary in the single-user setting naturally reduces to one in the multi-user setting.

And they conclude also that there is no real need to be worried about the multi-user setting for signature schemes as soon as we can bind them to a public key and have a very interesting result:

Signature schemes that are secure in the single-user setting can easily be transformed into schemes that are secure under our new definition in the multi-user setting by hashing the public key together with the message when computing the message digest

N.B: this notably explains why we are adding the public key to the message digest in the "Schnorr-like" signature scheme "EdDSA". (Actually it could also be because DJB found a flaw in the reduction from the single-user setting to the multi-user setting that had been given by GSM in 2002, but meanwhile we have another proof that shows it to be unnecessary for Schnorr signatures... But DJB dogfooded when he created EdDSA, I guess ;))

The multi-user attack model for signature schemes

Also, please notice that the attack model for forgeries in the multi-user setting is that the adversary is given $n$ signing oracles, one for each public key, and is allowed to make at most $q$ queries to these oracles. At the end of the attack, the adversary must output (with probability at most $\epsilon$) a tuple containing:

• one of the $n$ public keys, $y$
• a message $m$
• a signature $\sigma$, such that the signature $\sigma$ is valid for the message $m$ under the public key $y$. Where $m$ should not have been a query to the signing oracle corresponding to that key $y$.

The security of such a scheme is then defined depending on $q$, $n$. This is known as the "multi-user unforgeability against chosen message attacks" (MU-UF-CMA) model.

On the meaning of security for signature schemes

Also, before "defining" security for signature scheme in any setting, we need to know "what kind of security" we are trying to achieve. It is nice to say that "the signature scheme yields k-bits of security in the single-user setting", but against what kind of attacks? On that topic, the seminal paper by Goldwasser, Micali and Rivest is a good read, although a bit dated and a bit lacking on the multi-user setting for sure.

The most common notion of security for signature scheme is called "EUF-CMA" which means "existential unforgeability under adaptive chosen-message attacks", that is that it should be difficult for an adversary to come up with a "forged" message for a given public key. (There's also a notion of SUF-CMA "Strong Existential Unforgeability under Chosen Message Attack", which is trying to reduce the malleability of signature schemes)

But in a multi-user setting, there is another notion that is interesting, namely that of "Key Substitution Attacks" (KSA), where we can generate a new public key that would also verify a given (message, signature) pair. And there are key substitution attacks in provably secure EUF-CMA signature schemes! (E.g. in NTRUSign or in the "Short signatures without random oracles" scheme) What's really interesting with KSA, is that a malicious signer can also be an actor in such a setting!

On the k-bits of security

Finally, "having k-bits of security" is really against some attack model (but which one?) and is actually a way for us to compare public key cryptography with symmetric key crypto/bruteforce attacks. It's a way we use to have a metric allowing us to compare them, but it's sometimes quite difficult to evaluate in absolute terms. There are papers such as the ones on https://www.keylength.com/ that allow you to see the different ways we have to "estimate" the security of asymmetric crypto when compared to that of symmetric crypto, and as you can see there, the values are changing from one paper to the other.

In the end what we are trying to evaluate with the k-bit metric is the difficulty of breaking some scheme when compared to a bruteforce attack. (I recommend you to read this essay by DJB on bruteforce attacks.) But that's using the best known attacks against these public key schemes, and so it is not absolute, it's a relative measure.

Your definition, using $t/2^k$ is roughly that of a bruteforce attack: number of attempts divided by the "max number".

So, what you are saying is basically that we define "having k-bits of security" as being "as difficult as a bruteforce attack on a k-bit key", which I fully agree with. We do.

But a typical "proper definition of security" for public key signature schemes won't rely on that notion of "bits of security". It still has the notion of security parameter $k$ and it's still using a value $\mathbb{1}^k$ as input usually, but it is used as a way to limit the adversary to do less than a plain bruteforce attack and thus is also an input to the adversary, but it would be defined using some attack-model such as above.

This is why I discussed the "attack model" previously and cannot really give you a better definition than "Yeah, sure: bruteforce should ideally be the same difficulty as in the single-user setting for forgeries in the multi-user one".

But since we don't have "as tight" of a general reduction than that, we cannot say for sure whether it is actually the case or not in general. But it sure is the case for Schnorr-signatures as per both above linked papers.

Notice that fgrieu's answer is hinting at that notion of tightness too, but from the reverse point of view.

Answer 2

I'll assume $t$ is the number of "operations" (like group operations) an adversary makes; and the number of such operations legitimate users must make to sign and verify is small (like few times $k$; or at the very most polynomial in $k$).

The question's Def 2 is for security for $N$ users. For true security in the multi-user setting, we'd need to define $N$ from $k$, but I can quote no source for how. I'd replace $N$ by $2^{\alpha k}$ for some sensible $\alpha>0$. The practitioner is typically satisfied with $\alpha=1/4$ (yielding $N=2^{32}$ for $k=128$ ), the theoretician may want to bump that to $\alpha=1$.