A Hybrid Signature Method with Strong Non-Separability

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶

This Internet-Draft will expire on 21 December 2023.¶

Copyright Notice

Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved.¶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶

Table of Contents

1. Introduction

In the past few years, there has been great progress in the development of quantum-computing. Today, most of the cryptographic algorithms are based on the difficulty of integer factorization and discrete logarithm over finite fields or elliptic curves. Yet in the upcoming years, with the potential of building a strong enough quantum-computer capable of computing Shor's algorithm - a so-called cryptographically relevant quantum computer (CRQC) - these algorithms may no longer be secure enough to rely upon.¶

With the looming threat of CRQCs breaking existing public key constructs such as digital signatures, the world in general and the IETF in particular are looking to transition to so-called post-quantum algorithms, algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer.¶

The National Institute of Standards and Technology (NIST) has been running a project for selecting such post-quantum algorithms since 2016 ([NIST-PQC]). This project is not complete at the time of this writing. It has produced several finalists including Crystals-Dilithium ([Dilithium]), Falcon, and more.¶

There is, however, concern about deploying these new algorithms as full replacements for the existing (or "classic") algorithms. On the one hand, there is the fear that researchers or nation-state adversaries will produce a CRQC that will allow them to break the classic algorithms such as RSA, ECDSA, and EdDSA. On the other hand, there is still doubt about the security of the new algorithms. This doubt is well-founded: One of the candidate algorithms, SIKE, was broken in late stages of the competition ([SIKE-BREAK]).¶

To minimize the risks or relying on a single algorithm, there are some proposals for combining two or more algorithms, typically a classic algorithm and a post-quantum algorithm, such that all of the algorithms are used to create the signature, and some or all of them are used to verify the signature. This has the advantage that unless the adversary is able to break all of the algorithms, a verifier who uses all of the algorithms will not be fooled. One such proposal is [I-D.ounsworth-pq-composite-sigs].¶

Most such proposals, including the above-mentioned draft, involve independently signing with the several algorithms, each having their own private/public key pair. With these schemes the private key is a concatenation or a vector of the private keys of the several algorithms, and similarly the public key is a vector of the public keys, and the signature is a vector of independent signatures. A signature like that is said to be parallel and separable, as there is no dependency between the signatures involved.¶

This draft proposes alternate schemes where specific algorithms are combined to create signatures that are non-separable, meaning that it is not possible to verify the signature using just one algorithm. This is based on an article by Bindel and Hale ([Bindel23]).¶

2. Terminology

3. Hybrid Schemes

EDNOTE: As PQC standardization is still in process, both Dilithium and Falcon signature schemes can change in some aspects from their final form. To handle this situation both signatures will be described in more of a general form, Dilithium as a Fiat-Shamir based scheme with black box functions that will be replaced with the actual Dilithium implementation after the publication of parameters and implementations. Also, hybrid schemes with Falcon will be added.¶

Input:
sk1    signer's Dilithium private key (A_Dil, t, s1, s2)
sk2    signer's ECDSA private key (x, q)
pk1    verifier's Dilithium public key (A_Dil, t)
pk2    verifier's ECDSA public key (xG, q)
M      message to be signed of arbitrary size

Output:
S      signature, contains (z, h, r, s)
       z the Dilithium signature proof
       h challenge combining both of the signatures
       r the X coordinate of a randomly
         generated point on the curve
       s the ECDSA signature proof
-

4. IANA Considerations

To Be Added. We need at least OIDs for the combinations above.¶

5. Comparison with Other Proposals

TODO: Add here a discussion of the differences between this proposal and draft-ounsworth. Need to cover both advantages (SNS, SV) and disadvantages: backward compatibility.¶

6. Security Considerations

Security considerations appear in this document, specifically in Section 2.2 and Section 2.3, when discussing SNS and BC. Proofs of the security of the constructions described in Section 3 are given in the Bindel-Hale article.¶

Appendix A. Change Log

RFC EDITOR: PLEASE REMOVE THIS SECTION AS IT IS ONLY MEANT TO AID THE WORKING GROUP IN TRACKING CHANGES TO THIS DOCUMENT.¶

draft-nir-lamps-altcompsigs-00 - first version.¶

Author's Address