Re: [Cfrg] Adoption of threshold drafts by RG

Phillip Hallam-Baker <phill@hallambaker.com> Tue, 29 September 2020 17:16 UTC

Return-Path: <hallam@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 1F8813A0F65 for <cfrg@ietfa.amsl.com>; Tue, 29 Sep 2020 10:16:48 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.648
X-Spam-Level:
X-Spam-Status: No, score=-1.648 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.001, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_BLOCKED=0.001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no autolearn_force=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 WiuzMjY1XYEQ for <cfrg@ietfa.amsl.com>; Tue, 29 Sep 2020 10:16:46 -0700 (PDT)
Received: from mail-oi1-f176.google.com (mail-oi1-f176.google.com [209.85.167.176]) (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 A0D763A0F3B for <cfrg@irtf.org>; Tue, 29 Sep 2020 10:16:46 -0700 (PDT)
Received: by mail-oi1-f176.google.com with SMTP id a3so6304344oib.4 for <cfrg@irtf.org>; Tue, 29 Sep 2020 10:16:46 -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:references:in-reply-to:from:date :message-id:subject:to:cc; bh=6amiczfnycAWDzlXPy+m3E2IzlSVxpOF7dcMujbZNOc=; b=odKoS7tc4BnK1hEUVBhRZnAShQTTf7o/CQzPZQu6XhLfN2f/Alpl0Y3XOowiaGaoA+ 3yPYIE4+B+UTHS0H7EbB9UU6kULZ9DkhgOvWj8UyelKojDHPbUXJ5aSUnB5RoNr8apFf WO3rJb09BVmdg0aW/GUxMXG7LuXxmgdYbolUuZHtvDOLsZ1FJ8VXaLRpzhx4F6uC1tj7 LAQuUgnT2u7A3IT7RqTkWFQ7EYC4MrRq+n/ssKohfXYT2Skvc54XDnfbM2CoYBFPX1WR WK2+oQj2pkEhugmuejVJdYXXBPNvpngZZr/tomGFBYx1b+aNnc9X4p0lKXDzeYhSZ1lT LgHw==
X-Gm-Message-State: AOAM533BH9HKZK0p2PfGRxs2+Qc45g08JkKz/ANHCtkVpwu2OxGBgeWW 4ghA5AlWx2iNmKp/LMQKhVzhwoHcZR4Lc0s5PZw=
X-Google-Smtp-Source: ABdhPJyL7/jTcX15Tl0WBswkrK3Nfm3MFQ00Hcjb+LQl3sW/oq0uOYnZkzFF3qN3EzFMs2HFSj0h1X90a2ADsLyizNc=
X-Received: by 2002:aca:ed13:: with SMTP id l19mr3130309oih.90.1601399805877; Tue, 29 Sep 2020 10:16:45 -0700 (PDT)
MIME-Version: 1.0
References: <CAMm+Lwj8z0i56G7iTh-z7fZM5z5=B7-x63rVJjuWT7mC1x6x3w@mail.gmail.com> <CACsn0c=9SwWsJ=D_gAStP+gnbfmZkTEokESa0wunpBxaJPvn3g@mail.gmail.com>
In-Reply-To: <CACsn0c=9SwWsJ=D_gAStP+gnbfmZkTEokESa0wunpBxaJPvn3g@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Tue, 29 Sep 2020 13:16:35 -0400
Message-ID: <CAMm+LwgZ_o28FaUHJ2JdivarT7a3vUdBTRDKa4YLajF93Gn3ag@mail.gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
Cc: IRTF CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="00000000000092a2af05b076f235"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ackbiiqJAe81UegX2HMQjkaWSNI>
Subject: Re: [Cfrg] Adoption of threshold drafts by RG
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, 29 Sep 2020 17:16:55 -0000

Replying to Watson and Chelsea.

Having read through the papers, I think we are seeing a case of academic
hyperbole rather than an actual fundamental discovery in cryptography.
Rather the paper Watson cites constructs an age old result in concurrency
in terms of cryptography and discovers the same result. No surprise.

For my practical purposes, I am interested in a threshold signature scheme
that works with widely used algorithms and can be safely implemented within
common protocol interactions. This is a rather easier task than the one set
in most academic papers.

There are in fact two completely separate problems here: Creation of
threshold key shares and use of threshold key shares. The spurious claim
that a secure scheme can't be created comes from a crafty conflation of
these two very distinct issues.

Lets just ignore key share generation for the time being and look at use of
a threshold signature. There are four possible outcomes:

1) The process results in disclosure of the private key itself (or
information that enables another party to sign)
2) The process avoids 1 but creates a signature that does not verify
3) The process avoids 1, creates a signature that does verify but is non
deterministic and thus not fully compliant with the original Ed448 spec
4) The process avoids 1, creates a signature that does verify and is
deterministic and thus fully compliant with the original Ed448 spec

For my purposes, the third outcome is sufficient. And I can produce a
fairly straightforward proof that my construction is sound if Ed448 is.
'Attacks' in which a share holder does not provide the correct information
are only of concern if either this results in the private key or ability to
forge a signature leaks.

When it comes to use of the signature, FROST does add a capability that is
not in my current draft which I am very willing to add. But I am going to
need some text from the authors.


Creation of key shares is a rather different issue. The fundamental flaw in
the arguments in various papers asserting 'impossibility' of this or that
is that they don't consider the process of how the key is credentialed at
all. Which is a sure way to end up with nonsense.

There are two potential flows here.

In the first flow a group of contributors generate some data from which a
virtual key pair is established and that key pair is used in what is
essentially a certificate request protocol with some proof of
possession element and then the credential key is used to sign.

In the second flow, there is no certificate request protocol step and no
proof of possession and the result is insecure. That is neither surprising
nor problematic.

The problem is that if you use a proof of possession of the aggregate key
in the first flow it is essentially the same as the second.

If you wish to issue a credential for a threshold key of any type that is
held across multiple authorities, you have to establish a proof of
possession for each of the authorities concerned. This is not just a
problem with signature, there is a similar result for encryption.

So I see this problem as a problem of correctness of the cryptographic
protocol and not the cryptographic algorithm. And I am solving that problem
in my work by constructing keys in very specific ways that are simple,
robust and avoid the division of authority issue.