Summary first.

There has always been, and continues to be, a reasonable concern that
forging a message under 1 of N Schnorr keys could be significantly less
secure than the problem that (we hope!) has actually been thoroughly
studied, namely forging a message under a single targeted key. It's easy
to prove that the security loss is limited to a factor N, but this is
quantitatively unsatisfactory.

http://cr.yp.to/papers.html#multischnorr compares the key-prefixed
H(R,A,M) system to the traditional H(R,M) system and proves that

   probability of breaking any 1 of N signature keys using H(R,A,M)
   <= probability of breaking a targeted signature key using H(R,M)

which completely eliminates the issue for H(R,A,M). An old paper, by
Galbraith--Malone-Lee--Smart (GMLS), claimed to prove the same thing
_without_ inserting the key into the hash---

   probability of breaking any 1 of N signature keys using H(R,M)
   <= probability of breaking a targeted signature key using H(R,M)

---but the proof turned out to be wrong in a way that seems extremely
difficult to fix.

A new paper, by Kiltz--Masny--Pan (KMP), claims to have proven that "the
original GMLS theorem is correct". This claim is, unfortunately, not an
accurate characterization of what KMP actually proved; I expect KMP to
withdraw this claim. What the KMP paper actually proves (I'm assuming
that the new proof is correct---I haven't had a chance to check this
yet) is a new theorem that's

   * different from the GMLS claim, and
   * significantly weaker than the GMLS claim, with
   * no hope of obtaining the GMLS claim as a corollary.

The bottom line is the same as before: there's a reasonable concern
that breaking 1 of N Schnorr keys could be significantly less secure
than breaking a single targeted key. Inserting the key into the hash
eliminates this concern.

Now details, starting with background.

There's an old paper by Schnorr and Jakobsson showing that Schnorr
signatures provide security sqrt(group size) against generic attacks
(attacks that work for any group and any hash function):

   http://www.math.uni-frankfurt.de/~dmst/research/papers/schnorr.random_oracle_generic_model.1999.dvi

This 2^(b/2) is much stronger than the conclusion of the well-known
Pointcheval--Stern paper, the Neven--Smart--Warinschi paper, etc., and
the proof is conceptually simpler. The same technique should easily
generalize to multiple keys, superseding, e.g., the GMLS paper.

The only reason that the Schnorr--Jakobsson paper isn't the end of the
story is that there's a big difference between "generic attacks" and
"all attacks". There's a legitimate, and very frequently expressed,
concern about the possibility of a _non-generic_ attack breaking any
_specific_ standardized group and any _specific_ standardized hash
function.

This possibility is exactly why there are many papers criticizing proofs
in the generic-group "model" and the generic-hash "model" (typically
called the "random-oracle model"), and instead advertising proofs in the
"standard model". Consider, for example, the paper "Practical Chosen
Ciphertext Secure Encryption from Factoring" by Hofheinz and Kiltz,
which

   * won a best-paper award at Eurocrypt 2009;

   * works in the "standard model"---the same result _for generic-hash
     attacks_ had already been accomplished many years earlier by much
     simpler techniques; and

   * criticizes analysis of generic-hash attacks as follows: "We stress
     that although a proof in the random oracle model has a certain
     value it is still only a heuristic security argument for any
     implementation of the scheme."

Of course, there's lots of work on studying particular types of attacks
against particular choices of parameters: e.g., discrete-log attacks
against particular groups, or preimage attacks against particular hash
functions. But maybe someone can break the _signature_ scheme more
easily than breaking the problems that have actually been studied. As a
concrete example, the attack stated in my "Security concerns regarding
short hashes" message from July breaks narrow-pipe short-hash signatures
without breaking discrete logs and without breaking the traditional
single-target preimage problem.

With this background in mind, I'm puzzled to see Kiltz's message
glossing over

   * the difference between analyzing _all_ attacks and merely analyzing
     _generic_ attacks ("This is the original GMLS theorem, except that
     we make the random oracle requirement") and

   * the difference between assuming standard unforgeability and having
     to assume "strong" unforgeability.

If we don't care about differences in attack genericity, then why don't
we simply use the original Schnorr--Jakobsson theorem? If we don't care
about differences in attack targets, then why don't we simply analyze
discrete logs and preimage resistance?

The answer, of course, is that we _do_ care about these differences.
Having to assume "strong" unforgeability isn't as good as assuming
standard unforgeability---there could be huge differences in security
between these two attack targets. Studying all generic-hash attacks (=
"attacks in the random-oracle model") goes beyond studying generic-group
generic-hash attacks but isn't as good as studying _all_ attacks.

The new KMP paper makes the following claim in its introductory section:

   1.1 Our results

   Our main result states that the original GMLS theorem is correct,
   namely that single-user security of the Schnorr signatures scheme
   tightly implies multi-user security of the same scheme.

This claim is incorrect for a minor reason and a major reason. The minor
reason is that the original GMLS theorem actually claims something
quantitatively very strong, namely that there is _no_ loss of security
(theorem: "epsilon_n = epsilon_1"; subsequent summary: "security does
not decrease with the number of users"). Saying "tight" allows some
security loss, such as the factor 2+epsilon lost in the KMP theorem.

The major reason that the claim is incorrect is that the KMP theorem
assumes "strong" unforgeability, while the GMLS claim merely assumed
_standard_ unforgeability. Strong unforgeability

   * is much less studied than standard unforgeability and

   * could be much easier to break---as I said before, there's no limit
     on how much security this could lose.
     
Kiltz's response is that there's a tight limit _for generic attacks_,
but this is an even more restrictive hypothesis---there's no limit on
the security gap between generic attacks and all attacks.

Eike Kiltz writes:
> Our results are not stated entirely correctly, so let me clarify first.

If I've misstated something, my apologies; please pinpoint the error!

> Our results show that key-prefixing does not provide any advantage
> for multi-user security

Eike, if you're thinking "the advantage factor can't be more than about
2", why do you say that there isn't "any advantage"? This isn't terribly
important but it's sloppy.

More importantly, GMLS claimed a theorem about _all_ multi-key attacks
assuming _standard_ unforgeability for a single key. Key prefixing makes
this work. Your paper, by contrast, has to

   * assume "strong" unforgeability---not addressing the concern that
     this could be much easier to break than standard unforgeability---
     or

   * fall back to the random-oracle model---i.e., consider only
     generic-hash attacks, not addressing the concern that there could
     be much faster non-generic attacks.

So how can you claim that there's no advantage to the key-prefixing
theorem? That theorem completely _eliminates_ the concern regarding
multi-key attacks, while your theorem obviously doesn't accomplish this.

> As I understand the history of this thread, initially the group agreed
> that key-prefixing should be avoided for Schnorr

No; the group took very few actions, and this wasn't one of them. During
the discussion, a few people spoke up for avoiding key-prefixing, but
not many. It seems that very few people are in situations where

   * the signer doesn't care about knowing its own public key _and_
   * storing the 32-byte public key next to the secret signing key is a
     space problem _and_
   * recomputing the public key on demand is a speed problem,

so the performance argument for H(R,M) is quite flimsy, while there has
always been a _security_ argument for H(R,A,M).

The relevant series of events during the discussion started early in
September, when Struik---backed by the GMLS paper---claimed that H(R,M)
had the same security feature. The eventual conclusion, after some
investigation, was that

   * H(R,A,M) is now _proven_ to be (at least) as strong against
     multi-key attacks as H(R,M) is against single-key attacks, while

   * H(R,M) doesn't have any such proof---it's possible that multi-key
     attacks against H(R,M) are significantly easier than single-key
     attacks, contrary to the GMLS claim.

Your paper doesn't change either part of this conclusion.

It's hard to guess what effect the original claim would have had on the
final CFRG decision if the claim had lasted for more than two weeks. In
the "provable security" literature it's common to say that design
elements should be included if and only if those elements are
contributing to security proofs (as discussed in the last paragraph of
Section 1.2 of my multischnorr paper); on the other hand, for many good
reasons, real-world cryptography is actually guided by many factors
beyond the known security proofs. Anyway, as a historical matter, the
agreement on a particular signature scheme came after the dust had
settled regarding this claim.

> we recommend to reconsider this decision

Still seems feasible, logistically, but I'm missing what the argument is
supposed to be for making the opposite decision.

---Dan