Network Working Group S. Josefsson, Ed. Internet-Draft 23 June 2026 Intended status: Informational Expires: 25 December 2026 Classic McEliece draft-josefsson-mceliece-05 Abstract This document specifies Classic McEliece, a Key Encapsulation Method (KEM) designed for IND-CCA2 security, even against quantum computers. This is a transcribed version of the proposed ISO Classic McEliece draft, which ISO standardized in June 2026. About This Document This note is to be removed before publishing as an RFC. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-josefsson-mceliece/. Source for this draft and an issue tracker can be found at https://gitlab.com/jas/ietf-mceliece. 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 25 December 2026. Copyright Notice Copyright (c) 2026 IETF Trust and the persons identified as the document authors. All rights reserved. Josefsson Expires 25 December 2026 [Page 1] Internet-Draft Classic McEliece June 2026 This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Table of Contents 1. Foreword . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Terms and definitions . . . . . . . . . . . . . . . . . . . . 4 4. Symbols and abbreviated terms . . . . . . . . . . . . . . . . 5 4.1. Guide to notation . . . . . . . . . . . . . . . . . . . . 5 4.2. Column vectors vs. row vectors . . . . . . . . . . . . . 6 4.3. 0-numbering vs. 1-numbering . . . . . . . . . . . . . . . 6 5. Requirements . . . . . . . . . . . . . . . . . . . . . . . . 7 6. Parameters . . . . . . . . . . . . . . . . . . . . . . . . . 8 7. The one-way function . . . . . . . . . . . . . . . . . . . . 9 7.1. Matrix reduction . . . . . . . . . . . . . . . . . . . . 9 7.1.1. Reduced row-echelon form . . . . . . . . . . . . . . 9 7.1.2. Systematic form . . . . . . . . . . . . . . . . . . . 9 7.1.3. Semi-systematic form . . . . . . . . . . . . . . . . 10 7.2. Matrix generation for Goppa codes . . . . . . . . . . . . 10 7.2.1. General . . . . . . . . . . . . . . . . . . . . . . . 10 7.2.2. Systematic form . . . . . . . . . . . . . . . . . . . 10 7.2.3. Semi-systematic form . . . . . . . . . . . . . . . . 11 7.3. Encoding subroutine . . . . . . . . . . . . . . . . . . . 12 7.4. Decoding subroutine . . . . . . . . . . . . . . . . . . . 12 8. The Classic McEliece KEM . . . . . . . . . . . . . . . . . . 13 8.1. Irreducible-polynomial generation . . . . . . . . . . . . 13 8.2. Field-ordering generation . . . . . . . . . . . . . . . . 14 8.3. Key generation . . . . . . . . . . . . . . . . . . . . . 14 8.4. Fixed-weight-vector generation . . . . . . . . . . . . . 15 8.5. Encapsulation . . . . . . . . . . . . . . . . . . . . . . 16 8.6. Decapsulation . . . . . . . . . . . . . . . . . . . . . . 16 9. Bits and bytes . . . . . . . . . . . . . . . . . . . . . . . 17 9.1. Choices of symmetric-cryptography parameters . . . . . . 17 9.2. Representation of objects as byte strings . . . . . . . . 18 9.2.1. Bit vectors . . . . . . . . . . . . . . . . . . . . . 18 9.2.2. Session keys . . . . . . . . . . . . . . . . . . . . 18 9.2.3. Ciphertexts for non-pc parameter sets . . . . . . . . 18 9.2.4. Ciphertexts for pc parameter sets . . . . . . . . . . 18 9.2.5. Hash inputs for non-pc parameter sets . . . . . . . . 19 9.2.6. Hash inputs for pc parameter sets . . . . . . . . . . 19 9.2.7. Public keys . . . . . . . . . . . . . . . . . . . . . 19 Josefsson Expires 25 December 2026 [Page 2] Internet-Draft Classic McEliece June 2026 9.2.8. Field elements . . . . . . . . . . . . . . . . . . . 19 9.2.9. Monic irreducible polynomials . . . . . . . . . . . . 19 9.2.10. Field orderings . . . . . . . . . . . . . . . . . . . 20 9.2.11. Column selections . . . . . . . . . . . . . . . . . . 21 9.2.12. Private keys . . . . . . . . . . . . . . . . . . . . 22 10. Selected parameter sets . . . . . . . . . . . . . . . . . . . 22 10.1. Parameter set mceliece6688128 . . . . . . . . . . . . . 22 10.2. Parameter set mceliece6688128f . . . . . . . . . . . . . 22 10.3. Parameter set mceliece6688128pc . . . . . . . . . . . . 22 10.4. Parameter set mceliece6688128pcf . . . . . . . . . . . . 22 10.5. Parameter set mceliece6960119 . . . . . . . . . . . . . 23 10.6. Parameter set mceliece6960119f . . . . . . . . . . . . . 23 10.7. Parameter set mceliece6960119pc . . . . . . . . . . . . 23 10.8. Parameter set mceliece6960119pcf . . . . . . . . . . . . 23 10.9. Parameter set mceliece8192128 . . . . . . . . . . . . . 23 10.10. Parameter set mceliece8192128f . . . . . . . . . . . . . 23 10.11. Parameter set mceliece8192128pc . . . . . . . . . . . . 23 10.12. Parameter set mceliece8192128pcf . . . . . . . . . . . . 23 11. Security Considerations . . . . . . . . . . . . . . . . . . . 24 12. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 24 13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 25 14.1. Normative References . . . . . . . . . . . . . . . . . . 25 14.2. Informative References . . . . . . . . . . . . . . . . . 25 Appendix A. Overview of Classic McEliece resources (informative) . . . . . . . . . . . . . . . . . . . . . . 27 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 27 1. Foreword This document is a transcribed version of the proposed ISO McEliece standard (the "20230419" [CM-iso] version), prepared by the Classic McEliece team, as a draft of a potential ISO McEliece standard. ISO standardized Classic McEliece in June 2026 [ISO18033-2-AMD2]. 2. Introduction The first code-based public-key encryption system (PKE) was introduced in 1978 [McEliece]. The public key specifies a random binary Goppa code. A ciphertext is a codeword plus random errors. The private key allows efficient decoding: extracting the codeword from the ciphertext, identifying and removing the errors. The McEliece system was designed to be one-way (OW-CPA), meaning that an attacker cannot efficiently find the codeword from a ciphertext and public key, when the codeword is chosen randomly. The security level of the McEliece system has remained remarkably stable, despite dozens of attack papers over 45 years. The original McEliece Josefsson Expires 25 December 2026 [Page 3] Internet-Draft Classic McEliece June 2026 parameters were designed for only 2^64 security, but the system easily scales up to "overkill" parameters that provide ample security margin against advances in computer technology, including quantum computers. The McEliece system has prompted a tremendous amount of followup work. Some of this work improves efficiency while clearly preserving security: this includes a "dual" PKE proposed by Niederreiter, software speedups, and hardware speedups. Furthermore, it is now well known how to efficiently convert an OW- CPA PKE into a KEM that is IND-CCA2 secure against all ROM attacks. This conversion is tight, preserving the security level, under two assumptions that are satisfied by the McEliece PKE: first, the PKE is deterministic (i.e., decryption recovers all randomness that was used); second, the PKE has no decryption failures for valid ciphertexts. Even better, recent work achieves similar tightness for a broader class of attacks, namely QROM attacks. The risk that a hash-function- specific attack could be faster than a ROM or QROM attack is addressed by the standard practice of selecting a well- studied, high-security, "unstructured" hash function. Classic McEliece brings all of this together. It is a KEM designed for IND-CCA2 security at a very high security level, even against quantum computers. 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. Every level of the construction is designed so that future cryptographic auditors can be confident in the long-term security of post-quantum public-key encryption. 3. Terms and definitions For the purposes of this document, the following terms and definitions apply. * SHAKE256: see [NIST.FIPS.202], the sole symmetric primitive used in Classic McEliece with the selected parameters * IND-CCA2: indistinguishability against adaptive chosen-ciphertext attacks * KEM: key-encapsulation mechanism * OW-CPA: one-wayness against chosen-plaintext attacks * PKE: public-key encryption system Josefsson Expires 25 December 2026 [Page 4] Internet-Draft Classic McEliece June 2026 * ROM: random-oracle model * QROM: quantum random-oracle model * F_q: finite field of q * :=: member of a set * A_b, A_{b}: entity A subscripted with expression b * A^b, A^{b}: entity A superscripted with expression b * A_b^c, A_{b}^{c}, A^{c}_{b}: entity A subscripted with expression b and superscripted with expression c * =>: larger than or equal * <=: less than or equal * CEILING(a): function mapping a to the least integer greater than or equal to a * p * q: matrix multiplication 4. Symbols and abbreviated terms 4.1. Guide to notation The list below introduces the notation used in this specification. It is meant as a reference guide only; for complete definitions of the terms listed, refer to the appropriate text. Some other symbols are also used occasionally; they are introduced in the text where appropriate. * n: The code length (part of the CM parameters) * k: The code dimension (part of the CM parameters) * t: The guaranteed error-correction capability (part of the CM parameters) * q: The size of the field used (part of the CM parameters) * m: logarithm base 2 of q (part of the CM parameters) * u: A nonnegative integer (part of the CM parameters) * v: A nonnegative integer (part of the CM parameters) Josefsson Expires 25 December 2026 [Page 5] Internet-Draft Classic McEliece June 2026 * Hash: A cryptographic hash function (symmetric-cryptography parameter) * HashLen: Length of an output of Hash (symmetric-cryptography parameter) * Sigma_1 : A nonnegative integer (symmetric-cryptography parameter) * Sigma_2 : A nonnegative integer (symmetric-cryptography parameter) * PRG: A pseudorandom bit generator (symmetric-cryptography parameter) * g: A polynomial in F_q[x] (part of the private key) * alpha_i: An element of the finite field F_q (part of the private key) * Gamma: (g, alpha_0, ..., alpha_{n-1}) (part of the private key) * s: A bit string of length n (part of the private key) * T: An mt * k matrix over F_2 (the CM public key) * e: A bit string of length n and Hamming weight t * C: A ciphertext encapsulating a session key 4.2. Column vectors vs. row vectors Elements of F_2^n, such as codewords and error vectors, are always viewed as column vectors. This convention avoids all transpositions. Beware that this differs from a common convention in coding theory, namely to write codewords as row vectors but to transpose the codewords for applying parity checks. 4.3. 0-numbering vs. 1-numbering To simplify comparisons to software in most programming languages, this specification consistently uses indices numbered from 0, including row indices, column indices, and alpha indices. Beware that conventions in the mathematical literature sometimes agree with this but sometimes do not: for example, polynomial exponents are conventionally numbered from 0, while most vectors not related to polynomial exponents are conventionally numbered from 1. Josefsson Expires 25 December 2026 [Page 6] Internet-Draft Classic McEliece June 2026 5. Requirements This document defines the Classic McEliece KEM. The KEM consists of three mathematical functions, namely KeyGen, Encap, and Decap, for each of the "selected parameter sets" listed in Clause 10. The definitions for each selected parameter set are unified into a single definition for a broader parameter space specified in Clause 6. For each parameter set in that parameter space, subsequent clauses in this document define * exactly which public key and private key are output by KeyGen given random bits; * exactly which ciphertext and session key are output by Encap given a public key and random bits; and * exactly which session key is output by Decap given a ciphertext and a private key. This document defines each mathematical function F by presenting an algorithm to compute F. Basic algorithms such as Gaussian elimination are not repeated here, but MatGen, Encode, Decode, Irreducible, FieldOrdering, SeededKeyGen, FixedWeight, KeyGen, Encap, and Decap are specified below as numbered lists of steps. Three of these algorithms, namely FixedWeight, KeyGen, and Encap, are randomized, generating random bits at specified moments. The set of strings of random bits allowed as input for the corresponding mathematical functions is defined as the set of strings of random bits consumed by these algorithms. For example, the KeyGen algorithm reads exactly HashLen random bits, so the domain of the mathematical function KeyGen is the set of HashLen-bit strings. Here HashLen, one of the Classic McEliece parameters, is 256 for each of the selected parameter sets. To claim conformance to this document, an algorithm shall (1) name either KeyGen or Encap or Decap; (2) identify a parameter set listed in Clause 10 (not another parameter set from Clause 6); and (3) compute exactly the corresponding mathematical function defined in this document for that parameter set. For example, a KeyGen implementation claimed to conform to this document for the mceliece6960119 parameter set shall compute the specified KeyGen function for that parameter set: i.e.,