Linear Codes over Finite Fields: Understanding Hamming Distance and Syndrome Decoding

CLASSIC MCELIECE NIST PQC SUBMISSION presented by Gorjan Alagic

CLASSIC MCELIECE Website: https://classic.mceliece.org/ Team: Daniel J. Bernstein, University of Illinois at Chicago Tung Chou, Osaka University Tanja Lange, Technische Universiteit Eindhoven Ingo von Maurich, self Rafael Misoczki, Intel Corporation Ruben Niederhagen, Fraunhofer SIT Edoardo Persichetti, Florida Atlantic University Christiane Peters, self Peter Schwabe, Radboud University Nicolas Sendrier, Inria Jakub Szefer, Yale University Wen Wang, Yale University

LINEAR CODES OVER FINITE FIELDS Recall: Hamming distance ?with dim ? = ?, and An [?,?,?] code over ??is a subspace ? of ?? ?,? ?; ? ?? ?,? = ?. min elements of ? are called codewords; ? is called the distance; code can correct ? errors where ? = 2? + 1. ? ?? ?with Im ? = ? (put basis for ? as columns.) generator matrix: ? ?? ?, the codeword is ? = ?? ?? ?. our convention: ? acts on left, i.e., for a message ? ?? ? ? = ? ? ?

LINEAR CODES OVER FINITE FIELDS Recall: Hamming distance ? with dim ? = ?, and An [?,?,?] code over ?? is a subspace ? of ?? ?,? ?; ? ?? ?,? = ?. min elements of ? are called codewords; ? is called the distance; code can correct ? errors where ? = 2? + 1. ? ?? ? with Im ? = ? (put basis for ? as columns.) generator matrix: ? ?? ?, the codeword is ? = ?? ?? ?. our convention: ? acts on left, i.e., for a message ? ?? systematic form: express ? = ???) (via Gaussian elimination); ? ?? ? ? ?

LINEAR CODES OVER FINITE FIELDS Recall: Hamming distance ? with dim ? = ?, and An [?,?,?] code over ?? is a subspace ? of ?? ?,? ?; ? ?? ?,? = ?. min elements of ? are called codewords; ? is called the distance; code can correct ? errors where ? = 2? + 1. ? ?? ? with Im ? = ? (put basis for ? as columns.) generator matrix: ? ?? ?, the codeword is ? = ?? ?? ?. our convention: ? acts on left, i.e., for a message ? ?? ? systematic form: express ? = ???) (via Gaussian elimination); check matrix: ? ?? ? ? ?? ? ?with ker(?) = ?; can take ? = ? ?? ?) Why care about check matrix? Syndrome decoding: ? ?? ? ? ? ?, do ?(?) = ?(? + ?) = ?(?); 1. given noisy codeword ? ?? 2. now recover ? (not trivial) and output ? = ? ?. (p.s.: ? is also a generator matrix: for the dual code ? of ?.)

MCELIECE IDEA Decoding in a random code is a hard problem. Make crypto out of it? [McEliece, 78] choose [?,?,?] generator matrix ?and scramblers ? (invertible, ? ? ) and ? (permutation, ? ?); private key: (?,?,?); public key: ???; encrypt: ? (???)? + ? (where ? is a random error vector with Hamming weight ??(?) at most ?); decrypt: ? (? 1 Decode? ? 1)? Experience seems to indicate that decoding this (without private key) is as hard as the random-code case, at least for random messages. What codes to use? People have tried lots of choices, but binary Goppa codes seem safest. How to generate such a code: choose a polynomial ?(?) of degree ? over ?? with ? = 2?; choose ?1,?2, ,?? ??; ? 1/?(??). check matrix: ???= ??

NIEDERREITER VARIANT Take the dual everywhere [Niederreiter 86] choose [?,?,?] code with check matrix ?. Choose ? (invertible, (? ?) (? ?)) and ? (permutation, ? ?); private key: (?,?,?); public key: ???; encrypt: encode ? as an ?-bit error string ? with ?? ? ? , output (???)?; decrypt: ? (? 1 SyndromeExtract? ? 1) ?. ? ? ? ? ? ? still typically use binary Goppa codes; security is unchanged from McEliece, but some efficiency gains; important: ? is not structured, i.e., it really looks like a random error; formally, this means the scheme is only OW-CPA (given oracle for Enc and Enc(?) for *random* m, adversary has negligible success probability at outputting ?) but that s fine for a KEM.

CLASSIC MCELIECE (CM) Ok, now to the actual submission: Classic McEliece (CM). (Really, more like classic Niederreiter ) Parameters ? = 2? 0 < ? ? 1 < ? < ?/? ? = ? ?? monic, irreducible, degree ? polynomial ? ? ?2[?] ?q:= ?2? /? z cryptographic hash function ? with ? output bits.

? = 2? 0 < ? ? 1 < ? < ?/? ? = ? ?? monic, irred., deg-m ? ? ?2[?] ??:= ?2? /? ? Hash ? with ? output bits. KEY GENERATION Key generation for CM 1. Generate random monic irreducible degree-? polynomial ? ? ?qx ; generate check matrix for random binary Goppa code 2. Generate random, distinct ?1,?2, ,?? ??; ? 1/?(??); 3. Compute ? ? matrix ? = { ??} with ??= ?? ?0 ? 1????into column 4. Compute ?? ?, i.e., (? ?) ? binary matrix ? by expanding each entry ?=0 ?? 1 5. Reduce ? to unique systematic form (?? ?| ?) via Gaussian elimination; 6. Generate random ? 0,1?; Instead of adding scrambling, put H in systematic form (adversary can compute this too, so no security loss.) + key size ?(? ?)instead of ??. - only succeeds with probability ~29% over the choice of code 7. Output secret key (?,?,?1,?2, ,??) and public key ?.

? = 2? 0 < ? ? 1 < ? < ?/? ? = ? ?? monic, irred., deg-m ? ? ?2[?] ??:= ?2? /? ? Hash ? with ? output bits. ENCODE / DECODE Encode ? with ?? ? = ?; Input: public key ?, string ? ?2 1. output ?? = ?? ??)?. Decode ? ? Input: private key ?, and string ?0 ?2 1. set ? ?2 2. ? SyndromeDecode (?) ; output if failed 3. set ? = ? ?; if ?? ? = ? and ?0= ??, output ? ; otherwise output . check: ? ? = ?0, i.e., ? is a noisy codeword with syndrome ?0 n to be ?0 with ? zeroes appended; this is basically just Neiderreiter s scheme. as we said before, it s only OW-CPA; so CM will turn it into a KEM to get IND-CCA2.

? = 2? 0 < ? ? 1 < ? < ?/? ? = ? ?? monic, irred., deg-m ? ? ?2[?] ??:= ?2? /? ? Hash ? with ? output bits. ENCAPSULATE / DECAPSULATE Encapsulate Input: public key ?; ? with ?? ? = ?; 1. Generate random string ? ?2 2. Compute ?0= CM.Encode ? = ?? (recall ? = ?? ??)); 3. Output ciphertext ? = (?0,? 2,? ) and session key ? = ?(1,?,?); Decapsulate Input: private key ?, , ciphertext ? = ?0,?1; 1. set ? = 1; set ? = CM.Decode(?0); 2. if decoding rejects, or if ? 2,? ?1, set ? = ? and ? = 0. 3. output session key ? = ? ?,?,? ;

THEORETICAL SECURITY CM uses a standard approach of constructing a KEM from OW-CPA PKE; claim/hope: the resulting KEM is IND-CCA2 (if coupled with a secure DEM); there are classical security proofs [Dent03] in the ROM of a similar construction (basically, output instead of a pseudorandom value when Decapsulate fails); new result [Saito, Xagawa, Yamakawa; Eurocrypt 18]: IND-CCA2 for another similar KEM, but in the QROM! submitters have a sketched proposal for extending the SXY proof to CM, but it doesn t seem to be a complete proof, and I have not checked it; this would be good: QROM is a much better model for post-quantum security involving (public) hash functions.

ATTACKS Information-set decoding ignore structure, try to recover low-weight ? given ?? + ? for some ? and random ?; can be sped up using Grover (latest seems to be by E. Kirshanova: 20.05806?+?(?) PQCrypto 18?) Key recovery attacks brute force Sendrier s support splitting algorithm : Potential reason to choose ? < 2?; one parameter set does this. - can quickly find tuple (?1, ,??) given ? if ? = 2?. - can quickly find tuple (?1, ,??) given ? and ???. not as big of a threat as ISD (at least not yet.)

? = 2? 0 < ? ? 1 < ? < ?/? ? = ? ?? monic, irred., deg-m ? ? ?2[?] ??:= ?2? /? ? Hash ? with ? output bits. PARAMETER SETS kem/mceliece6960119 note ? < 2? ? = 13,? = 6960,? = 119,? = 256 ? ? = ?13+ ?4+ ?3+ ? + 1 ? = SHAKE256 with 32-byte output. Claimed strength: category 5 IND-CCA2 KEM. kem/mceliece8192128 ? = 13,? = 8192,? = 128,? = 256 ? ? = ?13+ ?4+ ?3+ ? + 1 ? = SHAKE256 with 32-byte output. Claimed strength: category 5 IND-CCA2 KEM.

? = 2? 0 < ? ? 1 < ? < ?/? ? = ? ?? monic, irred., deg-m ? ? ?2[?] ??:= ?2? /? ? Hash ? with ? output bits. PARAMETER SETS kem/mceliece6960119 note ? < 2? ? = 13,? = 6960,? = 119,? = 256 ? ? = ?13+ ?4+ ?3+ ? + 1 ? = SHAKE256 with 32-byte output. Claimed strength: category 5 IND-CCA2 KEM. proposed in [BLP08]; reported ISD attack with 2266.94 bit operations; improved ISD attacks now reduced this to considerably below 2256 . None of these analyses took into account the costs of memory access. A closer look shows that the attack in [BLP08] is bottlenecked by random access to a huge array (much larger than the public key being attacked), and that subsequent ISD variants use even more memory. The same amount of hardware allows much more parallelism in attacking, e.g., AES-256. Known quantum attacks multiply the security level of both ISD and AES by an asymptotic factor 0.5 + o(1), but a closer look shows that the application of Grover s method to ISD suffers much more overhead in the inner loop. We expect that switching from a bit-operation analysis to a cost analysis will show that this parameter set is more expensive to break than AES-256 pre-quantum and much more expensive to break than AES-256 post-quantum. from supporting doc

PERFORMANCE Sizes of things. Public key (bytes) Private key (bytes) Ciphertext (bytes) Session key (bytes) kem/mceliece6960119 1,357,824 14,080 240 32 kem/mceliece8192128 1,047,319 13,908 226 32 SW platform: Intel Xeon E3-1220 v3 Haswell 3.10 GHz, 32GB RAM, Ubuntu 16.04, no hyperthreading or Turbo Boost. Cycles ms KeyGen 4G-6G 1940 Encapsulate 300,000 0.1ms Decapsulate 450,000 0.15ms HW platform: Altera Stratix V FPGA (5SGXEA7N) @ 231Mhz Cycles ms KeyGen 1173750 5.08 Decoding 17140 0.074

ADVANTAGES / DISADVANTAGES Advantages simple, well-studied, well-understood: long history of attacks with not much effect on security parameters; seems plausible that there s a security proof (in the QROM?); fast encapsulation/decapsulation small ciphertexts Disadvantages huge public keys (order of MBs) very slow key generation