Re: [Cfrg] Internet-Draft: Collective Edwards-Curve Digital Signature Algorithm

Oleg Andreev <oleganza@gmail.com> Sun, 02 July 2017 20:47 UTC

Return-Path: <oleganza@gmail.com>
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 62700129ACD for <cfrg@ietfa.amsl.com>; Sun, 2 Jul 2017 13:47:34 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.7
X-Spam-Level:
X-Spam-Status: No, score=-2.7 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, 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 uJjCwjnRH9xY for <cfrg@ietfa.amsl.com>; Sun, 2 Jul 2017 13:47:32 -0700 (PDT)
Received: from mail-lf0-x234.google.com (mail-lf0-x234.google.com [IPv6:2a00:1450:4010:c07::234]) (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 23ABB129AC1 for <cfrg@irtf.org>; Sun, 2 Jul 2017 13:47:32 -0700 (PDT)
Received: by mail-lf0-x234.google.com with SMTP id b207so92765353lfg.2 for <cfrg@irtf.org>; Sun, 02 Jul 2017 13:47:32 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=ijySxrPCdDO1n3GyR5ToKGmd77qj3MRsX9Z9PjUPSwI=; b=Smq6UtQDAqqsIHrYxq+4SgIUOGVLS/LuYH4ONfRjBrqzCzFcWejLj3XzS4QvxAtHSA MjSBPJQEaoOSXWxD/848qjtaqiSuIrsTDfnxNpBSVqBPh/1PoJ9frraRU/yQJYzFG2cT CEMrLYE/Jknz/rcejx7LdB+A2k+BajXwPX+Q6D+bDq1ule7ilSvOIdUTD9dcy5yCmzK+ t4qLC4yZotYK9B2t4a6dZjcNl9dYhBAZDDZI//klVKxmApD85MThmXCGf91ww2z4VBc8 kB3t+R9MWfiiqULP7wHq4xENCiM2mb7DBuytg7TVADxqsv4TyIuPqbK4Zu0uBo1XZOAR mFBg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=ijySxrPCdDO1n3GyR5ToKGmd77qj3MRsX9Z9PjUPSwI=; b=K1s0zUWHSREhbLbx2VmmMtBcgo50Fi0CCEt0j+au/qxMhUsBTtvLmAH8rrVGtePIG4 HyRt4lzDTverfnZ03doTCaOEv0ehAny3djINk47JTceFTEKQamJS/lvi8F4/UupoZQrL mRvOqNTrR5uoY+GA+AefiTOF3LhjcTMpcgEV35C6dU+kkLx0dlypqIACRTWvnk1jYINC Nxr1u90uShjUPo6B7Q0IwnKtVabWCUqQF0aWLnjoEGUB5LIthqQphp73k8H1jLiMNGsT +xYuxek4URiluiPNZ0UeLh4TTueWya9FnP1S3uC4n1oVJ7e6rHKEC7aJgrSfLhCrPK0I rwdw==
X-Gm-Message-State: AKS2vOyUV85LGkkf6a5suQWWjjSnNIoRPK6v1ThtC2XqXnDhEHHeLnOl dab/5v83/yg06g==
X-Received: by 10.25.89.65 with SMTP id n62mr10505398lfb.183.1499028450333; Sun, 02 Jul 2017 13:47:30 -0700 (PDT)
Received: from [192.168.0.114] ([109.167.133.56]) by smtp.gmail.com with ESMTPSA id m16sm2194568ljb.26.2017.07.02.13.47.29 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 02 Jul 2017 13:47:29 -0700 (PDT)
Content-Type: text/plain; charset="utf-8"
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
From: Oleg Andreev <oleganza@gmail.com>
In-Reply-To: <8AE29DD0-26FE-4AB6-A4A9-2BB9169BAB13@jovanovic.io>
Date: Sun, 02 Jul 2017 23:47:28 +0300
Cc: cfrg@irtf.org
Content-Transfer-Encoding: quoted-printable
Message-Id: <5E91769F-B102-4A49-9ED5-B789D4FED598@gmail.com>
References: <8AE29DD0-26FE-4AB6-A4A9-2BB9169BAB13@jovanovic.io>
To: Philipp Jovanovic <philipp@jovanovic.io>
X-Mailer: Apple Mail (2.3273)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/2QTaj7zR80ki0cNoAqng62b6roI>
Subject: Re: [Cfrg] Internet-Draft: Collective Edwards-Curve Digital Signature Algorithm
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sun, 02 Jul 2017 20:47:34 -0000

Hi,

First of all: nice to see a simpler approach than a full SSSS-based threshold signing scheme!

After a quick glance at the spec, I have two security concerns:

1. It seems unsafe to add public keys directly (A = Sum[A_i]) without multiplying them by their hashes (A = Sum[Hash(A_i)*A_i]). Without that measure, it is possible to have A_j as a linear combination of other public keys. See this discussion for details: https://bitcointalk.org/index.php?topic=1377298.0

2. The signature does not commit to membership bitmask Z. Maybe it could be argued that signature is not malleable (especially with an improvement mentioned above), but to stay on safe side I think committing to the exact set of signers is a good idea.


Additionally, I'd suggest an improvement to the API. Since the scheme is not a SSSS scheme, verifier needs to reconstruct the exact key from the individual keys (4.3.5 Signature Verification). Current spec states that verifier should know the set of these member-keys upfront. It could be more practical to provide them as a part of the signature and commit into the aggregate public key, so the setup process looks as simple as non-aggregate one, or one using SSSS: just sharing a single aggregate public key.

This is how it could be done:

1. Organize all member keys in a merkle tree and compute it's root hash `h`.
2. Compute intermediate aggregate key as `A = Sum[Hash(A_i)*A_i]`.
3. Compute aggregate public key with commitment to the merkle tree: `P = Hash(A || h)*A`.
4. Signature will include:
    1) necessary member keys according to bitmask Z.
    2) merkle proof (necessary intermediate hashes needed to reconstruct the root hash).
    3) intermediate key A.
5. Verifier would reconstruct root hash h', compute `Hash(h' || A)*A` and verify it matches the P. Then it will reconstruct actual verification key `A' = A-T` and proceed with Schnorr protocol.

The member keys part of the signature could be optional, so the keys could be cached in case many signature from the same key are continuously verified.

Cheers,
Oleg.

> On 2 Jul 2017, at 00:58, Philipp Jovanovic <philipp@jovanovic.io> wrote:
> 
> Hi CFRG,
> 
> Here’s a first version of an Internet-Draft on “Collective Edwards-Curve Digital Signature Algorithms” based on Ed25519 and Ed448: https://datatracker.ietf.org/doc/draft-ford-cfrg-cosi/
> 
> We plan to give a short presentation on that topic at the next CFRG meeting in Prague.
> 
> Any feedback is more than welcome. Thanks!
> 
> All the best,
> Philipp
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg