[Cfrg] Threshold cryptography on CFRG curves

Phillip Hallam-Baker <phill@hallambaker.com> Tue, 17 December 2019 16:54 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 9300212007C for <cfrg@ietfa.amsl.com>; Tue, 17 Dec 2019 08:54:48 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.399
X-Spam-Status: No, score=-1.399 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.249, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.25, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id RSaryeGrfZpo for <cfrg@ietfa.amsl.com>; Tue, 17 Dec 2019 08:54:47 -0800 (PST)
Received: from mail-oi1-f174.google.com (mail-oi1-f174.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 0CDD412002F for <cfrg@irtf.org>; Tue, 17 Dec 2019 08:54:47 -0800 (PST)
Received: by mail-oi1-f174.google.com with SMTP id 6so5888132oix.7 for <cfrg@irtf.org>; Tue, 17 Dec 2019 08:54:47 -0800 (PST)
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=/vHtc0bw6Sxsg88VzvPC/6DiAgdvtseJNVag3KQDq0U=; b=RUEHB/nArlpwsdEx7oF+A8imXgolW35H4tPXA+c+uuntrdj0oksOcDSZqB0ULVAOBq xzzc+CL0hKDUsu9cU1YQsEdDmnnt+oTzWj+Hv53v+U7I+37Ggus6ENYQd5jqG2osvqky 4ZQPYlyur3+0+4lJgRunNmNOcCVeVm7QLQhWeO+4LWcG8lNC168+04GzXoWF4IH29ePH 188mURQhsp/ikfWTjY43LraBf2Mkd5WW8PcbeDDO4KvvleRtoaDukJNO2H6tq+FUyZul TLmE5jzJtwtcgKMPHw/yRoRbeTgyuYpqPrnfet2QHSWAr/XrcHbl3YnRIpmQ+Rs0xWUK pKvw==
X-Gm-Message-State: APjAAAUONNYbNpejgMsicUZx5lwCBQDRL4TY9WAnRwaZXKKjybO8eHfu BstVjwEcrZUlJ9wZ6FVbYyJgfshm7G66i63EGh5I6GDRlxI=
X-Google-Smtp-Source: APXvYqwthUb+1K84Mk1CtO2RBOpCZkDKAmvZGkRjS1NHn1r8bPrBQEbyAR5WovqDtrJ78HNrtjZ4mDeFB/OZqD7gDaI=
X-Received: by 2002:aca:4106:: with SMTP id o6mr2074693oia.173.1576601685917; Tue, 17 Dec 2019 08:54:45 -0800 (PST)
MIME-Version: 1.0
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Tue, 17 Dec 2019 11:54:35 -0500
Message-ID: <CAMm+Lwjagk4eObv283hTH0WCaYYfCAv6bWdFDPYCtNZwZqLT-Q@mail.gmail.com>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="0000000000007104910599e92f39"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/TC_RFSuHRUMXBoaoWIHHm7Wz1qk>
Subject: [Cfrg] Threshold cryptography on CFRG curves
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, 17 Dec 2019 16:54:49 -0000

I am working my way through an ID describing four schemes using threshold
math based on the Ed25519, Ed448, X25519 and X448 curves. These will specify

* Threshold Key Generation
* Threshold Decryption
* Mutual Authenticated Key Exchange
* Side channel resistance.

I think I have the math worked out now for the Montgomery curves. There is
something of an issue with encoding signed results. In particular for X448.

X25519 is 255 bits = 31.7 bytes so there is a spare bit we can use to
express the sign. X448 is 448 bits = 56.0 bytes. So there is no extra space.

The simplest option seems to be to extend the encoding of X448 results by
one byte so that they are 57 bytes. Which is essentially what we do for

Should I do the same for X25519 as well? After all RFC 7748 section 5 says:

For X25519, the unused, most significant bit MUST be zero.

These results are going to need separate algorithm identifiers in any case
as they are distinct from the regular CurveX results. But the only
circumstance in which they are going to appear on the wire is in contexts
which are not covered by existing IETF protocols, that is threshold
decryption and threshold key generation.

Also note that there is a NIST solicitation on this area:


The proposals at the workshop seem to have been focused on threshold
signatures which don't hold much interest for me. If we want to know that a
document was signed by Alice and by Bob, have Alice and Bob both sign it.
Done. Can even define signature quorums (n out of m).

The only advantage I can see in having a threshold scheme is if the
signature can sit in the exact same protocol slot that a regular one could.
And it doesn't look like RFC8032 can be adapted for that. Or at least, my
attempt failed.

I can split the signature between Alice and Bob so that both of them have
to co-operate to sign. But whoever assembles the contributions can extract
the private key (!). Which isn't going to work if we want Alice and Bob to
split up the signature duties.

This constraint might be acceptable if we were designing some sort of TPM
device and splitting the signature capability between application layer
code and the TPM with the combination of the signature contributions taking
place inside the TPM. But since the TPM is going to be able to reverse
engineer the private key anyway, why not have the application code just
tell the TPM what its contribution to the private key is... ?