En 2020, chaque mois, Charlotte Truchet et Serge Abiteboul nous racontent des histoires d’algorithmes. Des blockchains aux algorithmes de tri en passant par le web, retrouvez tous leurs textes, ainsi que des petits défis mathématiques, dans le Calendrier Mathématique 2020 et dans la série binaire associée… Antoine Rousseau
Septembre : Yicha nineez agaanstsiin aak’ee*
Depuis sans doute aussi longtemps qu’on sait écrire, on chiffre des messages pour éviter que n’importe qui puisse les lire. On a retrouvé en Irak un document avec une recette chiffrée de poterie qui date du XVIe siècle avant JC. Aujourd’hui, les communications électroniques peuvent être chiffrées pour protéger leur confidentialité comme, par exemple, dans les services Signal ou WhatsApp. Avec le protocole https les pages Web sont également chiffrées pour éviter qu’elles puissent être lues depuis les serveurs par lesquels elles transitent, ainsi que pour garantir leur provenance.
Le principe du “chiffrement asymétrique” permet d’éviter d’avoir à partager une clé secrète commune avant de communiquer. Pour un tel chiffrement, je dispose de deux clés, une publique que je publie sur Internet et une privée que je ne donne à personne. Si vous voulez m’écrire, vous chiffrez votre message avec la clé publique. Je pourrais le lire, mais quelqu’un ne disposant pas de la clé privée sera incapable de le décrypter.
Le principe de chiffrement asymétrique a été proposé en 1976. Deux ans plus tard, Ronald Rivest, Adi Shamir et Leonard Adleman, inventaient le chiffrement RSA (pour les premières lettres des trois noms).
Reprenons l’exemple de Wikipédia. Nous vous cacherons par manque de place comment Alice a obtenu ses deux clés : sa clé publique (33, 3) et sa clé privée (33, 7). Bob veut transmettre le message “4” à Alice. Il le chiffre avec la clé publique : 43 mod 33, soit 31. Alice calcule 317 mod 33, c’est à dire “4”. Elle a bien récupéré le message.
Il est important de savoir que n (ici 33) est le produit de deux nombres premiers. Pour qu’un ennemi puisse décrypter ce message, il lui “suffirait” de décomposer 33 en un produit de deux nombres premiers. Facile ! Mais en pratique, la clé de chiffrement n est le produits de deux nombres premiers très grands et pour trouver sa décomposition, c’est une toute autre histoire. Cela nécessite une énorme quantité de calculs. Nos communications et notre commerce électronique sont en réalité protégées par l’immensité du temps de calcul nécessaire à les décrypter.
A l’avenir, peut-être sera-t-il possible de réaliser rapidement une telle factorisation avec des ordinateurs quantiques. Heureusement, personne ne sait réaliser de telles machines. En attendant, les cryptologues travaillent sur des algorithmes qui résisteraient même aux machines quantiques.
StopCovid a agité les médias avant de passer pour quelques temps dans un relatif oubli. Le répit dans la propagation du virus le rendait relativement inutile. Mais le Corona revient et repose de manière critique la question de limiter sa propagation. En première ligne, la méthode manuelle de traçage de contact qui semble à la peine. On peut s’inquiéter d’entendre que ce n’est pas toujours simple de se faire tester, que les résultats tardent, que les personnes impliquées sont parfois réticentes à participer, que les services humains mis en place sont débordés, etc. La réactivité de la détection est critique si on veut bloquer la propagation du virus.
A coté de l’approche classique par enquêtes intensives, le traçage numérique a été proposé comme complément indispensable. En France, c’est StopCovid. Alors, quid de StopCovid ?
Une vidéo des Décodeurs explique clairement les deux formes de détection, humaine et numérique [11]Préambule : c’est clairement un sujet miné, une machine à prendre des baffes y compris de ses meilleurs amis. Nous tenons à préciser que nous sommes parmi ceux qui ont plutôt accueilli positivement l’approche française autour d’Inria. Nous pensons que c’est ok de donner au gouvernement des informations personnelles pour ralentir la pandémie, mais que le maximum doit être fait pour en garantir, autant que possible bien sûr, sa confidentialité mais aussi son efficacité.
Au 19 août, selon la DGS [1], « l’application a été téléchargée près de 2,3 millions de fois, sur les plateformes Android et Apple, depuis sa mise en service le 2 juin […] 1 169 QR codes ont été utilisés et 72 contacts à risque notifiés ». C’est évidemment décevant :
– Pas tant par le nombre d’installations : avec quasiment pas de publicité et d’autres sujets de préoccupation autrement plus importants comme les vacances, il ne fallait pas s’attendre à des miracles.
– Les 1169 QR codes correspondent aux personnes qui ont installé StopCovid et se sont déclarées contaminées. Cela représente 0,05% des 2,3 millions de ceux qui ont installé StopCovid, sans doute un peu plus si on considère qu’une personne peut l’avoir installée plusieurs fois. Ça reste très peu. Les gens qui installent StopCovid sont-ils beaucoup moins touchés que les autres par le virus (protégés par StopCovid 🙂 ? Ceux qui ont été contaminés n’ont-ils pas reçu de code à saisir, ne l’ont-ils pas déclaré ? On aimerait comprendre.
– 72 contacts notifiés pour 1169 QR codes, ça fait 0,06 contacts par personne malade. Comme il est peu probable que les gens qui ont installé StopCovid ne croisent quasiment jamais personne, faudrait-il croire qu’ils ne croisent que des gens qui n’ont pas installé ou pas activé StopCovid ? Ou alors est-ce que StopCovid ne fonctionne pas comme on le pense ?
Crédit image Pexels-bongkarn-thanyakij
Des utilisateurs de l’application s’interrogent :
– “Elle passe ses vacances avec sa fille testée positive au coronavirus, l’application Stop Covid ne l’alerte pas” [2].
– “J’ai été testé positif au #Covid19 vendredi et j’avais l’application #StopCovid […] j’ai donc voulu jouer le jeu en me déclarant positif sur l’application, et c’est là que je me suis heurté à un mur” [3].
On ne sait quoi répondre. De fait, on manque terriblement d’information publique sur l’App.
On sait ce qu’il faut faire pour l’installer, on connaît les principes selon lesquels elle a été conçue (utilisation de la technologie Bluetooth, architecture centralisée, protocole ROBERT). Mais on ne sait pas précisément comment l’App fonctionne une fois installée, quelles sont ses limites, et quelle est son efficacité. Nous avons bien inspecté son code (disponible en open-source [4], merci!) mais s’il permet aux plus initiés de voir comment l’application a été implémentée, il n’explique pas pourquoi elle l’a été de cette manière. Pourquoi une rotation de 90° d’un iPhone sur lequel tourne l’application fait-elle disparaître les informations présentes à l’écran et diminuer sa luminosité, par exemple ? Pour relativiser nos remarques qui peuvent paraître critiques, les applications de traçage de contacts développées dans les autres pays ne fournissent pas beaucoup plus d’informations sur ce qu’elles font une fois lancées, comment elles le font ou pourquoi elles le font de cette manière.
On dispose peu de suivi statistique de l’utilisation de StopCovid. Les Suisses, entre autres, pourraient nous donner des leçons de transparence [5]. Le projet était pourtant prometteur en termes de transparence, au départ. Une des conditions évoquées pour la réussite de ce dispositif était le nombre de téléchargements par les citoyens, mais au-delà des débats qui ont agité sa mise à disposition, la campagne d’information qui n’a duré que peu de temps n’a pas été convaincante. Il est dommage de constater que les illustrations des bonnes pratiques à adopter proposées par le gouvernement (“Luttons ensemble contre le Covid-19”, [6]) n’intègrent pas le téléchargement de l’application.
On aimerait une évaluation approfondie et publique de l’état des lieux et une information plus régulière sur l’application.
StopCovid a été réalisé dans l’urgence sous la pression publique. On ne pouvait pas s’attendre à ce que l’App soit directement parfaite. OK. Mais, maintenant, améliorons-la ! Deux questions ont éclipsé les autres : la protection des données et la souveraineté nationale (pour la question de l’accès à Bluetooth). On peut approfondir ces sujets.
Le système actuel n’utilise pas l’interface de programmation “Exposure Notification” d’Apple et Google (GAEN, [7]). En termes de souveraineté, c’est parfait, l’État gardant la maîtrise des données et de la gestion de l’épidémie. Mais les développeurs de StopCovid ont-ils réussi à s’affranchir des limites techniques imposées par Apple ou Google sur toutes les applications Bluetooth et qui rendent le traçage de contact difficile sans GAEN [8] ? Dans quelle mesure l’application peut-elle communiquer par Bluetooth lorsqu’elle n’est pas visible à l’écran, lorsqu’une autre application est utilisée ou que le téléphone est verrouillé ? Y-a-t-il des choses à faire ou ne pas faire pour que la communication se fasse dans de bonnes conditions ? Si des solutions techniques ont été trouvées, si des contraintes en résultent, elles méritent d’être expliquées. Si les limites imposées par Apple et Google ne peuvent être que mal contournées, si l’application doit être le plus souvent possible visible, au premier plan sans que le téléphone soit verrouillé, il faut le savoir et s’en souvenir pour lancer à court terme un plan d’enfer européen pour pouvoir se passer d’iOS et d’Android .
Pourquoi ne passe-t-on pas au nouveau protocole développé par Inria, DESIRE [9] ? Il a l’air trop cool. Est-ce qu’il y a des raisons techniques pour ne pas l’adopter ? Est-ce que ce serait trop compliqué de changer de protocole au milieu de la pandémie ? La base installée n’est pourtant pas si gigantesque.
A côté de ces deux aspects très discutés, un sujet hyper important a été, à notre humble avis, ignoré : l’App fonctionne trop comme une boîte noire. Si on veut que le numérique participe à régler les questions parfois existentielles posées à notre société de l’écologie aux épidémies, l’approche boîte noire ne fonctionne pas.
Certains ont reproché le manque d’aspect ludique de l’App, son niveau gaming très faible. Le fait que les gens la trouvent sympa et voient un intérêt personnel à l’utiliser n’est pas à négliger, évidemment. Mais l’enjeu principal n’est pas de faire une appli cool pour “jouer avec le Covid”. Ce qui est en jeu c’est avant tout la bonne compréhension de ce que fait l’application, de ce qu’il faut faire (ou pas) pour qu’elle fonctionne correctement une fois installée et qu’elle puisse être utile à la gestion de l’épidémie.
Je suis en train de parler à ma fille, je veux savoir si nos deux StopCovid se sont causées. OK, c’est une violation potentielle de confidentialité, mais si elle est d’accord et moi aussi ? Je devrais pouvoir vérifier que ça marche, regarder ce qui se passe si elle met son tél dans sa poche, ou au fond de son sac… Si on peut assister en direct à la rencontre de nos deux App qui se font coucou, on comprendra un peu mieux ce qui se passe.
Je veux savoir ce que sait faire le système et ce qu’il ne sait pas faire. Au minimum, j’aimerais savoir ce qu’il est en train de faire, ce qu’il a fait récemment. Si je ne sais pas répondre à de telles questions, est-ce que je vais réellement utiliser cette App ?
Qu’on ne se méprenne pas, nous ne proposons pas d’arrêter l’expérience. On ne pouvait pas s’attendre à ce que StopCovid soit immédiatement parfait. Nous on veut que cela fonctionne et nous aide à combattre la pandémie. Maintenant, améliorons-le ! C’est une belle occasion pour montrer comment réussir un projet collectif qui met le numérique au service de la société.
Serge Abiteboul, Claude Hinn, et Dominique Normane
En 2020, chaque mois, Charlotte Truchet et Serge Abiteboul nous racontent des histoires d’algorithmes. Des blockchains aux algorithmes de tri en passant par le web, retrouvez tous leurs textes, ainsi que des petits défis mathématiques, dans le Calendrier Mathématique 2020 et dans la série binaire associée… Antoine Rousseau
Août : Alea jacta la machine
Les algorithmes sont mécaniques. Tels Dieu, ils ne jouent pas aux dés. Ils ne sont, par nature, pas aléatoires. Mais aussi surprenant que cela puisse être, l’aléatoire est souvent un ingrédient algorithmique très utile.
Certains algorithmes doivent explorer un espace très grand, trop grand, tellement grand parfois que l’âge de l’Univers ne suffirait pas à le visiter de manière systématique. L’algorithme doit alors faire des choix, dont certains sont bons, d’autres mauvais. Quand on sait toujours faire les bons choix, on peut terminer raisonnablement vite. Mais quand on ne sait pas, l’algorithme peut perdre énormément de temps sur des paris malheureux. Pour éviter cela, on utilise judicieusement des ingrédients aléatoires. Par exemple, si l’on soupçonne l’algorithme d’être coincé dans une série de mauvais choix, couic, on l’arrête et on le relance en choisissant un <<ailleurs>> aléatoire. Ce procédé, qu’on appelle random restart, permet à un algorithme de visiter un grand espace en évitant de se laisser piéger dans des régions sans espoir.
Dans d’autres cas, l’aléatoire permet de résoudre des problèmes que l’on ne saurait pas résoudre autrement. C’est le cas lorsque l’on veut calculer la surface de l’intérieur de certaines courbes spécifiées par des équations. Un tel calcul peut exiger la résolution d’intégrales trop compliquées pour les meilleurs mathématiciens. On peut alors utiliser une méthode très simple à base d’échantillonnage. On utilise un carré qui contient la courbe ; comme c’est un carré, il est simple de calculer sa surface. Ensuite, on tire au hasard un grand nombre de points dans ce carré. C’est facile de savoir si un point est à l’intérieur ou à l’extérieur de la courbe, grâce à son équation. On compte le pourcentage de points dans la courbe par rapport au nombre de points dehors. Le produit de ce pourcentage par la surface du carré donne une estimation de la surface cherchée. C’est super simple à réaliser. Et en choisissant beaucoup de points au hasard, on peut être très précis.
De façon un peu paradoxale, l’aléatoire se révèle souvent utile dans le monde des algorithmes. Mais, fabriquer aléatoirement une donnée sur un ordinateur n’est pas chose aisée ! On y parvient en effectuant des calculs suffisamment tarabiscotés sur des données pas du tout aléatoires, ou en utilisant du hardware spécialisé. Les résultats, s’ils ne sont pas vraiment aléatoires, sont suffisamment imprévisibles pour le paraître.
Nous utilisons donc, à l’intérieur d’algorithmes, des donnés aléatoires produites par une machine, alors que les machines sont en théorie complètement déterministes.
En 2020, chaque mois, Charlotte Truchet et Serge Abiteboul nous racontent des histoires d’algorithmes. Des blockchains aux algorithmes de tri en passant par le web, retrouvez tous leurs textes, ainsi que des petits défis mathématiques, dans le Calendrier Mathématique 2020 et dans la série binaire associée… Antoine Rousseau
