[Cfrg] Schnorr multisignatures on Ed448 and Ed25519

Phillip Hallam-Baker <phill@hallambaker.com> Tue, 07 May 2019 21:46 UTC

Return-Path: <hallam@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id BCEA01202A9 for <cfrg@ietfa.amsl.com>; Tue, 7 May 2019 14:46:11 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.65
X-Spam-Status: No, score=-1.65 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.249, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id LX_csMunk0ps for <cfrg@ietfa.amsl.com>; Tue, 7 May 2019 14:46:10 -0700 (PDT)
Received: from mail-ot1-f45.google.com (mail-ot1-f45.google.com []) (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 D8FEF1202B7 for <cfrg@irtf.org>; Tue, 7 May 2019 14:46:09 -0700 (PDT)
Received: by mail-ot1-f45.google.com with SMTP id u3so11012760otq.4 for <cfrg@irtf.org>; Tue, 07 May 2019 14:46:09 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=aViJbQoECWRrAuOS61OFO6aeyskTEHIIqXdsJbwqP44=; b=TF8WG4c1BJVZWMJ0hasXwbJ89WZsc/L/1mxOCd/T3qjg/KxgulGNUaxF7c3bSLYKmo dq1Pf0WqCod46jOkCJ8qg7XtWtG/ESaST0l7PzemfbaxuNxVE+J5vkysQWJJeJIe9Dsl sC/t1NYiGmQjAvYFCYC+t0pZ03EsLu6shiRcYEJWCSskaeYjlSIcUVimBeb/90za5tKT rA3K+rTUwbairaevzPWFAWUnM2qa0tdNeKvQdJZdH/70LUHlDteJf7miJM3HyGU/rtJD TxDjdvw7q7SgGfUabDx8xIQb/6oCJafxc3EjsNql4qDTBI5y77MdekZ5GfqIfX2UuEw5 SCfA==
X-Gm-Message-State: APjAAAUEsZQE4l6OSLUjvn/yw97nB05K7UmhQNWg4v2JZwQ/5jwFBx3L CekjdKyLyYuuEdplUIkvM+JjqKdUb2UJihMBFbjOgIQDOQk=
X-Google-Smtp-Source: APXvYqzkQqd+YdoKhxtZN95p8zwDHXE8DFxOfiE0dSDVP8sXV1zq5okE7yWLrpMPHt1loNojffjpu3HZBu8hAbh5RXg=
X-Received: by 2002:a9d:e8c:: with SMTP id 12mr24593229otj.120.1557265568729; Tue, 07 May 2019 14:46:08 -0700 (PDT)
MIME-Version: 1.0
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Tue, 7 May 2019 17:45:59 -0400
Message-ID: <CAMm+LwgA6Z4R+SpFhxWrgfh8LYP7GarCqAASj+j+BMCG+CEt3g@mail.gmail.com>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="0000000000000b8e0b0588532555"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/FXvg1gKbXiJJnBwt7GUeDVH1cSM>
Subject: [Cfrg] Schnorr multisignatures on Ed448 and Ed25519
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
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: Tue, 07 May 2019 21:46:16 -0000

There is a lot of interest in the bitcoin world about the use of Schnorr
multi-signatures and was a recent conversation on the cryptography list on
these. My position is

1) I want to use them or something like them in my design for the Mesh.

I would very much like to have the ability to safely split the generation
of signatures between two different signers so that both signers must use
their parts of the key to generate a composite signature but this does not
reveal any information that might help either party generate signatures for
other documents or perform any other activity related to the composite
private key.

2) I have neither the time nor the expertise to arrive at a sufficient
degree of confidence that the construction is secure.

3) If we don't do it right or tell people it is a bad idea, they are
certain to do it and do it wrong.

Are there any academics who are interested in doing this analysis and
producing a draft that either explains a safe means of creating an Ed448
signature using private keys a, b such that they can be verified with key
A+B or tells us why this is a bad idea?

My concern is of course that El Gamal Signature is a tricky beast and if
you leak certain information used to create one signature, you can enable
an attacker to create other signatures or even disclose the private key.

I am already making use of the key co-generation scheme I described at a
CFRG in Prague some years back. It allows me to make use of manufacturer
generated keys on IoT devices without giving the manufacturer a backdoor.
But the approach I am using right now requires me to join the two parts of
the private key to make use of it. This means I cannot use a manufacturer
provided hardware bound key for signature operations.