Re: [Cfrg] key as message prefix => multi-key security

[Eike Kiltz <[e-mail]>]

Our results are not stated entirely correctly, so let me clarify first.

In our paper
     https://eprint.iacr.org/2015/1122.pdf
we show the following (cf. Figure 2):

1. Strong single-user security of Schnorr signatures tightly implies
strong multi-user security of the same scheme

2. Standard single user security of Schnorr signatures tightly implies strong
multi-user security of the same scheme, assuming a perfect hash
function (aka random oracle). This is the original GMLS theorem,
expect that we make the random oracle requirement.


As I understand the history of this thread, initially the group agreed
that key-prefixing should be avoided for Schnorr due to certain
performance and usability issues, referring to the GMLS theorem
from 2002. (See the message by Struik and Hamburg.)

Next, Dan pointed to the error in the original GMLS proof and gave
a fixed proof of tight security for the key-prefixed variant of Schnorr.
He further argued that a tight reduction for the original Schnorr
scheme without key-prefixing is very unlikely. As a consequence
the group mutually agreed to use the key-prefixed variant, resulting
in the current draft for EdDSA.

Our results show that key-prefixing does not provide any advantage
for multi-user security so we recommend to reconsider this decision.

 -Eike


On Fri, Nov 20, 2015 at 8:45 AM, D. J. Bernstein <[e-mail]> wrote:
> There's a new paper out on multi-user signature security:
>
>    https://eprint.iacr.org/2015/1122.pdf
>
> The abstract says that "single-user security of Schnorr signatures
> tightly implies multi-user security of the same scheme".
>
> My impression from previous papers is that Kiltz is careful, but I
> haven't had time to look at the details of the new proof yet. The only
> obvious caveats in the theorem statement from a first glance are that
>
>    * the theorem allows a factor of 2 gain in success probability and,
>      more importantly,
>
>    * the theorem actually has to assume "strong unforgeability" rather
>      than the standard notion of unforgeability---there's no limit on
>      how much security this could lose.