Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 41DCA129683 for ; Wed, 22 Mar 2017 04:25:59 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.699 X-Spam-Level: X-Spam-Status: No, score=-2.699 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, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com 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 DAT-nZ8Rt4YE for ; Wed, 22 Mar 2017 04:25:56 -0700 (PDT) Received: from mail-yw0-x22c.google.com (mail-yw0-x22c.google.com [IPv6:2607:f8b0:4002:c05::22c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E8973129483 for ; Wed, 22 Mar 2017 04:25:55 -0700 (PDT) Received: by mail-yw0-x22c.google.com with SMTP id v76so126642052ywg.0 for ; Wed, 22 Mar 2017 04:25:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=0FbLwdEQ8+t/8+HMgZ139fLuB3Iz/rZ9Ol8UQIV9sog=; b=k9vft1uQUAjiYXua0O1gcd71Q/FgbR66LzInH8UZQYF6MvL0LvypLEFU49Uc5KD03A HQMtrefa7rmQCQKJT+XDJcFSjWluU2FxSHbKeqfH1JzI6rF63pUzr9tHoYGTaTzMiK/r PaiExCowE7PjkeIAAsjfEz54ZHcjAMqRSnLuDjOWuttHhf1Vq0qyPgPc2WYXGcnUvC/2 gHQ91VDD5sjWer+4YlA77Y8pvRJ++NV8biIhVPeqWe2SaTuT6GSmZSbJ/bRf/VMTnA4D uqBAtG2s9pqF93a0v+TaMKEZa+16eKLhkC16QU0Ln6+M0ZsuJxatE/k/SgGt8I6zNach N7uQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=0FbLwdEQ8+t/8+HMgZ139fLuB3Iz/rZ9Ol8UQIV9sog=; b=XqMlevzAzoBvZItZL8USDVb4cJzdlR6uhvW2tFhiXC8+KLrKfLQl1RTevw8CCnbhwR uEDratqNV+wS0v6dSspjnjx7M8ESKAGAxoZWjmezndnL6NKfcR/uQybgGP4rRjv6QFTb BztxpR+PAE1h6tj1+DM5D/q9j1AoPuZqX72KHmldmAg06x1uteZ0BgP16Y/rIT6XQUzj 8nupYm8MJaRdtDQqMtfIJPAYZa55LtbYqicyX84DKCI8bfeYMkP0Z39JZ6UoGk3L5vRQ gsnl0wPNx0fM3dyyL1caP1tZRdWhFE5fdpTjeF0HS4z61wU5kWZu1cFjcfLgXuqcnAFq Nmcg== X-Gm-Message-State: AFeK/H1XqtgXCZPHD5EmHa1zTjOIQto7eAz6+WBmKaF2a5nJaRwH0BTU2+hNF77t1WlXhD5uCE0h1Rsl86g9vA== X-Received: by 10.129.111.8 with SMTP id k8mr15446566ywc.303.1490181954683; Wed, 22 Mar 2017 04:25:54 -0700 (PDT) MIME-Version: 1.0 Received: by 10.83.67.35 with HTTP; Wed, 22 Mar 2017 04:25:39 -0700 (PDT) In-Reply-To: References: From: Dmitry Khovratovich Date: Wed, 22 Mar 2017 12:25:39 +0100 Message-ID: To: Phillip Hallam-Baker , Jason Law Cc: Tony Arcieri , "cfrg@irtf.org" Content-Type: multipart/alternative; boundary=001a1145ec6a0f5498054b5006b1 Archived-At: Subject: Re: [Cfrg] Interest in an "Ed25519-HD" standard? X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 22 Mar 2017 11:25:59 -0000 --001a1145ec6a0f5498054b5006b1 Content-Type: text/plain; charset=UTF-8 Being a co-author of [5], I am ready to contribute to such a document. I will present our own proposal at http://prosecco.gforge.inria.fr/ieee-blockchain2016/ in Paris just before the CFRG meeting at the same place next day. It would be great if we come up with some proposal to discuss it already there. The most recent version is https://drive.google.com/open?id=0ByMtMw2hul0EMFJuNnZORDR2NDA It has some critique of [6], hopefully not too offensive:) Our motivation in [5] was to generate private keys satisfying the Curve25519 requirements too so that the code can be reused, even if in the signature setting some attacks would not apply. But it would be great to have comments from the community as well. Best regards, Dmitry On Wed, Mar 22, 2017 at 5:00 AM, Phillip Hallam-Baker wrote: > You can do hierarchical key derivation in Montgomery without the need for > an add. > > Say your master key is x. To generate a key for site 'example.com' we > take > > xs = (x + H('example.com')) mod q > > Where q is the sub group order. > > In fact that isn't really using any EC relevant operation at all. Perhaps > I am not understanding the full requirements for the scheme. > > > I don't follow the argument about small subgroups in the referenced post. > With Curve25519 and Ed25519 we have chosen the curve cofactor and the > generator point. So there is only one group that our point can possibly be > in regardless of whether our private key is (x mod q) or (x mod q + nq). We > are going to arrive at the same set of points regardless. > > > I do very much prefer the Edwards curves though because we can combine two > keypairs by simply adding the corresponding public and private keys. That > allows us to do the co-generation trick I showed a while back. > > We can also split the key, give one part to a recryption service and > encrypt the other half under the public key of the recipient. This allows > us to support group messaging through proxy re-encryption. > > Some applications of that are encumbered (possibly) under a soon to expire > patent. > > > > On Tue, Mar 21, 2017 at 8:34 PM, Phillip Hallam-Baker < > phill@hallambaker.com> wrote: > >> I have just implemented Proxy Re-Encryption under Ed-25519 and Ed448. I >> think EdCurve Crypto is a good plan. >> >> Or we could do it on the Montgomery Curves and give the algorithm for >> point addition. >> >> On Tue, Mar 21, 2017 at 3:42 PM, Tony Arcieri wrote: >> >>> Hierarchical key derivation (also sometimes described as "semiprivate >>> keys" or "key blinding") is an increasingly popular technique for >>> generating unlinkable child keys from master public and private keys. >>> >>> The Tor Project has been exploring such an approach as the basis for >>> their next-generation hidden services design for several years now[1], >>> during which time it has received security proofs[2]. Their latest >>> design[3] allegedly includes feedback from Dan Bernstein. >>> >>> Application of hierarchical key derivation is perhaps most notable in >>> the cryptocurrency space, where Bitcoin's BIP32[4] provided a means for >>> unlinkable single-use signature keys for the secp256k1 elliptic curve. >>> There are several designs for applying the ideas from BIP32 to Ed25519, >>> including ones from Evernym[5] and Chain[6] (where I am an employee). >>> >>> The designs in [3], [5], and [6] are all highly similar and accomplish >>> the same goals. Personally I would love to see a single standard design for >>> producing Ed25519 signatures from hierarchically derived keys, notably one >>> which produces signatures that can be verified by any off-the-shelf RFC >>> 8032-compatible Ed25519 implementation. >>> >>> There's already been some discussion of this on the moderncrypto.org >>> curves list: >>> >>> https://moderncrypto.org/mail-archive/curves/2017/000858.html >>> >>> I'd be curious to know if anyone else would be interested in >>> collaborating on a draft for such a standard, which can be a synthesis of >>> the existing work in this space. >>> >>> [1]: https://lists.torproject.org/pipermail/tor-dev/2012-Sep >>> tember/004026.html >>> [2]: https://www-users.cs.umn.edu/~hopper/basic-proof.pdf >>> [3]: https://gitweb.torproject.org/torspec.git/tree/proposal >>> s/224-rend-spec-ng.txt#n1979 >>> [4]: https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki >>> [5]: https://github.com/WebOfTrustInfo/rebooting-the-web-of- >>> trust-fall2016/blob/master/topics-and-advance-readings/HDKey >>> s-Ed25519.pdf >>> [6]: https://chain.com/docs/protocol/specifications/chainkd >>> >>> -- >>> Tony Arcieri >>> >>> _______________________________________________ >>> Cfrg mailing list >>> Cfrg@irtf.org >>> https://www.irtf.org/mailman/listinfo/cfrg >>> >>> >> > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg > > -- Best regards, Dmitry Khovratovich --001a1145ec6a0f5498054b5006b1 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Being a co-author of [5], I am ready to contribute to such= a document. I will present our own proposal at=C2=A0http://prosecco.gforge.inria.fr/= ieee-blockchain2016/ in Paris =C2=A0just before the CFRG meeting at the= same place next day. It would be great if we come up with some proposal to= discuss it already there.

The most recent version is=C2= =A0https://drive.google.com/open?id=3D0ByMtMw2hul0EMFJuNnZORDR2NDA It = has some critique of [6], hopefully not too offensive:)

<= div>Our motivation in [5] was to generate private keys satisfying the Curve= 25519 requirements too so that the code can be reused, even if in the signa= ture setting some attacks would not apply. But it would be great to have co= mments from the community as well.

Best regards,
Dmitry

On Wed, Mar 22, 2017 at 5:00 AM, Phillip Hallam-Baker <phill@halla= mbaker.com> wrote:
You can do hiera= rchical key derivation in Montgomery without the need for an add.

Say you= r master key is x. To generate a key for site 'example.com' we take=C2=A0

xs =3D (x + H= ('example.com'= )) mod q

Where q is the sub group order.

In fact that isn't really = using any EC relevant operation at all. Perhaps I am not understanding the = full requirements for the scheme.

<= /div>

I don't follow the argument about small subgroups in the referenced p= ost. With Curve25519 and Ed25519 we have chosen the curve cofactor and the = generator point. So there is only one group that our point can possibly be = in regardless of whether our private key is (x mod q) or (x mod q + nq). We= are going to arrive at the same set of points regardless.


I do very much prefer the Edwards curves though= because we can combine two keypairs by simply adding the corresponding pub= lic and private keys. That allows us to do the co-generation trick I showed= a while back.

We can also split the key, give one part to a recryption s= ervice and encrypt the other half under the public key of the recipient. Th= is allows us to support group messaging through proxy re-encryption.
<= div style=3D"font-size:small">
Some= applications of that are encumbered (possibly) under a soon to expire pate= nt.=C2=A0



On Tue, Mar = 21, 2017 at 8:34 PM, Phillip Hallam-Baker <phill@hallambaker.com&g= t; wrote:
I have just implemented Proxy Re= -Encryption under Ed-25519 and Ed448. I think EdCurve Crypto is a good plan= .

Or we could do it on the Montgomery Curves and give the algorithm for p= oint addition.

On Tue, Mar 21, = 2017 at 3:42 PM, Tony Arcieri <bascule@gmail.com> wrote:
=
Hierarchical key deri= vation (also sometimes described as "semiprivate keys" or "k= ey blinding") is an increasingly popular technique for generating unli= nkable child keys from master public and private keys.

T= he Tor Project has been exploring such an approach as the basis for their n= ext-generation hidden services design for several years now[1], during whic= h time it has received security proofs[2]. Their latest design[3] allegedly= includes feedback from Dan Bernstein.

Application= of hierarchical key derivation is perhaps most notable in the cryptocurren= cy space, where Bitcoin's BIP32[4] provided a means for unlinkable sing= le-use signature keys for the secp256k1 elliptic curve. There are several d= esigns for applying the ideas from BIP32 to Ed25519, including ones from Ev= ernym[5] and Chain[6] (where I am an employee).

Th= e designs in [3], [5], and [6] are all highly similar and accomplish the sa= me goals. Personally I would love to see a single standard design for produ= cing Ed25519 signatures from hierarchically derived keys, notably one which= produces signatures that can be verified by any off-the-shelf RFC 8032-com= patible Ed25519 implementation.

There's alread= y been some discussion of this on the moderncrypto.org curves list:

https://moderncrypto.org/mail-archive/curves/2017/00= 0858.html

I'd be curious to know = if anyone else would be interested in collaborating on a draft for such a s= tandard, which can be a synthesis of the existing work in this space.
=
[5]:=C2=A0https://github.com/WebOfTrustInfo/rebooting-the-web-of-tru= st-fall2016/blob/master/topics-and-advance-readings/HDKeys-Ed2551= 9.pdf

--
Tony Arcieri

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg




_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg




--
Best regards,
Dmitry Khovratovich
--001a1145ec6a0f5498054b5006b1--