Re: [Cfrg] EC signature: next steps

Mike Hamburg <mike@shiftleft.org> Fri, 04 September 2015 17:31 UTC

Return-Path: <mike@shiftleft.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 38FD81A92B4 for <cfrg@ietfa.amsl.com>; Fri, 4 Sep 2015 10:31:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.445
X-Spam-Level:
X-Spam-Status: No, score=-0.445 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, GB_I_LETTER=-2, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
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 VyU2AynzuFv7 for <cfrg@ietfa.amsl.com>; Fri, 4 Sep 2015 10:31:29 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B55D51A888E for <cfrg@irtf.org>; Fri, 4 Sep 2015 10:31:29 -0700 (PDT)
Received: from [10.152.184.244] (mobile-166-171-251-003.mycingular.net [166.171.251.3]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 746A63A9C9; Fri, 4 Sep 2015 10:23:32 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1441387412; bh=twpH2HT2mj+HmWKsPJkG0STJq3rL8egPyypyzMz579U=; h=References:In-Reply-To:Cc:From:Subject:Date:To:From; b=jOnPecUBZj5AtmCe7/IOGBDy0kX9XnerLLFYuup7UQiUf591LP+wejBwQhk9eeQDs HMQUXQvOk8BVog9A8nm1idoIF8sCkNaxTDBaBslRdZ6o/PZ4vYybBKDJwACZpn3eUj 66UpZt4h55naT8gKqHVhb9jGgPyfAXKFxd+NQcmI=
References: <55DD906F.3050607@isode.com> <D2035132.531EE%kenny.paterson@rhul.ac.uk> <55DDA21D.9060302@isode.com> <55DF3E3C.7020206@isode.com> <55E42414.3020805@isode.com> <55E99B7C.6020509@gmail.com> <55E9C1A0.7040707@sbcglobal.net> <5EB6295E-33EA-482E-B046-7C3E3C66DF8B@mikehamburg.com>
Mime-Version: 1.0 (1.0)
In-Reply-To: <5EB6295E-33EA-482E-B046-7C3E3C66DF8B@mikehamburg.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: quoted-printable
Message-Id: <B2CE6A03-61B0-4230-AAB0-1726CE8AE5C5@shiftleft.org>
X-Mailer: iPhone Mail (12H321)
From: Mike Hamburg <mike@shiftleft.org>
Date: Fri, 4 Sep 2015 10:31:26 -0700
To: Mike Hamburg <mike@mikehamburg.com>
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/af170b6OrLyNZUHBMOPWxcDrVRI>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] EC signature: next steps
X-BeenThere: cfrg@mail.ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.mail.ietf.org>
List-Unsubscribe: <https://mail.ietf.org/mailman/options/cfrg>, <mailto:cfrg-request@mail.ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@mail.ietf.org>
List-Help: <mailto:cfrg-request@mail.ietf.org?subject=help>
List-Subscribe: <https://mail.ietf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@mail.ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 04 Sep 2015 17:31:31 -0000

I agree with Rene. Having to hold the public key along with the private key can be annoying, and there is little gain to it in light of the papers he cited. More below. 


Sent from my phone.  Please excuse brevity and typos.

> On Sep 4, 2015, at 09:06, David Jacobson <dmjacobson@sbcglobal.net>; wrote:
> 
> Why do you advocate that signing should be possible without requiring the signer to access its public key?  In RSA signataures the public key is (m, e) and the private key is d.  But the signer needs m.   This does not seem to be a problem.

This is useful in cases where the private key is derived pseudo randomly from something like a PUF.  This way the signer can just sign the message instead of deriving the public key first, which would make the operation twice as expensive. 

This use case is not practical with RSA. 

> I don't get how you can do verification without a public key that you believe is the public key for the party you believe to be the sender.  There has to be some connection to something trusted.

By verifying the signature, you recover the public key. Then you can decide whether you trust it, eg by following a cert chain or checking a list of trusted keys or hashes. This avoids sending the public key, which isn't usually a big deal but it can matter for constrained devices.  It's also more elegant in some systems. 

>  --David

Cheers,
-- Mike
> 
>> On 9/4/15 6:24 AM, Rene Struik wrote:
>> Dear colleagues:
>> 
>> I think the signature scheme should facilitate the following:
>> a) signature generation.
>> Ideally, signing should be possible without requiring the signer to access its public key (obviously, it does require the private key). For Schnorr and ECDSA type schemes, one does not need to include the public key in the signing process, since security in the multi-user setting is roughly the same as in the single-user setting (see [1], [2]).
>> b) signature verification.
>> If the public key of the signer is not included with signing, it is also generally not required with verification (if the signature includes the ephemeral signing key), since then the public key of the signer can be reconstructed from the signature itself (with Schnorr signature (R,s) over message m, one has Q=(1/h)(R-sG), where h=H(R,m)). This may have advantages in settings with certificate chains and with single signatures (where one can reduce overhead to identify the public key of the signer).
>> c) reuse of same signing key with IUF/non-IUF schemes.
>> Ideally, one should be able to use the same signing key, no matter whether one uses the signature scheme in the so-called IUF setting or in the non-IUF setting. If I understand correctly, consensus is to only specify an IUF-scheme, but even then, the design should be so that it can support both flavors. This should *not* be left to applications to specify (and can also easily be done).
>> d) same signature scheme for Weierstrass curves, (twisted) Edwards curves, and Montgomery curves.
>> The signature scheme should work for all these three schemes and not just for (twisted) Edwards curves. Ideally, it should also work for Huff curves, Jacobian curves, etc., without requiring any changes outside the scalar multiplication routine.
>> 
>> Best regards, Rene
>> 
>> Ref:
>> [1] A. Menezes, N.P. Smart, "Security of Signature Schemes in A Multi-User Setting", CACR-Corr-2001-063.
>> [2] J. Malone Lee, S. Galbraith, N. P. Smart, "Public Key Signatures in the Multi-User Setting", Inform.Proc.Letters, 2002.
>> 
>> 
>> 
>> 
>>> On 8/31/2015 5:53 AM, Alexey Melnikov wrote:
>>> Dear CFRG participants,
>>> 
>>> Many thanks to Ilari for posting this updated summary of where things
>>> currently stand. Kenny and I would now like to run a short discussion
>>> focusing on this summary, with our intention being to flush out any last
>>> issues or additional points of comparison between the different schemes
>>> that everyone should be aware of.
>>> 
>>> Once everyone has kicked the tires, so to speak, we plan to move to a
>>> poll to decide which scheme CFRG should focus on writing up and formally
>>> recommending. We, as chairs, are hoping these steps will get us to the
>>> finishing line.
>>> 
>>> So:
>>> 
>>> - are there important characteristics or points of comparison that
>>> Ilari's summary does not cover?
>>> 
>>> - are there errors of fact or omission that need to be corrected?
>>> 
>>> - anything else?
>>> 
>>> 
>>> We'll let this discussion run for exactly one week, but we might extend
>>> the time if the discussion is still going strong and new arguments or
>>> points of comparison are brought up. After that, if no major new
>>> information is brought up, we will start the Quaker poll for selecting a
>>> single CFRG-recommended signature scheme.
>>> 
>>> 
>>> Best Regards,
>>> Kenny and Alexey
>>> 
>>> _______________________________________________
>>> Cfrg mailing list
>>> Cfrg@mail.ietf.org
>>> https://mail.ietf.org/mailman/listinfo/cfrg
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@mail.ietf.org
> https://mail.ietf.org/mailman/listinfo/cfrg

References: