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

"D. J. Bernstein" <djb@cr.yp.to> Fri, 20 November 2015 07:45 UTC

Date: Fri, 20 Nov 2015 07:45:29 -0000
Message-ID: <20151120074529.15234.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@ietf.org
Mail-Followup-To: cfrg@ietf.org
In-Reply-To: <20150930225622.21805.qmail@cr.yp.to>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/PQJAdD1MOKaMs3gufLklBYK8Zds>
Subject: Re: [Cfrg] key as message prefix => multi-key security
Precedence: list

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.

---Dan

[Cfrg] EC signature: next steps Alexey Melnikov
Re: [Cfrg] EC signature: next steps Simon Josefsson
Re: [Cfrg] EC signature: next steps Watson Ladd
[Cfrg] EC signature: next steps Dan Brown
Re: [Cfrg] EC signature: next steps Ilari Liusvaara
Re: [Cfrg] EC signature: next steps Stephen Farrell
Re: [Cfrg] EC signature: next steps Dan Brown
Re: [Cfrg] EC signature: next steps Simon Josefsson
Re: [Cfrg] EC signature: next steps Ilari Liusvaara
[Cfrg] Side inputs to signature systems D. J. Bernstein
Re: [Cfrg] Side inputs to signature systems Natanael
Re: [Cfrg] EC signature: next steps Simon Josefsson
Re: [Cfrg] Side inputs to signature systems Michael Hamburg
Re: [Cfrg] EC signature: next steps Rene Struik
Re: [Cfrg] EC signature: next steps David Jacobson
Re: [Cfrg] EC signature: next steps Mike Hamburg
Re: [Cfrg] EC signature: next steps William Whyte
Re: [Cfrg] EC signature: next steps Stephen Farrell
Re: [Cfrg] EC signature: next steps Blumenthal, Uri - 0553 - MITLL
Re: [Cfrg] EC signature: next steps Ilari Liusvaara
Re: [Cfrg] EC signature: next steps Stephen Farrell
Re: [Cfrg] EC signature: next steps Blumenthal, Uri - 0553 - MITLL
Re: [Cfrg] EC signature: next steps Blumenthal, Uri - 0553 - MITLL
Re: [Cfrg] EC signature: next steps Blumenthal, Uri - 0553 - MITLL
Re: [Cfrg] key as message prefix => multi-key sec… Dan Brown
[Cfrg] key as message prefix => multi-key security D. J. Bernstein
Re: [Cfrg] key as message prefix => multi-key sec… D. J. Bernstein
Re: [Cfrg] key as message prefix => multi-key sec… Paterson, Kenny
Re: [Cfrg] key as message prefix => multi-key sec… Sven Schäge
Re: [Cfrg] key as message prefix => multi-key sec… Blumenthal, Uri - 0553 - MITLL
Re: [Cfrg] key as message prefix => multi-key sec… William Whyte
Re: [Cfrg] key as message prefix => multi-key sec… Bill Cox
Re: [Cfrg] key as message prefix => multi-key sec… Andrey Jivsov
Re: [Cfrg] key as message prefix => multi-key sec… D. J. Bernstein
Re: [Cfrg] key as message prefix => multi-key sec… D. J. Bernstein
Re: [Cfrg] key as message prefix => multi-key sec… D. J. Bernstein
Re: [Cfrg] key as message prefix => multi-key sec… Eike Kiltz
Re: [Cfrg] key as message prefix => multi-key sec… D. J. Bernstein
Re: [Cfrg] key as message prefix => multi-key sec… Simon Josefsson