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

"D. J. Bernstein" <> Wed, 30 September 2015 22:56 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 375291AC3E8 for <>; Wed, 30 Sep 2015 15:56:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 2.896
X-Spam-Level: **
X-Spam-Status: No, score=2.896 tagged_above=-999 required=5 tests=[BAYES_50=0.8, HELO_EQ_NL=0.55, HOST_EQ_NL=1.545, RCVD_IN_DNSWL_NONE=-0.0001, UNPARSEABLE_RELAY=0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id DF7uPEldHKUD for <>; Wed, 30 Sep 2015 15:56:31 -0700 (PDT)
Received: from ( []) by (Postfix) with SMTP id D7B8A1AC3E1 for <>; Wed, 30 Sep 2015 15:56:30 -0700 (PDT)
Received: (qmail 23058 invoked by uid 1017); 30 Sep 2015 22:56:50 -0000
Received: from unknown (unknown) by unknown with QMTP; 30 Sep 2015 22:56:50 -0000
Received: (qmail 21807 invoked by uid 1000); 30 Sep 2015 22:56:22 -0000
Date: 30 Sep 2015 22:56:22 -0000
Message-ID: <>
From: "D. J. Bernstein" <>
In-Reply-To: <>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
Archived-At: <>
Subject: Re: [Cfrg] key as message prefix => multi-key security
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 30 Sep 2015 22:56:33 -0000

Andrey Jivsov writes:
> Because CFRG requires a deterministic signature method, "classic"
> scheme in [1] doesn't look like a good model for any current signature
> proposal.

The whole point of this type of security analysis is to understand the
potential gaps in difficulty between _different_ problems facing the
attacker: e.g., between the problem of breaking signature system X and
the problem of breaking signature system Y.

The gold standard in this area is proving that a new problem is at least
as hard to solve as a classic problem. This doesn't say that the two
problems are good models of each other: maybe the new problem is even
_harder_ to break! But that's not relevant to the logic. Here's the
standard argument: the classic problem has survived scrutiny; this means
(hopefully) that the classic problem is hard to solve; this in turn
implies that the new problem is hard to solve. (Of course, all of this
breaks down if the classic problem is actually easy to solve---maybe
everybody missed an important attack strategy against that problem.)

Consider, for example, the following chain of problems:

   * Problem 1: Forge signatures from a single signer in the classic
     Schnorr signature scheme.

     This has been around long enough, and studied long enough, that one
     can reasonably hope that it's hard to break. However, even if we
     _assume_ that it's hard to break, we still need to figure out what
     this means for other problems facing the attacker.

   * Problem 2: Forge signatures from any 1 of N signers in a modified
     signature scheme that uses the public key as a prefix of a message.

     It's conceivable that Problem 2 is _harder_ to solve than Problem
     1. Maybe an attack against Problem 1 requires particular message
     prefixes that can't be adjusted to match the public key. (One can
     manufacture artifically dumb hash functions that allow attacks
     against Problem 1 without obviously breaking Problem 2; on the
     other hand, this doesn't say anything about real hash functions.)

     Earlier I was explaining in detail a proof that Problem 2 can't be
     _easier_ to solve than Problem 1: any attack against Problem 2 can
     be converted into an attack against Problem 1 with the same success
     probability and practically identical speed.
   * Problem 3: Same as Problem 2, except with "signature caching" by
     all of the legitimate signers. This means that, once a message has
     been signed, the signer will always return that signature for that
     message, rather than generating new signatures for that message.

     It's conceivable that Problem 3 is _harder_ to solve than Problem
     2. Maybe having multiple signatures on the same message leaks
     information somehow, and signature caching stops this (as in, e.g.,

     Problem 3 can't be _easier_ to solve than Problem 2. Any attack
     against Problem 3 can be converted (by caching!) into an attack
     against Problem 2 with the same success probability and practically
     identical speed.

   * Problem 4: Same as Problem 3, except that now the legitimate
     signers deterministically generate each one-time scalar as a keyed
     hash of the message to be signed, where the key is a long-term
     signer secret, independent of everything else.

     If the keyed hash is indistinguishable from uniform---this is a
     standard "PRF" assumption---then Problem 4 is indistinguishable
     from Problem 3, and thus can't be easier or harder to solve than
     Problem 3.

The main conclusion is that _if_ classic Schnorr for a single signer is
hard to break, _and_ the PRF assumption holds, _then_ the deterministic
key-prefixed system for N signers is hard to break. This provides the
following guidance to someone looking for attacks against the
deterministic key-prefixed system:

   * find a single-key attack against classic Schnorr, or
   * find an attack against the PRF assumption, or
   * find an error in the logic, or
   * find an attack outside the attack model.

The bigger picture is that this is still only part of a comprehensive
security analysis. Earlier I mentioned several complications in the
"provable security" picture; derandomization was only one of the items,
certainly not the most difficult item.