Quantique :
ordinateur & cryptographie

Les performances de l'algorithme de Shor sont effarantes.

L'algorithme de Shor lui-même n'est pas si complexe, mais il est très astucieux, et repose sur la recherche d'une période, un truc qu'un ordinateur quantique saura bien faire.

Pour pallier cela, deux solutions sont proposées, avec des termes peu évidents pour le vulgum pecus:

La cryptographie post-quantique. Autrement dit, une nouvelle méthode qu’on espère moins vulnérable que RSA (mais ce n’est pas dit qu’un nouveau Shor vous casse votre nouvelle méthode dans le futur).

La cryptographie quantique dite QKD: on va envoyer des bits (a priori secrets) directement entre Alice et Bob, car il existe une propriété intéressante de non-clonage dans le monde quantique.

La cryptographie post-quantique est l'établissement de nouveaux algorithmes de chiffrement, qui n'auront rien de quantique, mais qui devraient résister aux futurs ordinateurs quantiques.

Quelles sont les voies de recherche en cryptographie dite post-quantique ? Comment justifier les choix ?

On part du problème (malheureusement) non résolu « P = NP ? ». Un problème appartient à la classe P s'il admet une procédure de résolution dont le temps de calcul est polynomial, et un problème appartient à la classe NP s'il admet une procédure de vérification d'une solution donnée ayant un temps de calcul polynomial.

Il existe une classe de problèmes dit NP-complets, qui sont au moins aussi difficiles que tous les autres problèmes NP, mais non formulables par une recherche de période, et donc solvables en un temps polynomial avec un ordinateur quantique.

Résultat des courses : on recherche des nouveaux algorithmes de chiffrement reposants sur des problèmes NP-complets. Mais vous l'avez compris, pas de preuve définitive que c'est un bon choix actuellement.

On fait du chiffrement par bloc -sinon il faudrait une clé aussi longue que le message. Alors on découpe en blocs grosso-modo de la taille de la clé et on recommence, en espérant que déchiffrer sera vraiment très long. Et là, on va vous dire que l'ordinateur quantique serait bien adapté pour rechercher des fonctions périodiques, alors on peut se poser des questions !

Il existe effectivement un schéma, celui d'Even-Mansour, qui attaque les blocs en recherchant des périodes. L'enfant se présente mal, comme on dit. L'attaque n'est pas réussie, mais bon, on est paranoïaque en sécurité.

Donc nous avons un géant aux pieds d'argile. Pas de preuves, que des conjectures. Voilà qui n'est guère engageant, mais on fonce dans le mur, ça, pas de soucis, on sait bien faire regardez la planète.

J'ai donc voulu comprendre le détail de cela, afin de pouvoir faire ma propre idée.

Et là, les ennuis commencent car:

• Il faut s'y connaitre un minimum en chiffrement pour voir de quoi on parle. D'où l'introduction de la cryptographie.
• Il faut s'y connaitre un minimum en mécanique quantique, afin de comprendre comment on va transmettre des qubits d'une manière sécurisée, et aussi pour comprendre ce que fait vraiment un ordinateur quantique.
• L'informatique quantique (et ses algorithmes) est un thème particulier à part entière : il faut voir comment ça marche afin de comprendre ce qu'est l'algorithme de Shor.
• La cryptographie quantique, bien que ce soit un titre galvaudé, est également un sujet à part entière, surtout qu'on utilise quasiment uniquement le photon pour ça, ce qui implique d'avoir un vernis en optique.

Du coup, si vous n'y connaissez pas grand-chose dans les sujets de base, il va falloir commencer par là (plutôt dans cet ordre, mais bon, c'est vous qui voyez):

• éléments d'optique
• mécanique quantique
• chiffrement

Ensuite, vous pourrez vous risquer sur les "vrais sujets". Mais bon, vous pouvez aussi sauter les bases en acceptant les résultats déjà connus, à vous de voir votre niveau. Vous pourrez toujours faire des allers-retours vers les bases en cas de besoin, c'est l'avantage d'un site web avec des liens...

Vous avez besoin juste des concepts basiques sans vraiment comprendre le fond des choses et sans y passer des plombes, ce rapport est fait pour vous:
- le rapport Villani pour le Sénat : 4 pages de juillet 2019 : Note n° 18 « Technologies quantiques: cryptographies quantiques et post-quantiques. » (copie locale)

Vous voulez en savoir plus, et comme j'étais au CEA, je vais la jouer "corporate": il existe un numéro spécial maison. Permet de connaitre les noms des gens sur le sujet, et ils sont nombreux.
- « Clefs »le numéro de juin 2018 (copie locale)

L’ennui avec ce numéro spécial, c’est que les gens pensent expliquer comment ça marche, mais en fait n’y arrivent pas vraiment et partent dans des détails qui ne vous mènent nulle part, il n’y a pas de cohérence dans la présentation un comble pour de la mécanique quantique. Une fois que vous avez lu, et bien vous n’êtes guère plus avancé. Même en relisant attentivement, c’est une sorte de patchwork. Et vous commencez à sentir que ce n’est pas gagné pour comprendre, si même les gars de « haut niveau » avec des noms prestigieux enfin, éventuellement n’arrivent pas à être clairs et convaincants.

Et là, un petit miracle est arrivé. Olivier Ezratty, un gars comme vous et moi, a voulu vraiment comprendre, et c’est fendu d’un document assez fouillé compilant ses recherches :
- Comprendre Informatique Quantique d'Olivier Ezratty, édition 2020

Perso, à l'époque où je me suis intéressé à ce sujet, j'ai lu la version de septembre 2019.

Sauf que… le document faisait 500+ pages... Mais il est parfaitement lisible par tout le monde, pas besoin d’avoir la médaille Fields ou un prix Nobel. Ce document vous sauvera des heures de recherches laborieuses, avec des articles à n’en pas finir qui n’abordent souvent que des détails particuliers sans vraiment expliquer. Ceci dit, malgré le préambule initial qui indique qu’il voulait vraiment comprendre, et bien je suis resté sur ma faim quand il a fallu comprendre comment diable on pouvait paralléliser les calculs, et surtout extraire de ce bourbier la réponse qui nous intéresse : OK, les calculs sont faits simultanément et nos qubits ont toutes les réponses superposées, mais pourquoi ce serait celle qui nous intéresse qui sort magiquement lors de l’effondrement de la fonction d’onde ? Je trouve qu’il est passé un peu à côté de certains concepts physiques, mais par contre, sa connaissance des compagnies qui sévissent sur le sujet est encyclopédique (et je n’aborderai pas cela ici, c’est trop de boulot inintéressant).

Et là, si vous avez compris le paragraphe précédent, c’est que vous êtes déjà un cake, et inutile de lire ma prose. Mais bon, simplement en lisant son bouquin, vous pourrez facilement faire le cake ensuite dans ce domaine. C’est ce que je vais faire, je l’ai lu.

La nouvelle édition a été totalement refondue : il est possible que les points que je viens d'évoquer soient un poil plus clairs, mais bon, je n'ai pas suivi la même démarche intellectuelle, aussi ce que je vais vous présenter est forcément différent. Probablement complémentaire.

Et j'espère avoir le même niveau d'humilité qu'Olivier Ezratty, mais ce n'est pas gagné, je me connais.

Je vais tenter de vulgariser les concepts, car mon niveau mathématique est au ras des pâquerettes, alors si des formules apparaissent, sachez que c’est forcément simple (on aime les bra|ket> dans le quantique, vous verrez).

Ma démarche est plutôt physique, j’aime comprendre, même s’il faut comprendre qu’en fait, on ne comprend pas ce qui se passe.

Allez, mettez votre bouée canard favorite et sautez !

Il va falloir choisir un des deux grands thèmes pour commencer :

• La cryptographie quantique
• Les ordinateurs quantiques