Post-quantum Multi-Key Mechanisms for PKIX-like protocols; Problem Statement and Overview of Solution Space
draft-pq-pkix-problem-statement-01

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions
• 00
• 01

LAMPS                                                       M. Ounsworth
Internet-Draft                                          Entrust Datacard
Intended status: Informational                        September 17, 2019
Expires: March 20, 2020

   Post-quantum Multi-Key Mechanisms for PKIX-like protocols; Problem
                Statement and Overview of Solution Space
                   draft-pq-pkix-problem-statement-01

Abstract

   With the widespread adoption of post-quantum (PQ) cryptography will
   come uncertainty about the strength of cryptographic primitives.  For
   example; when will RSA and ECC fall?  Are Lattice schemes as strong
   as we believe?  The cryptographic community is calling for hybrid
   schemes that combine classic and post-quantum crypto in ways that
   remain strong so long as at least one of the algorithms used remains
   strong.

   This document defines the problem statement for digital signatures in
   PKIX-like protocols, and gives an overview of the general families of
   solutions.

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 March 20, 2020.

Copyright Notice

   Copyright (c) 2019 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

Ounsworth                Expires March 20, 2020                 [Page 1]
Internet-Draft       PQ PKIX Sigs Problem Statement       September 2019

   (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 Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Problem Statement . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Formal Security Requirements  . . . . . . . . . . . . . .   2
   2.  Solution Space  . . . . . . . . . . . . . . . . . . . . . . .   3
     2.1.  "Composite" concatenated keys and signatures  . . . . . .   4
     2.2.  Application: X.509  . . . . . . . . . . . . . . . . . . .   5
       2.2.1.  Multiple Certificate Chains . . . . . . . . . . . . .   5
       2.2.2.  "Hybrid" v3 extensions  . . . . . . . . . . . . . . .   6
   3.  Conclusion  . . . . . . . . . . . . . . . . . . . . . . . . .   7
   4.  Intellectual Property Considerations  . . . . . . . . . . . .   8
   5.  Contributors and Acknowledgements . . . . . . . . . . . . . .   8
   6.  Informative References  . . . . . . . . . . . . . . . . . . .   8
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .   8

1.  Problem Statement

   In general terms, "hybrid" or "layered" signatures means that the
   document signer performs multiple, parallel, signatures over the
   document and provides them all to the verifier.  The verifier's job
   is to check that all signatures are valid.

   The general concept is straight-forward, but the devil is in the
   details.

1.1.  Formal Security Requirements

   A solution to the PQ multi-signature problem MUST meet the following
   "security" properties:

   o  S1.  In order to break the overall signature, an attacker must
      break all the signatures.

   o  S2.  Robust to stripping and substitution attacks, which in most
      cases reduces to the following statement: the verifier needs a way
      to know which and how many signature algorithms to expect on a
      given message.

   A solution to the PQ multi-signature problem MAY meet the following
   "desirable" properties, depending on context of the protocol in which

Ounsworth                Expires March 20, 2020                 [Page 2]
Internet-Draft       PQ PKIX Sigs Problem Statement       September 2019

   the signature is being performed.  And yes, some of these conflict
   with each other:

   o  D1.  The set of signing algorithms is negotiated dynamically
      between client and server.

   o  D2.  Since post-quantum public keys and signatures are large, they
      should only be sent when you know the client will verify them.
      For bonus points, the protocol should control when and how the