An Algorithmic Reduction Theory for Binary
    Codes: LLL and More
    Leo Ducas (CWI), Thomas Debris-Alazard (Inria),
    ´
    Wessel van Woerden (CWI).
                  Overview
       This work
    Propose analogues from
    lattices to binary codes
     (Defs, Algs, Bounds).
    Speed-up cryptanalytic
   algorithms for code-based
       cryptography. ?
                                      1 / 15
                                  Overview
             This work                           This talk
        Propose analogues from               • Recall the LLL algorithm
       lattices to binary codes                 for lattices.
        (Defs, Algs, Bounds).
                                             • Adapt it to codes.
        Speed-up cryptanalytic                           notion of
      algorithms for code-based                     What        for
            cryptography. ?                        orthogonality
                                                   binary codewords?
                                                                        1 / 15
                                                                                Lattices & Codes
                                               Lattice                                                                                     Binary Code
                                         P                                   k                 n                   C(B) := {P x b : x ∈ Fk} ⊂ Fn
                L(B) := {                        x b : x ∈ Z } ⊂ R                                                                                   i    i
                                              i     i   i                                                                                       i                             2                2
                                            Euclidean                                                                                           Hamming
                                                                 b
                                                                    2
                                                   0                    b
                                                                           1
                                       L=bZ+bZ                                                                              C = {000,011,101,110}
                                                     1               2                                                                                                                                   2 / 15