Re: [TLS] [Cfrg] FW: Schnorr Signatures

Watson Ladd <watsonbladd@gmail.com> Mon, 07 July 2014 15:01 UTC

Return-Path: <watsonbladd@gmail.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A68161A0208 for <tls@ietfa.amsl.com>; Mon, 7 Jul 2014 08:01:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id n4OimLcPCmwT for <tls@ietfa.amsl.com>; Mon, 7 Jul 2014 08:01:05 -0700 (PDT)
Received: from mail-we0-x22e.google.com (mail-we0-x22e.google.com [IPv6:2a00:1450:400c:c03::22e]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 74C501A01E1 for <tls@ietf.org>; Mon, 7 Jul 2014 08:01:05 -0700 (PDT)
Received: by mail-we0-f174.google.com with SMTP id u57so4560126wes.19 for <tls@ietf.org>; Mon, 07 Jul 2014 08:01:04 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=9PGr9ciCJUoEBAjNyiV64OjhCF97PPxHYuLhdH5g84s=; b=Jbp5Ehv1zq2cayOKJuzagdPx14p+rw1JgTnaHR3o5AWmrdzuKCdYKcbLUUAiDIQUsb XKNZDoSdCgiXgBfcYnY371TJ+FiwCObbwkiref5YVYPW9z0oHguIOAv9FWUlTb7DsjHx +8E2REg/0+PmafyKJRuHSgGVVuxDTxTx5mNfLKO2kW+OfdwWj7iYEMOhYPeFmUMECAC+ 0zHkEoLe6ft+Lp13YHe2Y1u60uB5n3kSIyrVx++PVYGl9f/m9+D1Q+L4jNzItzcgXx08 XILa8DX8zKQFhdPG3Fl7gU/7q0U/cO9XCRRrdMuB0+dKeTFhnD5ZObjjRtugVGXp9VZo 0IzA==
MIME-Version: 1.0
X-Received: by 10.194.219.70 with SMTP id pm6mr32575862wjc.53.1404745263391; Mon, 07 Jul 2014 08:01:03 -0700 (PDT)
Received: by 10.194.21.69 with HTTP; Mon, 7 Jul 2014 08:01:03 -0700 (PDT)
Received: by 10.194.21.69 with HTTP; Mon, 7 Jul 2014 08:01:03 -0700 (PDT)
In-Reply-To: <53BAB45C.7040603@secunet.com>
References: <53AC88F2.7020405@cs.bris.ac.uk> <53BAB45C.7040603@secunet.com>
Date: Mon, 7 Jul 2014 08:01:03 -0700
Message-ID: <CACsn0ckNFh_sH0WOpTSE6byq9_-2JqApWYREjzkfsyGCDMGThQ@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: tls@ietf.org
Content-Type: multipart/alternative; boundary=001a11c1b31c6ca99804fd9bbe2b
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/s_Ug2e-I6wDdrHChA2WTk8IRyOo
Subject: Re: [TLS] [Cfrg] FW: Schnorr Signatures
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 07 Jul 2014 15:01:07 -0000

On Jul 7, 2014 7:53 AM, "Johannes Merkle" <johannes.merkle@secunet.com>
wrote:
>
> Nigel Smart wrote on 26.06.2014 22:56:
> > With Schnorr you dont send the x-coord of R. What you send is
> > half the hash value e
> >     e=Hash(R||Message)
> > So if using SHA-256 you send 128 bits of e over.
>
> Actually, the Schnorr signature is defined as using the full hash value,
but it has been repeatedly proposed (originally
> by Schnorr himself) to use a half-length hash function (and that could be
truncated SHA-256).
>
> However, as you pointed out in [1], the security proofs you mentioned do
not work with reduced hash length h=b AND
> standard group order g = 2^(2b) for security level b. Your proof in the
generic model [1] requires h=2*b and the proof
> of Pointcheval and Stern in the Random oracle model [2] needs g=2^(3b).
Thus, when using half-length hash values you
> sacrifice provable security.

While the Pointcheval and Stern result is not tight, no one has made
attacks that do better.

The most compact and performant variant sends R and S. R is the size of a
group element, S the size of order of the group. This way the length of
what is to be transmitted does not depend on the hash used.
>
>
> [1] Gregory Neven, Nigel P. Smart, and Bogdan Warinschi. Hash function
requirements for schnorr
> signatures. J. Mathematical Cryptology, 3(1):69–87, 2009
>
> [2] David Pointcheval and Jacques Stern. Security arguments for digital
signatures and blind signatures.
> Journal of Cryptology, 13(3):361–396, March 2000.
>
>
> --
> Johannes
>
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls