Internet-Draft QSC Cryptography Key Information November 2021
Vredendaal, et al. Expires 13 May 2022 [Page]
Workgroup:
Internet Engineering Task Force
Individual-Draft:
draft-uni-qsckeys-00
Published:
Intended Status:
Informational
Expires:
Authors:
C.v.V. Vredendaal, Ed.
NXP Semiconductors
S.D. Dragone, Ed.
IBM Research GmbH
B.H. Hess, Ed.
IBM Research GmbH
T.V. Visegrady, Ed.
IBM Research GmbH
M.O. Osborne, Ed.
IBM Research GmbH
D.B. Bong, Ed.
Utimaco IS GmbH
J.B. Bos, Ed.
NXP Semiconductors

Quantum Safe Cryptography Key Information

Abstract

This proposal addresses key identification, key serialization, and key compression for Quantum Safe Cryptographic (QSC) algorithms currently under evaluation in the NIST Post Quantum Cryptography (PQC) process. The purpose of this proposal is to simplify the management of key material for algorithms as they evolve through standardization phases into production. Early definition of key material standards will help expedite the adoption of new quantum safe algorithms at the same time as improving interoperability between implementations and minimizing divergence across standards.

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 13 May 2022.

Table of Contents

1. Introduction

QSC algorithms being standardized in the NIST PQC Process have evolved through several rounds and iterations. Keys are neither easily identifiable nor compatible across rounds. It is also expected that algorithms will evolve after final candidates have been selected. The lack of binary compatibility between algorithm versions and variants means that it is important to clearly identify key material. Parallel to the NIST process, industry is evaluating the impact of adopting new PQC algorithms, in particular key management. Here it is important to define and standardize key serialization and encoding formats. Finally, we have seen that many platforms and protocols are very constrained when it comes to the amount of memory or space available for key objects. This makes it important to define and standardize key compression formats. This proposal addresses aspects of key identification, key serialization, and key compression for NIST PQC candidates.

1.1. Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119] .

1.2. Algorithm Identification

Algorithm identification is important for several reasons:

The current standardization of quantum-safe algorithms does not address the definition of serialization structures for keys. As a result, it has become commonplace for the cryptographic community working on and with these algorithms to define their own approaches. This leads to proprietary and internal representations for key material. This has certain advantages in terms of ease of experimentation while focusing on finding the best-performing QSC algorithms. In terms of longer-term support where algorithm versions change this is a problem. For the purpose of temporarily supporting ongoing experimentation with opaque blobs, for example in simple "classic key-emulating" test applications, such as TLS, this document specifies a temporary but suboptimal key format in section 2.1, mainly to establish a base of reference for as long as experimentation is ongoing. This is referenced as the 'raw key material' representation. At the same time, this proposal documents in section 2.2 below, a long-term key representation format useful to address the goals outlined in 1.1. This proposal contains all information required to document and transition from one version of key material representation to another.

1.3. Algorithm and Algorithm Parameter Object Identifier

Algorithm and algorithm parameter information shall have ASN.1 type AlgorithmIdentifier as given in [RFC5280] and shall be extended by an pqcAlgorithmParameterName type in the optional parameters field:


AlgorithmIdentifier  ::=  SEQUENCE  {
algorithm  OBJECT IDENTIFIER, - OID: algorithm and algo parameter
parameters pqcAlgorithmParameterName OPTIONAL
}
pqcAlgorithmParameterName ::= PrintableString

2. Overview of PQC algorithm and parameter OIDs

Each PQC algorithm has its own specific parameters. Different parameter sets provide different levels of security within one algorithm. This memo attributes a name and an OID to the different security level NIST round 3 parameter sets. The following table gives an overview of the possible OIDs in the algorithm field and possible parameters set names in the parameters field of the AlgorithmIdentifier type. Each name or OID represents a single parameter set of given security. Details can be found in the individual PQC algorithm chapters.


|=========+=====+===============================================|
| Classic McEliece (PQC KEM)                                    |
|=========+=====+===============================================|
| qc-kem-mceliece (PQC KEM)                                     |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*..pqc-kem-mceliece .. }                   |
|         |dot  |                                               |
|=========+=====+===============================================|
| Crystals-Kyber (PQC KEM)                                      |
|=========+=====+===============================================|
| kyber-512-r3                                                  |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-kem-kyber kyber-512-r3 }           |
|         |dot. | 1.3.6.1.4.1.2.267.8.2.2                       |
|---------+-----+-----------------------------------------------|
| kyber-512-90s-r3                                              |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-kem-kyber kyber-512-90s-r3}        |
|         |dot  | 1.3.6.1.4.1.2.267.10.2.2                      |
|---------------+-----+-----------------------------------------|
| kyber-768-r3                                                  |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-kem-kyber kyber-768-r3 }           |
|         |dot  | 1.3.6.1.4.1.2.267.8.3.3                       |
|---------------+-----+-----------------------------------------|
| kyber-768-90s-r3                                              |
|---------------+-----+-----------------------------------------|
|         |ASN.1| {..*.. pqc-kem-kyber kyber-768-90s-r3 }       |
|         |dot  | 1.3.6.1.4.1.2.267.10.3.3                      |
|---------+-----+-----------------------------------------------|
| kyber-1024-r3                                                 |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-kem-kyber kyber-1024-r3 }          |
|         |dot  | 1.3.6.1.4.1.2.267.8.4.4                       |
|---------+-----+-----------------------------------------------|
| kyber-1024-90s-r3                                             |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-kem-kyber kyber-1024-90s-r3}       |
|         |dot  | 1.3.6.1.4.1.2.267.10.4.4                      |
|=========+=====+===============================================|
| NTRU (PQC KEM)                                                |
|=========+=====+===============================================|
| ntruhps2048509-r3                                             |
|---------+-----+-----------------------------------------------|
|         |ASN.1| { pqc-kem-ntru ntruhps2048509 }               |
|         |dot  |                                               |
|---------+-----+-----------------------------------------------|
| ntruhps204867                                                 |
|---------+-----+-----------------------------------------------|
|         |ASN.1| { ..*.. pqc-kem-ntru ntruhps204867            |
|         |dot. |                                               |
|---------+-----+-----------------------------------------------|
| ntruhps4096821                                                |
|---------+-----+-----------------------------------------------|
|         |ASN.1| { ..*.. pqc-kem-ntru ntruhps4096821 }         |
|         |dot  |                                               |
|---------+-----+-----------------------------------------------|
| ntruhrss701                                                   |
|---------+-----+-----------------------------------------------|
|         |ASN.1| { ..*.. pqc-kem-ntru ntruhrss701 }            |
|         |dot  |                                               |
|=========+=====+===============================================|
| SABER ((PQC KEM)                                              |
|=========+=====+===============================================|
| pqc-kem-saber                                                 |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-kem-saber .. }                     |
|         |Dot  |                                               |
|=========+=====+===============================================|
| Crystals-Dilithium (PQC Digital Signature)                    |
|=========+=====+===============================================|
| dilithium-4x4-r3                                              |
|---------+-----+-----------------------------------------------|
|         |ASN.1|{..*.. pqc-ds-dilithium dilithium-4x4-r3}      |
|         |dot  | 1.3.6.1.4.1.2.267.7.4.4                       |
|---------------+-----+-----------------------------------------|
| dilithium-4x4-aes-r3                                          |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-ds-dilithium dilithium-4x4-aes-r3} |
|         | dot |                                               |
|---------+-----+-----------------------------------------------|
| dilithium-6x5-r3                                              |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-ds-dilithium dilithium-6x5-r3}     |
|         | Dot | 1.3.6.1.4.1.2.267.7.6.5                       |
|---------+-----+-----------------------------------------------|
| dilithium-6x5-aes-r3                                          |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-ds-dilithium dilithium-6x5-aes-r3} |
|         | Dot |                                               |
|---------+-----+-----------------------------------------------|
| dilithium-8x7-r3                                              |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-ds-dilithium dilithium-8x7-r3}     |
|         |Dot  | 1.3.6.1.4.1.2.267.7.8.7                       |
|---------+-----+-----------------------------------------------|
| dilithium-8x7-aes-r3                                          |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-ds-dilithium dilithium-8x7-aes-r3} |
|         |dot. |                                               |
|=========+=====+===============================================|
| FALCON (PQC Digital Signature)                                |
|=========+=====+===============================================|
| falcon512-r3                                                  |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-ds-falcon falcon512-r3}            |
|         |dot. |                                               |
|---------+-----+-----------------------------------------------|
| falcon1024-r3                                                 |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-ds-falcon falcon1024-r3}           |
|         |Dot  |                                               |
|=========+=====+===============================================|
| Rainbow (PQC Digital Signature)                               |
|=========+=====+===============================================|
| pqc-ds-rainbow                                                |
|---------+-----+-----------------------------------------------|
|         |ASN.1| {..*.. pqc-ds-rainbow .. }                    |
|         |dot. |                                               |
|=========+=====+===============================================|

Figure 1

2.1. Key Formats

The Secret Key Format defined is from PKCS#8 [RFC5208] . PKCS#8 PrivateKeyInfo is defined as:


PrivateKeyInfo ::=  SEQUENCE {
    version               INTEGER             -- PKCS#8 syntax ver
    privateKeyAlgorithm   AlgorithmIdentifier -- see chapter above
    privateKey            OCTET STRING,       -- see chapter below
    attributes            [0]  IMPLICIT Attributes OPTIONAL
}

Distributing a PQC private key requires a PKCS#8 PrivateKeyInfo with a joined PQC algorithm and algorithm parameter OID in the algorithm field of AlgorithmIdentifier and a PQC algorithm specific private key object in the privateKey field of PrivateKeyInfo. Both objects are defined in the specific algorithm sections of this document. For an overview see tables above and below.

2.2. Public Key Format based on [RFC5480]

RFC5480 subjectPublicKeyInfo is defined in as:


subjectPublicKeyInfo := SEQUENCE {
    algorithm          AlgorithmIdentifier  -- see chapter above
    subjectPublicKey   BIT STRING           -- see chapter below
}

Distributing a PQC public key requires a [RFC5480] subjectPublicKeyInfo with a joined PQC algorithm and algorithm parameter OID in the algorithm field of AlgorithmIdentifier and a PQC algorithm specific public key object in the subjectPublicKey field of subjectPublicKeyInfo. Both objects are defined in the specific algorithm sections of this document. For an overview see tables above and below.

2.3. Overview of Memo Definitions - PQC Key Formats

The privateKey field in the PrivateKeyInfo type [RFC5480] is an OCTET STRING whose contents are the value of the private key. The interpretation of the content differs from PQC algorithm to algorithm. The subjectPublicKey field in the subjectPublicKeyInfo type RFC 5480 [RFC5480] is a BIT STRING whose contents are the value of the public key. Here also the interpretation of the content differs from PQC algorithm to algorithm.

For an NTRU private key, for example, the content needs to be interpreted according to the NTRUPrivateKey type and for an NTRU public key the content needs to be interpreted according to the NTRUPublicKey type; both are defined in the NTRU chapter below.

3. Classic McEliece

Classic McEliece is an IND-CCA2-secure key encapsulation mechanism (KEM). The KEM is built conservatively from a PKE designed for OW-CPA security, namely Niederreiter's dual version of McEliece's PKE using binary Goppa codes. Project Website: https://classic.mceliece.org/index.html NIST Round 3 Submission: https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/Classic-McEliece-Round3.zip

3.1. Algorithm Parameter Identifiers

Classic McEliece uses OIDs to identify parameters sets for different security strengths.


|=========================+=====================================|
| mceliece348864-r3                                             |
|=========================+=====================================|
| Parameter OID           | {..*.. mceliece348864-r3}           |
| NIST Level Security     | Level 1                             |
|-------------------------|-------------------------------------|
| Parameters              | m=12,n=3488,t=64                    |
|                         | f(z)=z^{12} + z^3 + 1               |
|                         | F(y)=y^{64} + y^3 + y + z           |
|                         | (mu; nu)=(0; 0)                     |
|                         | l = 256                             |
|                         | k=n-mt=2720                         |
|=========================+=====================================|
| mceliece348864f-r3                                            |
|=========================+=====================================|
| Parameter OID           | {..*.. mceliece348864f-r3}          |
| NIST Level Security     | Level 1                             |
|-------------------------|-------------------------------------|
| Parameters              | m=12,n=3488,t=64                    |
|                         | f(z)=z^{12} + z^3 + 1               |
|                         | F(y)=y^{64} + y^3 + y + z           |
|                         | (mu; nu)=(32;64)                    |
|                         | l = 256                             |
|                         | k=n-mt=2720                         |
|=========================+=====================================|
| mceliece460896-r3                                             |
|=========================+=====================================|
| Parameter OID           | {..*.. mceliece460896-r3}           |
| NIST Level Security     | Level 3                             |
|-------------------------|-------------------------------------|
| Parameters              | m=13,n=4608,t=96,                   |
|                         | f(z)=z^{13} + z^4 + z^3 + z + 1     |
|                         | F(y)=y^{96} + y^{10} + y^9 + y^6 + 1|
|                         | (mu; nu)=(0; 0)                     |
|                         | l = 256                             |
|                         | k=n-mt=3360                         |
|=========================+=====================================|
| mceliece460896f-r3                                            |
|=========================+=====================================|
| Parameter OID           | {..*.. mceliece460896f-r3           |
| NIST Level Security     | Level 3                             |
|-------------------------|-------------------------------------|
| Parameters              | m=13,n=4608,t=96,                   |
|                         | f(z)=z^{13} + z^4 + z^3 + z + 1     |
|                         | F(y)=y^{96} + y^{10} + y^9 + y^6 + 1|
|                         | (mu; nu)=(32; 64)                   |
|                         | l = 256                             |
|                         | k=n-mt=3360                         |
|=========================+=====================================|
| mceliece6688128-r3                                            |
|=========================+=====================================|
| Parameter OID           | {..*.. mceliece6688128-r3}          |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | m=13,n=6688,t=128                   |
|                         | f(z)=z^{13} + z^4 + z^3 + z + 1     |
|                         | F(y)=y^{128} + y^7 + y^2 + y + 1    |
|                         | (mu; nu)=(0; 0)                     |
|                         | l = 256                             |
|                         | k=n-mt=5024                         |
|=========================+=====================================|
| mceliece6688128f-r3                                           |
|=========================+=====================================|
| Parameter OID           | {..*.. mceliece6688128f-r3}         |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | m=13,n=6688,t=128                   |
|                         | f(z)=z^{13} + z^4 + z^3 + z + 1     |
|                         | F(y)=y^{128} + y^7 + y^2 + y + 1    |
|                         | (mu; nu)=(32; 64)                   |
|                         | l = 256                             |
|                         | k=n-mt=5024                         |
|=========================+=====================================|
| mceliece6960119-r3                                            |
|=========================+=====================================|
| Parameter OID           | {..*.. mceliece6960119-r3}          |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | m=13,n=6960,t=119                   |
|                         | f(z)=z^{13} + z^4 + z^3 + z + 1     |
|                         | F(y)=y^{119} + y^8 + 1              |
|                         | (mu; nu)=(0; 0)                     |
|                         | l = 256                             |
|                         | k=n-mt=5413                         |
|=========================+=====================================|
| mceliece6960119f-r3                                           |
|=========================+=====================================|
| Parameter OID           | {..*.. mceliece6960119f-r3}         |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | m=13,n=6960,t=119                   |
|                         | f(z)=z^{13} + z^4 + z^3 + z + 1     |
|                         | F(y)=y^{119} + y^8 + 1              |
|                         | (mu; nu)=(32; 64)                   |
|                         | l = 256                             |
|                         | k=n-mt=5413                         |
|=========================+=====================================|
| mceliece8192128-r3                                            |
|=========================+=====================================|
| Parameter OID           | {..*.. mceliece8192128-r3}          |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | m=13,n=8192,t=128                   |
|                         | f(z)=z^{13} + z^4 + z^3 + z + 1     |
|                         | F(y)=y^{128} + y^7 + y^2 + y + 1    |
|                         | (mu; nu)=(0; 0)                     |
|                         | l = 256                             |
|                         | k=n-mt=6528                         |
|=========================+=====================================|
| mceliece8192128f-r3                                           |
|=========================+=====================================|
| Parameter OID           | {..*.. mceliece8192128f-r3}         |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | m=13,n=8192,t=128                   |
|                         | f(z)=z^{13} + z^4 + z^3 + z + 1     |
|                         | F(y)=y^{128} + y^7 + y^2 + y + 1    |
|                         | (mu; nu)=(32; 64)                   |
|                         | l = 256                             |
|                         | k=n-mt=6528                         |
|=========================+=====================================|

Figure 2

3.2. Key Details

Public key. The public-key consists of * T: mt x k matrix Each row of T is represented as a ceiling(k/8)-byte string, and the public key is represented as the mt*ceiling(k/8)-byte concatenation of these strings. Secret key. The secret key consists of five parameters:

The size necessary to hold all secret key elements accounts to ceiling(l / 8) + [ceiling(nu / 8) | 8] + ceiling(m / 8) + ceiling((2*m - 1) * 2*m - 4) + ceiling(n / 8) bytes. The resulting public key and private key sizes can be found in the table below.


|=====================+=================+================|
| Parameter Set.      | Size of the     | Size of the    |
|                     | public key      | secret key     |
|                     | in bytes.       | in bytes       |
|=====================+=================+================|
| mceliece348864-r3   |       261120    |       6492     |
| mceliece348864f-r3  |       261120    |       6492     |
| mceliece460896-r3   |       524160    |      13608     |
| mceliece460896f-r3  |       524160    |      13608     |
| mceliece6688128-r3  |      1044992    |      13932     |
| mceliece6688128f-r3 |      1044992    |      13932     |
| mceliece6960119-r3  |      1047319    |      13948     |
| mceliece6960119f-r3 |      1047319    |      13948     |
| mceliece8192128-r3  |      1357824    |      14120     |
| mceliece8192128f-r  |      1357824    |      14120     |
|=====================+=================+================|

Figure 3

3.3. Secret Key Full Encoding

Distributing a Classic McEliece private key with PKCS#8 involves including:

When a Classic McEliece public key is included in the distributed PrivateKeyInfo, the PublicKey field in McEliecePrivateKey is used (see description of McEliecePublicKey below). ASN.1 Encoding for a Classic McEliece private key for fully populated:


McEliecePrivateKey ::= SEQUENCE {
    Version    INTEGER {v0(0)} -- version (round 3)
    delta      OCTET STRING,   -- nonce
    C          OCTET STRING,   -- column selections
    g          OCTET STRING,   -- monic irreducible polynomial
    alpha      OCTET STRING,   -- field orderings
    s          OCTET STRING,   -- random n-bit string
    PublicKey  [0] IMPLICIT McEliecePublicKey OPTIONAL
                                -- see next section
}

3.4. Public Key Full Encoding


Classic McEliece Public Key Format
    McEliecePublicKey ::= SEQUENCE {
    T       OCTET STRING    -- public key
}

4. Kyber

Kyber is an IND-CCA2-secure key encapsulation mechanism (KEM), whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices. Project Website: https://pq-crystals.org/kyber/index.shtml NIST Round 3 Submission: https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/Kyber-Round3.zip

4.1. Algorithm Parameter Identifiers

Kyber uses OIDs to identify parameters sets for different security strengths.


|=========================+=====================================|
| kyber-512-r3                                                  |
|=========================+=====================================|
| Parameter OID           | {..*.. kyber-512-90s-r3}            |
|                         | 1.3.6.1.4.1.2.267.8.2.2             |
| NIST Level Security     | Level 1                             |
|-------------------------|-------------------------------------|
| Parameters              | n= 256,                             |
|                         | k=2                                 |
|                         | q=3329                              |
|                         | nu_1=3                              |
|                         | nu_2=2                              |
|                         | (d_u, d_v)=(10, 4)                  |
|                         | delta=2^{-139}                      |
|=========================+=====================================|
| kyber-512-90s-r3                                              |
|=========================+=====================================|
| Parameter OID           | {..*.. kyber-512-90s-r3}            |
|                         | 1.3.6.1.4.1.2.267.10.2.2            |
| NIST Level Security     | Level 1                             |
|-------------------------|-------------------------------------|
| Parameters              | n= 256,                             |
|                         | k=2                                 |
|                         | q=3329                              |
|                         | nu_1=3                              |
|                         | nu_2=2                              |
|                         | (d_u, d_v)=(10, 4)                  |
|                         | delta=2^{-139}                      |
|=========================+=====================================|
| kyber-768-r3                                                  |
|=========================+=====================================|
| Parameter OID           | {..*.. kyber-768-r3}                |
|                         | 1.3.6.1.4.1.2.267.8.3               |
| NIST Level Security     | Level 3                             |
|-------------------------|-------------------------------------|
| Parameters              | n= 256,                             |
|                         | k=3                                 |
|                         | q=3329                              |
|                         | nu_1=2                              |
|                         | nu_2=2                              |
|                         | (d_u, d_v)=(10, 4)                  |
|                         | delta=2^{-164}                      |
|=========================+=====================================|
| kyber-768-90s-r3                                              |
|=========================+=====================================|
| Parameter OID           | {..*.. kyber-768-90s-r3}            |
|                         | 1.3.6.1.4.1.2.267.10.3.3            |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | n= 256,                             |
|                         | k=3                                 |
|                         | q=3329                              |
|                         | nu_1=2                              |
|                         | nu_2=2                              |
|                         | (d_u, d_v)=(10, 4)                  |
|                         | delta=2^{-164}                      |
|=========================+=====================================|
| kyber-1024-r3                                                 |
|=========================+=====================================|
| Parameter OID           | {..*.. kyber-1024-r3}               |
|                         | 11.3.6.1.4.1.2.267.8.4.4            |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | n= 256,                             |
|                         | k=4                                 |
|                         | q=3329                              |
|                         | nu_1=2                              |
|                         | nu_2=2                              |
|                         | (d_u, d_v)=(11, 5)                  |
|                         | delta=2^{-174}                      |
|=========================+=====================================|
| kyber-1024-90s-r3                                             |
|=========================+=====================================|
| Parameter OID           | {..*.. kyber-1024-90s-r3}           |
|                         | 1.3.6.1.4.1.2.267.10.4.4            |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | n= 256,                             |
|                         | k=4                                 |
|                         | q=3329                              |
|                         | nu_1=2                              |
|                         | nu_2=2                              |
|                         | (d_u, d_v)=(11, 5)                  |
|                         | delta=2^{-174}                      |
|=========================+=====================================|

Figure 4

The '90s' variants listed above differ in the symmetric primitives that are used internally. By default, Kyber uses SHAKE-128 as XOF, SHA3 for hashing and SHAKE-256 for PRF and KDF. The '90s' variants use AES256CTR to construct a XOF and a PRF, SHA2 for hashing and SHAKE-256 as KDF. The main advantage of the '90s' variants is that they benefit from the ready availability of hardware AES and SHA2 co-processors. While the parameters listed in the table are the same, the key-pairs will not be compatible with the '90s' variants.

4.2. Key Details

Public key. The public-key consists of two parameters:

The size necessary to hold all public key elements is 12*k*n/8+32 bytes. Secret key. The secret key consists of 3 parameters:

If the secret key is fully populated, it consists of 3 parameters. The size necessary to hold all secret key elements accounts to 12*k*n/8+64 bytes, not counting the optional public key. The resulting public key and private key sizes are shown in the following table.


|==========================+=========+==========+=========|
| Algorithm OID            | Public  |   Secret |  Secret |
|                          | Key     |   Key    |  Key    |
|                          |         |          |(partial)|
|==========================+=========+==========+=========|
| kyber512-r3 /            |   800   |   832    |    32   |
| kyber512-90s-r3          |         |          |         |
|--------------------------|---------|----------|---------|
| kyber768-r3 /            |  1184   |   1216   |    32   |
| kyber768-90s-r3          |         |          |         |
|--------------------------|--------------------|---------|
| kyber1024-r3 /           |  1568   |   1600   |    32   |
| kyber1024-90s-r3         |         |          |         |
|==========================+=========+==========+=========|

Figure 5

4.3. Secret Key Full Encoding

Distributing a Kyber private key with PKCS#8 requires:

When a Kyber public key is included in the distributed PrivateKeyInfo, the PublicKey field in KyberPrivateKey is used (see description of KyberPublicKey below). The ASN.1 encoding for a Kyber private key is defined as follows:


KyberPrivateKey ::= SEQUENCE {
    Version     INTEGER {v0(0)}   -- version (round 3)
    nonce       OCTET STRING,     -- z
    s           OCTET STRING,     -- sample s
    PublicKey   [0] IMPLICIT KyberPublicKey OPTIONAL,
                                  -- see next section
    hpk         OCTET STRING      -- H(pk)
}

4.4. Secret Key Partial Encoding

The partially populated parameter set uses of the fact that some parameters can be regenerated. In this case, only the initial seed 'd' (nonce) is stored and used to regenerate the full key. Partially encoded keys use the same ASN.1 structure as the fully polulated keys, simply with the regenerated fields set to EMPTY. Compared to the approach of a single definition and setting the regenratable fields as OPTIONAL, this approach significantly simplifies the processing os ASN.1 frames and validation of the partial encoding. The ASN.1 format for the partially populated versions is the same as for the fully populated version. The ASN.1 encoding for this variant (z replaced by d) is defined as follows:


KyberPrivateKey ::= SEQUENCE {
    version     INTEGER {v0(0)}   -- version (round 3)
    nonce       OCTET STRING,     -- d
    s           OCTET STRING,     -- EMPTY
    PublicKey   [0] IMPLICIT KyberPublicKey OPTIONAL,
                                  -- see next section
    hpk         OCTET STRING      -- EMPTY
}

4.5. Public Key Full Encoding

The vector 't' is encoded using the function Encode_12, defined as the inverse of Decode_12 as defined in Algorithm 3 of the Kyber round 3 specification. The size of t is 12*k*n/8 bytes. The seed 'rho' is a 32 byte OCTET STRING.


KyberPublicKey ::= SEQUENCE {
    t           OCTET STRING,
    rho         OCTET STRING
}

5. NTRU

NTRU is a key encapsulation mechanism (KEM), whose security is based on the hardness of solving the Shortest Vector Problem in NTRU lattices. Project Website: https://ntru.org/ NIST Round 3 Submission: https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/NTRU-Round3.zip

5.1. Algorithm Parameter Identifiers

Below are the NTRU parameter sets. Note that the definition of local/non-local security is out of scope for this document, but can be found in the NTRU NIST Round 3 Submission.


|=========================+=====================================|
| ntruhps2048509-r3                                             |
|=========================+=====================================|
| Parameter OID           | {..*.. ntruhps2048509-r3}           |
|                         |  <.>                                |
| NIST Level Security     | Level 1                             |
|-------------------------|-------------------------------------|
| Parameters              | Dimension/Degree n= 509             |
|                         | Polynomial  Phin= (xn - 1)/(x-1     |
|                         | Polynomial  Phi1=(x-1)              |
|                         | Modulus p=3                         |
|                         | Modulus q= 2048                     |
|=========================+=====================================|
| ntruhps2048677-r3                                             |
|=========================+=====================================|
| Parameter OID           | {..*.. ntruhps2048677-r3}           |
|                         | <.  >                               |
| NIST Level Security     | Level 3 (1) see spec.               |
|-------------------------|-------------------------------------|
| Parameters              | Dimension/Degree n= 677             |
|                         | Polynomial  Phin= (xn - 1)/(x-1)    |
|                         | Polynomial  Phi1=(x-1)              |
|                         | Modulus p=3                         |
|                         | Modulus q= 2048                     |
|=========================+=====================================|
| ntruhps4096821-r3                                             |
|=========================+=====================================|
| Parameter OID           | {..*.. ntruhps4096821-r3}           |
|                         | <.>                                 |
| NIST Level Security     | Level 3 (1) see spec.               |
|-------------------------|-------------------------------------|
| Parameters              | Dimension/Degree n= 821             |
|                         | Polynomial  Phin= (xn - 1)/(x-1)    |
|                         | Polynomial  Phi1=(x-1)              |
|                         | Modulus p=3                         |
|                         | Modulus q= 4096                     |
|=========================+=====================================|
| ntruhrss701-r3                                                |
|=========================+=====================================|
| Parameter OID           | {..*.. ntruhrss701-r3}              |
|                         | <.>                                 |
| NIST Level Security     | Level 5 (3)  see spec.              |
|-------------------------|-------------------------------------|
| Parameters              | Dimension/Degree n= 701             |
|                         | Polynomial  Phin= (xn - 1)/(x-1)    |
|                         | Polynomial  Phi1=(x-1)              |
|                         | Modulus p=3                         |
|                         | Modulus q= 8192                     |
|=========================+=====================================|

Figure 6

The parameter sets differ in the degree of the polynomial n and the modulus q.

5.2. Key Details

Public key. The public-key consists of a single parameter :

This means there are n - 1 coefficients of size at most q in the public key, and the size necessary to store the polynomial is therefore is ceiling((n - 1)?log2(q)/8) bytes. The resulting sizes for the parameter sets can be found in the Table below. Secret key. The secret key consists of 4 parameters:

This means there are 2 polynomials, f and fp, having n - 1 coefficients with absolute value at most 1 in the secret key. For these polynomials, the packing algorithm in Section 1.8.7 of the Specification allows to pack 5 coefficients in a byte, so the storage requirement to store each is ceiling((n - 1)/5) bytes. Additionally hq is part of the secret key, which requires the same storage size as that of the public key h, i.e. ceiling((n - 1)?log2(q)/8) bytes. For the seed bytes, the specification recommends:

Implementers may choose to expand the seed from one 32-byte seed. The resulting sizes for the parameter sets can be found in the Table below. Where the seed expansion is omitted, the 32-byte seed must be replaced by key_seed_bits=sample_key_bits+prf_key_bits. The impact of these options are indicated as 32-byte seed/expanded seed in the Table below. Parameter Set Size of the public key in bytes Size of the secret key in bytes


|=====================+==============================|
| ntruhps2048509-r3                                  |
|---------------------|------------------------------|
| Public Key (Bytes)  | 699                          |
| seed/expanded seed  | 935 / 3348                   |
| f,fp,hq,seed        | 102,102,699,32/2445          |
|=====================+==============================|
| ntruhps2048677-r3                                  |
|---------------------|------------------------------|
| Public Key (Bytes)  | 699                          |
| seed/expanded seed  | 935 / 3348                   |
| f,fp,hq,seed        | 102,102,699,32/2445          |
|=====================+==============================|
| ntruhps2048677-r3                                  |
|---------------------|------------------------------|
| Public Key (Bytes)  |    930                          |
| seed/expanded seed  | 1234 / 4445                  |
| (f,fp,hq,seed)      | 136,136,930,32/3243          |
|=====================+==============================|
| ntruhps4096821-r3                                  |
|---------------------|------------------------------|
| Public Key (Bytes)  | 1230                         |
| seed/expanded seed  | 1590 / 5485                  |
| (f,fp,hq,seed)      | 164,164,1230,32/3927         |
|=====================+==============================|
| ntruhrss701-r3                                     |
|---------------------|------------------------------|
| Public Key (Bytes)  | 1138                         |
| seed/expanded seed  | 1450 / 2850                  |
| (f,fp,hq,seed)      | 140,140,1138,32/1432         |
|=====================+==============================|

Figure 7

5.3. Secret Key Full Encoding

An NTRU private key encoded according with PKCS#8 MUST include the following two fields:

When a NTRU public key is included in the distributed PrivateKeyInfo, the PublicKey field in NTRUPrivateKey is used (see description of NTRUPublicKey below). An NTRU secret key contains f, fp and hq, as well as a seed. The octet string format indicates the length of the string to follow, and indicates whether the seed or expanded seed is used.


NTRUPrivateKey ::= SEQUENCE {
    version    INTEGER  {v0(0)}    -- version (round 3)
    f          OCTET STRING,      -- short integer polynomial f
    fp         OCTET STRING,      -- short integer polynomial gp
    hq         OCTET STRING,      -- mod q integer polynomial hq
    seed       OCTET STRING,      -- fg_bits/prf_bits (or their seed)
    PublicKey [0] IMPLICIT NTRUPublicKey OPTIONAL -- see next section
}

5.4. Public Key Full Encoding

From the NTRU specification, the public key contains h. Each coefficient of h is encoded as an ? bit sequence, where ?=ceiling((n - 1)?log2(q)). Coefficients are then concatenated (two's complement, big endian convention). The final bit string is zero padded to fit into a byte sequence. NTRUPublicKey := SEQUENCE { h OCTET STRING -- integer polynomial h }

6. SABER

SABER is a family of cryptographic primitives that rely on the hardness of the Module Learning with Rounding problem (M-LWR). Project Website: https://www.esat.kuleuven.be/cosic/pqcrypto/saber/ NIST Round 3 Submission: https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/SABER-Round3.zip

6.1. Algorithm Parameter Identifiers

Saber has three parameter sets shown in the table below


|=========================+=====================================|
| LightSaber-r3                                                 |
|=========================+=====================================|
| Parameter OID           | {..*.. lightsaber-r3}               |
|                         |  <.>                                |
| NIST Level Security     | Level 1                             |
|-------------------------|-------------------------------------|
| Parameters              | Degree n= 256                       |
|                         | rank of the module ?= 2             |
|                         | binomial distribution with u=10     |
|                         | Modulus q=2^{13} and p=2^{10}       |
|=========================+=====================================|
| Saber-r3                                                      |
|=========================+=====================================|
| Parameter OID           | {..*.. saber-r3}                    |
|                         |  <.>                                |
| NIST Level Security     | Level 3                             |
|-------------------------|-------------------------------------|
| Parameters              | Degree n= 256                       |
|                         | rank of the module ?= 3             |
|                         | binomial distribution with u=8      |
|                         | Modulus q=2^{13} and p=2^{10}       |
|=========================+=====================================|
| FireSaber-r3                                                  |
|=========================+=====================================|
| Parameter OID           | {..*.. firesaber-r3}                |
|                         |  <.>                                |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | Degree n= 256                       |
|                         | rank of the module ?= 4             |
|                         | binomial distribution with u=6      |
|                         | Modulus q=2^{13} and p=2^{10}       |
|=========================+=====================================|

Figure 8

The rank of the module is denoted ? and differs per parameter set.

6.2. Key Details

Public key. The public-key consists of the following two parameters:

This means the size of the public key can be stored using ?*256*10+256 bits. The size of the public key as used in the three parameter sets can be found in the Table below.

Secret key. The secret key s consists of three parameters:

This means the secret key can be stored using 512+?*256*13 bits. The size of the secret key as used in the three parameter sets can be found in the Table below.


|==========================+=========+==========|
| Algorithm                | Public  |   Secret |
|                          | Key     |   Key    |
|                          | Length  |   Length |
|==========================+=========+==========+
| LightSaber-r3            |    672  |    896   |
| Saber-r3                 |    992  |   1312   |
| FireSaber-r3             |   1312  |   1728   |
|==========================+=========+==========|

Figure 9

6.3. Secret Key Full Encoding

A SABER private key encoded according with PKCS#8 MUST include the following two fields:

When a SABER public key is included in the distributed PrivateKeyInfo, the PublicKey field in SABERPrivateKey is used (see the description below).


SABERPrivateKey ::= SEQUENCE {
    version     INTEGER  {v0(0)}    -- version (round 3)
    z           OCTET STRING,       -- 32-byte random value z
    s           OCTET STRING,       -- short integer polynomial s
    PublicKey   [0] IMPLICIT SABERPublicKey OPTIONAL,
                                    -- see next section
    hpk         OCTET STRING        -- H(pk)
}

6.4. Public Key Full Encoding


SABERPublicKey := SEQUENCE {
    seed_A      OCTET STRING,        -- 32-byte seed
    b           OCTET STRING         -- short integer polynomial b
}

7. CRYSTALS-DILITHIUM

Dilithium is a digital signature scheme that is based on the hardness of lattice problems over module lattices. Project Website: https://pq-crystals.org/dilithium/index.shtml NIST Round 3 Submission (version 3.1): https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/Dilithium-Round3.zip https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf

7.1. Algorithm Parameter Identifiers

Dilithium uses OIDs to identify parameters sets for different security strengths.


|=========================+=====================================|
| dilithium-4x4-r3                                              |
|=========================+=====================================|
| Parameter OID           | {..*.. dilithium-4x4-r3}            |
|                         | 1.3.6.1.4.1.2.267.7.4.4             |
| NIST Level Security     | Level 2                             |
|-------------------------|-------------------------------------|
| Parameters              | Polynomial Ring Zq[x]/( x^n +1)     |
|                         | Dimension/Degree n= 256             |
|                         | Modulus q=8380417                   |
|                         | Dropped bits from t: d=13           |
|                         | # of +-1's in c: tau=39             |
|                         | challenge entropy=192               |
|                         | gamma coefficient range: gamma1=2^17|
|                         | low-order rounding range: gamma2=(q-|
|                         | 1)/88                               |
|                         | Secret Key Range (nu)=2             |
|                         | Dimensions of A: (k,l)=(4,4)        |
|                         | Max # of 1's in the hint h: w=80    |
|                         | Repetitions=4.25                    |
|=========================+=====================================|
| dilithium-4x4-aes-r3                                          |
|=========================+=====================================|
| Parameter OID           | {..*.. dilithium-4x4-aes-r3}        |
|                         | <.>                                 |
| NIST Level Security     | Level 2                             |
|-------------------------|-------------------------------------|
| Parameters              | Polynomial Ring Zq[x]/( x^n + 1 )   |
|                         | Dimension/Degree n= 256             |
|                         | Modulus q=8380417                   |
|                         | Dropped bits from t: d=13           |
|                         | # of +-1's in c: tau=39             |
|                         | challenge entropy=192               |
|                         | y coefficient range: gamma1=2^17    |
|                         | low-order rounding range:gamma2=(q- |
|                         | -1)/88                              |
|                         | Secret Key Range (nu)=2             |
|                         | Dimensions of A: (k,l)=(4,4)        |
|                         | Max # of 1's in the hint h: w=80    |
|                         | Repetitions=4.25                    |
|=========================+=====================================|
| dilithium-6x5-r3                                              |
|=========================+=====================================|
| Parameter OID           | {..*.. dilithium-6x5-r3}            |
|                         | 1.3.6.1.4.1.2.267.7.6.5             |
| NIST Level Security     | Level 3                             |
|-------------------------|-------------------------------------|
| Parameters              | Polynomial Ring Zq[x]/( x^n + 1 )   |
|                         | Dimension/Degree n= 256             |
|                         | Modulus q=8380417                   |
|                         | Dropped bits from t: d=13           |
|                         | # of +-1's in c: ?=49               |
|                         | challenge entropy=225               |
|                         | y coefficient range: gamma1=2^19    |
|                         | low-order rounding range:gamma2=(q- |
|                         | -1)/32                              |
|                         | Secret Key Range (nu)=4             |
|                         | Dimensions of A: (k,l)=(6,5)        |
|                         | Max # of 1's in the hint h: w=55    |
|                         | Repetitions=5.1                     |
|=========================+=====================================|
| dilithium-6x5-aes-r3                                          |
|=========================+=====================================|
| Parameter OID           | {..*.. dilithium-6x5-aes-r3}        |
|                         | <.>                                 |
| NIST Level Security     | Level 3                             |
|-------------------------|-------------------------------------|
| Parameters              | Polynomial Ring Zq[x]/( x^n +1 )    |
|                         | Dimension/Degree n= 256             |
|                         | Modulus q=8380417                   |
|                         | Dropped bits from t: d=13           |
|                         | # of +-1's in c: tau=49             |
|                         | challenge entropy=225               |
|                         | y coefficient range: gamma1=2^19    |
|                         | low-order rounding range:gamma2=(q- |
|                         | -1)/32                              |
|                         | Secret Key Range (nu)=4             |
|                         | Dimensions of A: (k,l)=(6,5)        |
|                         | Max # of 1's in the hint h: w=55    |
|                         | Repetitions=5.1                     |
|=========================+=====================================|
| dilithium-8x7-r3                                              |
|=========================+=====================================|
| Parameter OID           | {..*.. dilithium-8x7-r3}            |
|                         | 1.3.6.1.4.1.2.267.7.8.7             |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | Polynomial Ring Zq[x]/( x^n + 1 )   |
|                         | Dimension/Degree n= 256             |
|                         | Modulus q=8380417                   |
|                         | Dropped bits from t: d=13           |
|                         | # of +-1's in c: tau=60             |
|                         | challenge entropy=257               |
|                         | y coefficient range: ?1=2^19        |
|                         | low-order rounding range:gamma2=(q- |
|                         | -1)/32                              |
|                         | Secret Key Range (nu)=2             |
|                         | Dimensions of A: (k,l)=(8,7)        |
|                         | Max # of 1's in the hint h: w=75    |
|                         | Repetitions=3.85                    |
|=========================+=====================================|
| dilithium-8x7-aes-r3                                          |
|=========================+=====================================|
| Parameter OID           | {..*.. dilithium-8x7-aes-r3}        |
|                         | <.>                                 |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | Polynomial Ring Zq[x]/( x^n + 1 )   |
|                         | Dimension/Degree n= 256             |
|                         | Modulus q=8380417                   |
|                         | Dropped bits from t: d=13           |
|                         | # of +-1's in c: tau=60             |
|                         | challenge entropy=257               |
|                         | y coefficient range: gamma1=2^19    |
|                         | low-order rounding range:gamma2=(q- |
|                         | -1)/32                              |
|                         | Secret Key Range (nu)=2             |
|                         | Dimensions of A: (k,l)=(8,7)        |
|                         | Max # of 1's in the hint h: w=75    |
|                         | Repetitions=3.85                    |
|=========================+=====================================|

Figure 10

The aes variants listed above differ from the other variants in that they use AES, rather than SHAKE internally to expand the key parameters from an initial seed. While the parameters listed in the table are the same, the key-pairs will not be compatible with the 'aes' variants.

7.2. Key Details

Public key. The public-key consists of two parameters:

The size necessary to hold all public key elements accounts to 32+320*k bytes.

Secret key. The secret key consists of 6 parameters:

If the secret key is fully populated, it consists of 6 parameters. The size necessary to hold all secret key elements accounts to 32+32+32+32*[(k+l)*ceiling(log(2*nu+1))+13*k] bytes. The resulting public key and private key sizes can be found in the table below.


|=========================+========+========+=========+=========|
| Algorithm               | Public | Secret | Partial | Partial |
|                         | Key    | Key SK | SK (V1) | SK (V2) |
|                         | Length | Length | Length  | Length  |
|=========================+========+========+=========+=========+
| dilithium-4x4-r3        | 1312   | 2528   |   64    |    32   |
| dilithium-4x4-aes-r3    | 1312   | 2528   |   64    |    32   |
| dilithium-6x5-r3        | 1952   | 4000   |   64    |    32   |
| dilithium-6x5-aes-r3    | 1952   | 4000   |   64    |    32   |
| dilithium-8x7-r3        | 2596   | 4864   |   64    |    32   |
| dilithium-8x7-aes-r3    | 2592   | 4864   |   64    |    32   |
|=========================+========+========+=========+=========|

Figure 11

7.3. Secret Key Full Encoding

A Dilithium private key encoded according with PKCS#8 MUST include the following two fields:

Dilithium public key are optionally distributed in the PublicKey field of the PrivateKeyInfo structure.

ASN.1 Encoding for a Dilithium private key for fully populated:


DilithiumPrivateKey ::= SEQUENCE {
    version     INTEGER {v0(0)}     -- version (round 3)
    nonce       BIT STRING,         -- rho
    key         BIT STRING,         -- key/seed/D
    tr          BIT STRING,         -- PRF bytes (CRH in spec)
    s1          BIT STRING,         -- vector(L)
    s2          BIT STRING,         -- vector(K)
    t0          BIT STRING,
    PublicKey  [0] IMPLICIT DilithiumPublicKey OPTIONAL
                                    -- see next section
}

7.4. Secret Key Partial Encoding Option 1

In option 1 of Dilithium partial encoding the rho (nonce) and the seed (key) are used to regenerate the full key. Note: There are a number of alternative ways to encode a partially filled structure that include defining fields as optional and defining fields as 'EMPTY'. As an example partial RSA keys are encoded using EMPTY fields. It can be argued that defining fields as EMPTY significantly simplifies the implementation of parsing ASN.1 frames. The ASN.1 format for the partially populated versions is the same as for the fully populated version. The ASN.1 encoding for the first variant (rho and seed) is defined as follows:


DilithiumPrivateKey ::= SEQUENCE {
    version     INTEGER {v0(0)}     -- version (round 3)
    nonce       BIT STRING,         -- rho
    key         BIT STRING,         -- key/seed/D
    tr          BIT STRING,         -- EMPTY
    s1          BIT STRING,         -- EMPTY
    s2          BIT STRING,         -- EMPTY
    t0          BIT STRING,         -- EMPTY
    PublicKey   [0] IMPLICIT DilithiumPublicKey OPTIONAL
                                    -- see next section
}

7.5. Secret Key Partial Encoding Option 2

In option 2 of Dilithium partial encoding only zeta (nonce) is used to regenerate the full key. The ASN.1 encoding for this is defined as follows:


DilithiumPrivateKey ::= SEQUENCE {
    version     INTEGER {v0(0)}     -- version (round 3)
    nonce       BIT STRING,         -- zeta
    key         BIT STRING,         -- EMPTY
    tr          BIT STRING,         -- EMPTY
    s1          BIT STRING,         -- EMPTY
    s2          BIT STRING,         -- EMPTY
    t0          BIT STRING,         -- EMPTY
    PublicKey   [0] IMPLICIT DilithiumPublicKey OPTIONAL
                                   -- see next section
}

7.6. Public Key Full Encoding

Components are individual OCTET STRINGs, without unused bits, encoded with the exact size. There is no removal of leading zeroes.


DilithiumPublicKey ::= SEQUENCE {
    rho         OCTET STRING,
    t1          OCTET STRING
}

8. FALCON

FALCON is a lattice-based signature scheme that uses the short integer solution problem (SIS) over NTRU lattices as its underlying hard problem. Project Website https://falcon-sign.info/ NIST Round 3 Submission https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/Falcon-Round3.zip

8.1. Algorithm Parameter Identifiers


|=========================+=====================================|
| falcon512-r3                                                  |
|=========================+=====================================|
| Parameter OID           | {..*.. falcon512-r3}                |
|                         | <.>                                 |
| NIST Level Security     | Level 1                             |
|-------------------------|-------------------------------------|
| Parameters              | Dimension/Degree n = 512            |
|                         | Polynomial Phi = 1+X{n}             |
|                         | Modulus q = 12289                   |
|                         | Max. signature square norm          |
|                         | floor (beta2) = 34034726            |
|                         | Standard deviation = 165.736617183  |
|                         | sigmamax = 1.8205                   |
|                         | sigmamin = 1.27783369               |
|=========================+=====================================|
| falcon1024-r3                                                 |
|=========================+=====================================|
| Parameter OID           | {..*.. falcon1024-r3}               |
|                         | <.>                                 |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | Dimension/Degree n = 1024           |
|                         | Polynomial Phi = 1+X{n}             |
|                         | Modulus q = 12289                   |
|                         | Max. signature square norm          |
|                         | floor (beta2) = 34034726            |
|                         | Standard deviation = 168.388571447  |
|                         | sigmamax = 1.8205                   |
|                         | sigmamin = 1.298280334              |
|=========================+=====================================|

Figure 12

8.2. Key Details

The FALCON secret key contains the key components f, g and F. Each coefficient of f and g is encoded over a fixed number of bits, which depends on the degree of f and g: 6 bits each for degree 512 (parameter name = falcon512-r3) and 5 bits each for degree 1024 (parameter name = falcon1024-r3). Coefficients of F use 8 bits each, regardless of its degree. Each coefficient uses signed encoding, with two's complement for negative values. Moreover, the minimal value is forbidden, e.g. when using degree 512, the valid range for a coefficient of f or g is ?31 to +31; ?32 is not allowed.


|==========================+=========+==========|
| Algorithm OID            | Params  |   Secret |
|                          |         |   Key    |
|                          |         |   Length |
|==========================+=========+==========+
| falcon512-r3             | f=384   | 1280     |
|                          | g=384   |          |
|                          | F=512   |          |
|--------------------------+---------+----------|
| falcon1024-r3            | f=640   | 2304     |
|                          | g=640   |          |
|                          | F=1024  |          |
|==========================+=========+==========+

Figure 13

8.3. Secret Key Full Encoding

Encoding a FALCON private key with PKCS#8 must include the following two fields:

When a FALCON public key is included in the distributed PrivateKeyInfo, the PublicKey field in FALCONPrivateKey is used (see description of FALCONPublicKey below). ASN.1 Encoding for a FALCON private key:


FALCONPrivateKey ::= SEQUENCE {
    version     INTEGER {v2(1)}    -- syntax version 2 (round 3)
    f           OCTET STRING,      -- short integer polynomial f
    g           OCTET STRING,      -- short integer polynomial g
    F           OCTET STRING,      -- short integer polynomial F
    PublicKey   [0] IMPLICIT FALCONPublicKey  OPTIONAL
                                   -- see next section
}

8.4. Public Key Full Encoding

The FALCON public key contains a series of coefficients encoded into parameter h. Each coefficient of h is encoded as a 14 bit sequence (since q = 12289, 14 bits per coefficient are used). Coefficients are then concatenated. The final bit string is zero padded to fit into a byte sequence.


|==========================+=========+==========|
| Algorithm                | Public Key Length  |
|==========================+====================+
| falcon512-r3             | 896                |
|--------------------------+--------------------|
| falcon1024-r3            | 1792               |
|==========================+====================|

Figure 14

FALCONPublicKey := SEQUENCE {
    h           OCTET STRING       -- integer polynomial h
}

9. Rainbow

Rainbow is a multivariate-based signature scheme that relies on the hardness of solving a set of random multivariate quadratic systems. Project Website: https://www.pqcrainbow.org/ NIST Round Submission: https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/Rainbow-Round3.zip

9.1. Algorithm Parameter Identifiers

The following tables shows Rainbow parameter sets.


|=========================+=====================================|
| rainbowI-r3                                                   |
|=========================+=====================================|
| Parameter OID           | {..*.. rainbowI-r3}                 |
|                         | <.>                                 |
| NIST Level Security     | Level 1 / Level 2  see spec.        |
|-------------------------|-------------------------------------|
| Parameters              | Field F = GF(16)[2]                 |
|                         | u = 2                               |
|                         | v1 = 36                             |
|                         | o1 = 32                             |
|                         | o2 = 32                             |
|                         | n = v2 = 100[3]                     |
|                         | m = n - v1 = 64                     |
|=========================+=====================================|
| rainbowIII-r3                                                 |
|=========================+=====================================|
| Parameter OID           | {..*.. rainbowIII-r3                |
|                         | <.>                                 |
| NIST Level Security     | Level 3 / Level 4.  See spec.       |
|-------------------------|-------------------------------------|
| Parameters              | Field F = GF(256)                   |
|                         | u = 2                               |
|                         | v1 = 68                             |
|                         | o1 = 32                             |
|                         | o2 = 48                             |
|                         | n = v2 = 148                        |
|                         | m = n - v1 = 80                     |
|=========================+=====================================|
| rainbowV-r3                                                   |
|=========================+=====================================|
| Parameter OID           | {..*.. rainbowV-r3}                 |
|                         | <.>                                 |
| NIST Level Security     | Level 5                             |
|-------------------------|-------------------------------------|
| Parameters              | Field F = GF(256)                   |
|                         | u = 2                               |
|                         | v1 = 96                             |
|                         | o1 = 36                             |
|                         | o2 = 64                             |
|                         | n = v2 = 196                        |
|                         | m = n - v1 = 100                    |
|=========================+=====================================|

Figure 15

9.2. Key Details

Public key. The public-key consists of two parameters:

This mapping can be expressed as m quadratic polynomials in the ring F[x1, ... , xn], which means the public key consists of m*(n+1)*(n+2)/2 elements of F. With optimizations (see Rainbow specification), this can be reduced to m*n*(n+1)/2 elements of F. The size necessary to hold all public key elements accounts to m*n*(n+1)/16*f bytes, where f=4 for rainbowI and 8 for rainbowIII and rainbowV. For all parameter sets ell is 16 bytes. Secret key. The secret key consists of 4 parameters:

The affine mappings S and T can respectively be expressed in terms of m*(m+1) and n*(n+1) elements of F. The central map F mapping can be expressed as m multivariate polynomials and be stored as o1*(v1*(v1+1)/2 + v1*o1)+ o2*((v1+ o1)*(v1+o1+1)/2 +(v1+o1)*o2) field elements (see section 4.1 of the Rainbow specification). Rainbow can be instantiated in its CZ-Rainbow form. The key generation method is then inverted. This allows parts of the public key to be fixed and therefore reproduced from a partially stored public key.

Public key - CZ.

The public-key of CZ-Rainbow consists of 3 parameters:

The partial public key now consists of 5 submatrices totaling o1*o2*v1 + o1*o1*(o1+1)/2 +o1*o2*o1 + o1*o2*(o2+1)/2 + o2*o2*(o2+1)/2 elements of F. Additionally the seed spub is 32 bytes. The secret key can also be stored as the seeds of the key generation process spriv (32 bytes) and spub (32 bytes). This is denoted as the compressed key and has a size of total 64 bytes. The resulting public key and private key sizes can be found in the table below.


|=========================+==========+=========|
| Algorithm               | Public   | Secret  |
|                         | Key      | Key     |
|                         | Length   | Length  |
|=========================+==========+=========+
| rainbowI-r3             |  161616  |  103632 |
| rainbowI-r3 (CZ)        |   60208  |      64 |
| rainbowIII-r3           |  882096  |  626032 |
| rainbowIII-r3 (CZ)      |  264624  |      64 |
| rainbowV-r3             | 1930616  | 1408720 |
| rainbowV-r3 (CZ)        |  536152  |      64 |
|=========================+==========+=========|

Figure 16

9.3. Secret Key Full Encoding

A Rainbow private key encoded according with PKCS#8 MUST include the following two fields:

When a Rainbow public key is included in the distributed PrivateKeyInfo, the PublicKey field in RainbowPrivateKey is used (see description of RainbowPublicKey below). ASN.1 Encoding for a fully populated rainbow private key:


RainbowPrivateKey ::= SEQUENCE {
    version    INTEGER {v0(0)}       -- version (round 3)
    S          OCTET STRING,         -- map S
    T          OCTET STRING,         -- map T
    F          OCTET STRING,         -- map F
    ell        OCTET STRING,
    PublicKey  [0] IMPLICIT RainbowPublicKey OPTIONAL
    -- see next section
}

9.4. Secret Key Partial Encoding

A partially populated private key is used when Compressed Rainbow is used. In this case, spriv and spub are used to regenerate the full key. The ASN.1 encoding is then defined as follows:


RainbowPrivateKey ::= SEQUENCE {
    version    INTEGER {v0(0)}  -- version (round 3)
    s_priv     OCTET STRING,    -- seed for private key
    s_pub      OCTET STRING,    -- seed for public key
    ell        OCTET STRING,
    PublicKey  [0] IMPLICIT RainbowPublicKey OPTIONAL
                                -- see next section
}

9.5. Public Key Full Encoding

Public keys can either be distributed stand-alone as subjectPublicKeyInfo or optionally be included in PrivateKeyInfo (::=OneAsymmetricKey) and distributed together with the corresponding private key. Once the RainbowPublicKey below is encoded as OCTET STRING (subjectPublicKey in subjectPublicKeyInfo) and once as BIT STRING (publicKey in OneAsymmetricKey).

The public key for the standard Rainbow scheme consists of an EMPTY spub field, and P consists of encoding of respectively GF(16) and GF(256) field elements appended to form OCTET STRINGS. The CZ variant of rainbow then includes a 32-byte seed spub, which reduces the number of field elements encoded in P.


RainbowPublicKey ::= SEQUENCE {
    s_pub      OCTET STRING      -- (EMPTY)
    P          OCTET STRING,
    ell        OCTET STRING
}

10. Acknowledgements

This template was derived from an initial version written by Pekka Savola and contributed by him to the xml2rfc project.

This document is part of a plan to make xml2rfc indispensable.

11. IANA Considerations

This memo includes no request to IANA.

12. Security Considerations

Any processing of the ASN.1 private key structures, such as base64 en/decoding shall be performed in "constant-time", meaning without secret-dependent control flow and table lookups. The ASN.1 structures in this document are defined with fixed tag-lengths. The purpose is to prevent side-channel leakage of variable lengths during DER parsing. Any DER parsing of the private key ASN.1 key structures shall be performed with these fixed lengths.

13. References

13.1. Normative References

[RFC2119]
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfc-editor.org/info/rfc2119>.
[RFC5208]
Kaliski, B., "Public-Key Cryptography Standards (PKCS) #8: Private-Key Information Syntax Specification Version 1.2", BCP 14, RFC 5208, DOI 10.17487/RFC5208, , <hhttps://www.rfc-editor.org/info/rfc5208>.
[RFC5280]
Cooper, D., "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", BCP 14, RFC RFC5280, DOI 10.17487/RFC5280, , <hhttps://www.rfc-editor.org/info/rfcRFC5280>.
[RFC5480]
Turner, S., "Elliptic Curve Cryptography Subject Public Key Information", BCP 14, RFC RFC5480, DOI 10.17487/RFC5480, , <hhttps://www.rfc-editor.org/info/rfc5480>.

13.2. Informative References

[RFC2629]
Rose, M., "Writing I-Ds and RFCs using XML", RFC 2629, DOI 10.17487/RFC2629, , <https://www.rfc-editor.org/info/rfc2629>.
[RFC3552]
Rescorla, E. and B. Korver, "Guidelines for Writing RFC Text on Security Considerations", BCP 72, RFC 3552, DOI 10.17487/RFC3552, , <https://www.rfc-editor.org/info/rfc3552>.
[RFC5226]
Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", RFC 5226, DOI 10.17487/RFC5226, , <https://www.rfc-editor.org/info/rfc5226>.

Appendix A. Additional Stuff

This becomes an Appendix.

Authors' Addresses

Christine van Vredendaal (editor)
NXP Semiconductors
High Tech Campus 60
5656 AE Eindhoven
Netherlands
Silvio Dragione (editor)
IBM Research GmbH
Saeumerstrasse 4
CH-8803 Rueschlikon
Switzerland
Basil Hess (editor)
IBM Research GmbH
Saeumerstrasse 4
CH-8803 Rueschlikon
Switzerland
Tamas Visgrady (editor)
IBM Research GmbH
Saeumerstrasse 4
CH-8803 Rueschlikon
Switzerland
Michael Osborne (editor)
IBM Research GmbH
Saeumerstrasse 4
CH-8803 Rueschlikon
Switzerland
Dieter Bong (editor)
Utimaco IS GmbH
Germanusstrasse 4
52080 Aachen
Germany
Joppe Bos (editor)
NXP Semiconductors
High Tech Campus 60
5656 AE Eindhoven
Netherlands