Dihedral Quantum MDPC Codes and their Applications to Code-Based Cryptography

In the evolving field of post-quantum cryptography, the McEliece cryptosystem, which leverages the difficulty of decoding linear codes, is gaining great importance. Among the variants of this system, those utilizing moderate-density parity-check (MDPC) codes have proven particularly noteworthy, as they offer a good trade-off between security and efficiency.

Recently, it has been shown that there exists a family of asymptotically good quantum Low-Density-Parity-Check (LDPC) codes, i.e., quantum LDPC codes whose minimum code distance and dimension grow linearly with the block length. These codes are based on the lifted product construction from certain group codes. A generalization of this result has profound implications for the McEliece cryptosystem, particularly in the context of integrating MDPC codes.

The aim of this talk is to examine the intersection of quantum codes and cryptography, emphasizing the role of quantum MDPC codes in the context of McEliece-type systems. In particular, we will focus on the construction of lifted product codes over the dihedral group algebra. Lifted product codes over this group algebra have not yet been explored but still allow for the formulation of useful distance bounds. Using this construction, which is based on classical linear codes with special self-orthogonal properties, we can provide explicit examples of new MDPC quantum codes.

Im sich entwickelnden Bereich der Post-Quanten-Kryptographie gewinnt das McEliece-Kryptosystem, welches die Schwierigkeit des Decodierens linearer Codes ausnutzt, grosse Bedeutung. Unter den Varianten dieses Systems haben sich insbesondere solche, die moderate-density parity-check (MDPC)-Codes nutzen, als bemerkenswert erwiesen, da sie einen guten Kompromiss zwischen Sicherheit und Effizienz bieten.

Kürzlich wurde gezeigt, dass es eine Familie von asymptotisch guten quantenmechanischen Low-Density-Parity-Check (LDPC)-Codes gibt, das heißt, quantenmechanische LDPC-Codes, deren minimale Code-Distanz und Dimension linear mit der Blocklänge wachsen. Diese Codes basieren auf der Lifted-Product-Konstruktion von bestimmten Gruppencodes. Eine Verallgemeinerung dieses Ergebnisses hat tiefgreifende Implikationen für das McEliece-Kryptosystem, insbesondere im Zusammenhang mit der Integration von MDPC-Codes.

Das Ziel dieses Vortrags ist es, die Schnittstelle zwischen Quanten Codes und Kryptographie zu untersuchen und dabei die Rolle von Quanten MDPC-Codes im Kontext von McEliece-ähnlichen Systemen hervorzuheben. Insbesondere werden wir uns auf die Konstruktion von Lifted-Product-Codes über der Diedergruppenalgebra konzentrieren. Lifted-Product-Codes über dieser Gruppenalgebra wurden bisher noch nicht betrachtet und erlauben dennoch die Formulierung nützlicher Distanzschranken. Mit dieser Konstruktion, die auf der Konstruktion klassischer linearer Codes mit speziellen selbstorthogonalen Eigenschaften basiert, können wir explizite Beispiele neuer MDPC-Quanten-Codes geben.

Dans le domaine en pleine évolution de la cryptographie post-quantique, le système cryptographique de McEliece, qui exploite la difficulté du décodage des codes linéaires, prend une grande importance. Parmi les variantes de ce système, celles utilisant des codes à vérification de parité de densité modérée (MDPC) se sont révélées particulièrement intéressantes, car elles offrent un bon compromis entre sécurité et efficacité.

Il a été récemment démontré qu'il existe une famille de codes quantiques LDPC (Low-Density-Parity-Check) asymptotiquement bons, c’est-à-dire des codes LDPC quantiques dont la distance minimale et la dimension augmentent linéairement avec la longueur du bloc. Ces codes reposent sur la construction dite du "lifted product" à partir de certains codes de groupes. Une généralisation de ce résultat a des implications profondes pour le système de McEliece, en particulier dans le cadre de l'intégration des codes MDPC.

L'objectif de cette présentation est d'examiner l'intersection entre les codes quantiques et la cryptographie, en mettant l'accent sur le rôle des codes MDPC quantiques dans le contexte des systèmes de type McEliece. En particulier, nous nous concentrerons sur la construction de codes "lifted product" sur l’algèbre du groupe diédral. Les codes "lifted product" sur cette algèbre de groupe n'ont pas encore été explorés, mais ils permettent néanmoins la formulation de bornes utiles pour les distances. En utilisant cette construction, basée sur des codes linéaires classiques dotés de propriétés auto-orthogonales spécifiques, nous pouvons fournir des exemples explicites de nouveaux codes MDPC quantiques.