Quantum Safe Cryptography Key Information for FALCON

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:¶

• Managing a smooth transition from early adoption algorithm versions to production versions where there is no compatibility.¶
• Supporting different algorithm versions from different NIST rounds¶
• Identifying different key serialization strategies¶
• Identifying compressed and uncompressed keys¶

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. This proposal defines in section 2 a long-term structured key representation format useful to address the goals outlined above.¶

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.1. Key Formats

The private 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 [RFC5280]

RFC5280 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 [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.¶

3.1. Algorithm Parameter Identifiers

FALCON uses OIDs to identify parameters sets.¶

|=========================+=====================================|
| 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 (beta^2) = 34034726           |
|                         | Standard deviation = 165.736617183  |
|                         | sigma_{max} = 1.8205                |
|                         | sigma_{min} = 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 (beta^2) = 34034726           |
|                         | Standard deviation = 168.388571447  |
|                         | sigma_{max} = 1.8205                |
|                         | sigma_{min} = 1.298280334           |
|=========================+=====================================|

3.2. Key Details

The FALCON private 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  |   Private |
|                          |         |   Key     |
|                          |         |   Length  |
|==========================+=========+===========+
| falcon512-r3             | f=384   | 1280      |
|                          | g=384   |           |
|                          | F=512   |           |
|--------------------------+---------+-----------|
| falcon1024-r3            | f=640   | 2304      |
|                          | g=640   |           |
|                          | F=1024  |           |
|==========================+=========+===========+

3.3. Private Key Full Encoding

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

• falcon-(degree)-r3 in the algorithm field of AlgorithmIdentifier¶
• FALCONPrivateKey in the privateKey field, which is an OCTET STRING.¶

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
}

3.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               |
|==========================+====================|

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

7.1. Normative References

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <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, May 2008, <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, May 2008, <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, May 2009, <hhttps://www.rfc-editor.org/info/rfc5480>.

7.2. Informative References

[draft-uni-qsckeys-01]

Vredendaal, C. V., Dragone, S., Hess, B., Visegrady, T., Osborne, M., Bong, D., and J. Bos, "Quantum Safe Cryptography Key Information", Work in Progress, Internet-Draft, draft-uni-qsckeys-01, 12 May 2022, <https://www.ietf.org/archive/id/draft-uni-qsckeys-01.txt>.

[RFC2629]

Rose, M., "Writing I-Ds and RFCs using XML", RFC 2629, DOI 10.17487/RFC2629, June 1999, <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, July 2003, <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, May 2008, <https://www.rfc-editor.org/info/rfc5226>.