Le cryptographe qui garantit que nous pouvons faire confiance à nos ordinateurs | Quanta Magazine

Yael Tauman Kalai est une informaticienne théorique pionnière qui a remporté des prix impressionnants et a changé la façon dont les gens perçoivent Internet. Mais enfant, elle n'était pas exactement une étudiante modèle.

"J'étais une fauteuse de troubles", a-t-elle déclaré. "J'étais fondamentalement - pas tout à fait, mais fondamentalement - expulsé du lycée."

Kalai est né et a grandi à Tel Aviv, en Israël, dans une famille universitaire. Son père, Yair Tauman, est économiste et théoricien des jeux. Ses cours de lycée l'ennuyaient - un bulletin scolaire documentait quelque chose comme 150 absences à l'école, se souvient-elle, car elle préférait passer son temps à faire du ski nautique et à socialiser. Mais ses capacités d'analyse ont toujours été là.

"Quand mes parents ne me laissaient pas sortir, souvent la seule façon d'amener mon père à accepter était de lui dire : 'OK, donne-moi une énigme mathématique. Aussi fort que tu veux, mais si je résous, j'y vais. » Elle y allait habituellement.

Son amour dormant pour les mathématiques s'est finalement réveillé à l'université, lorsqu'elle a commencé à reconnaître sa beauté. Finalement, elle a découvert qu'elle pouvait utiliser ces mathématiques avec des ordinateurs et, plus précisément, sécuriser des informations. Maintenant, son travail chevauche les domaines des mathématiques et de l'informatique, et ses idées ont été fondamentales pour protéger et vérifier le calcul à l'ère numérique. Au cours des deux dernières décennies, elle a travaillé pour assurer l'intégrité de nos smartphones, des connexions cloud et même des crypto-monnaies. Aujourd'hui chercheuse chez Microsoft et professeure adjointe au Massachusetts Institute of Technology, elle a récemment remporté le prestigieux ACM Prize in Computing de l'Association for Computer Machinery pour "des percées dans la délégation vérifiable du calcul et des contributions fondamentales à la cryptographie". Ses derniers travaux sont également tournés vers l'avenir, car elle examine comment les ordinateurs quantiques peuvent affecter le paysage de la sécurité.

Quanta a parlé avec Kalai de la fuite de secrets, de la vérification du cloud et du funkiness de l'informatique quantique. L'interview a été condensée et modifiée pour plus de clarté.

Comment êtes-vous passé de trublion du lycée à universitaire ?

J'ai toujours su que j'aimais les maths, mais les maths au lycée n'étaient pas du tout intéressantes. Ensuite, je suis allé étudier les mathématiques au premier cycle et j'ai été époustouflé. C'est la première fois de ma vie où je me suis assise et j'ai étudié sans arrêt, du matin au soir. J'étais dans l'euphorie. Et je dois dire que j'étais un peu contrarié, parce que je pensais : « Je ne peux pas croire que j'aurais pu apprécier ça quand j'étais beaucoup plus jeune !

Qu'est-ce qui vous a captivé dans les mathématiques ?

C'est très propre, élégant et abstrait. Et certains concepts en mathématiques sont contre-intuitifs ; Je me souviens avoir senti que l'étudier me changeait en tant que personne. Vous apprenez à être humble, car vous apprenez encore et encore que vos intuitions sont fausses.

Mais quand je cherchais une bonne question de recherche, tout semblait progressif. J'ai donc commencé à m'orienter vers l'informatique. Et la cryptographie était exactement ce qui me manquait, car elle traite des problèmes du monde réel. Aujourd'hui, la cryptographie est utilisée partout. Il est utilisé pour garantir que les messages que nous envoyons sont confidentiels et authentiques. Lorsque j'envoie un texto à quelqu'un, comment puis-je savoir que le message que j'ai reçu est le message qui a été envoyé ? Comment puis-je savoir que la personne qui prétend avoir envoyé le message est celle qui l'a réellement envoyé ? Qu'est-ce que ça veut dire de savoir ça ? Les concepts sont très philosophiques et la façon dont nous les modélisons mathématiquement est vraiment magnifique. Cela m'a frappé, à la fois la pureté des mathématiques et l'applicabilité.

Sur quel type de problèmes cryptographiques avez-vous travaillé ?

Ma thèse de maîtrise s'intitulait « Comment divulguer un secret ». Voici le problème : nous savons comment signer numériquement - pour dire : "C'est moi qui ai écrit ce message". Mais disons que je veux signer quelque chose en tant que professeur du MIT, mais je ne veux pas que les gens sachent que c'est moi ? De cette façon, le secret tient un peu d'eau parce que vous savez qu'un professeur du MIT l'a signé, mais vous ne savez pas qui.

Nous avons résolu ce problème avec quelque chose que nous avons appelé les signatures en anneau, qui ont été inspirées par une notion en informatique appelée preuves indiscernables par témoin. Disons qu'il y a une déclaration et deux façons différentes de le prouver. Nous disons qu'il y a deux "témoins" pour que la déclaration soit correcte - chacune des preuves. Une preuve indiscernable par un témoin a la même apparence, peu importe celle que vous utilisez : elle cache le témoin avec lequel vous avez commencé.

Les signatures en anneau sont similaires. Dans le groupe des fuyards potentiels, vous pouvez considérer chaque personne comme ayant une clé secrète. Et la signature de l'anneau prouve essentiellement que ce message a été signé par quelqu'un avec l'une des clés secrètes, mais cela ne révèle pas quelle clé secrète ils connaissent. Il cache dont la clé secrète a été utilisée.

Une institution utiliserait-elle réellement ce système ?

C'est ce qu'il y a de beau et d'effrayant - je peux le faire sans que personne d'autre ne soit impliqué. Je peux signer en tant que membre du groupe sans l'autorisation du groupe. Il n'est pas clair s'il s'agit d'une fonctionnalité ou d'un bogue, mais il est clair qu'il s'agit d'une découverte scientifique. Des signatures en anneau ont été utilisées - il existe une crypto-monnaie appelée monero qui dit qu'ils l'utilisent pour la confidentialité des transactions. Mais franchement, je ne sais pas vraiment qui utilise notre travail. La vérité est que je suis trop occupé pour le suivre.

Comment votre travail a-t-il évolué vers l'analyse de la sécurité de nos appareils ?

Au début des années 2000, j'étais à la fin de mon doctorat, travaillant avec Shafi Goldwasser au MIT. Les gens venaient de commencer à parler du cloud computing, que nous utilisons maintenant tous les jours. Avant, vous aviez un immense bureau où tout était fait. Avec l'augmentation de la collecte de données volumineuses, les calculs sont devenus plus coûteux et ont commencé à être effectués à distance. L'idée est qu'il existe un cloud puissant qui effectue des calculs pour vous. Mais vous ne faites peut-être pas confiance à la plate-forme cloud, alors comment savez-vous qu'ils effectuent le calcul correctement ? Parfois, il peut y avoir une incitation à tricher car le calcul peut être très coûteux. Et puis, dans certains contextes, vous pouvez vous inquiéter d'une erreur aléatoire. Donc, vous voulez vraiment une preuve que ce calcul est correct.

Mais généralement, les preuves sont très longues et les appareils faibles ne peuvent pas vérifier les longues preuves. Même pour les appareils qui le peuvent, c'est très coûteux. Alors, y a-t-il un moyen de réduire les preuves ? Information-théoriquement, non. Mais il s'avère qu'en utilisant des outils cryptographiques, nous pouvons à la place générer des certificats succincts qui sont très, très difficiles à falsifier. Ceux-ci sont appelés arguments succincts non interactifs, ou SNARG. Ce n'est pas une preuve, vraiment. Mais tant que vous ne pouvez pas résoudre un problème que nous, les cryptographes, considérons comme très difficile, comme la factorisation de grands nombres, vous ne pouvez pas simuler les preuves succinctes.

Comment ces preuves sont-elles venues ?

Cela a commencé en 1985 avec Shafi Goldwasser, Silvio Micali et Charles Rackoff, qui ont introduit ensemble une notion de preuves interactives. Avant, quand les gens pensaient aux preuves, ils pensaient à écrire des lignes de données, et vous pouvez lire et vérifier si elles sont correctes ou non. Goldwasser, Micali et Rackoff ont introduit une manière complètement différente de prouver quelque chose : utiliser l'interaction. Il y a un prouveur et il y a un vérificateur, et ils échangent des messages dans les deux sens. Ensuite, le vérificateur décide s'il est convaincu ou non.

Permettez-moi de vous donner un exemple de quelque chose qui est plus facile à faire comme preuve interactive que comme preuve classique. Supposons que nous jouions aux échecs. Supposons maintenant que je veuille vous prouver que j'ai une stratégie gagnante. Peu importe les mouvements que vous ferez, je gagnerai toujours. Comment te le prouver ?

Classiquement, c'est une énorme preuve, car je dois prouver que ma stratégie fonctionne contre toutes les combinaisons de coups possibles. Mais, il s'avère que, grâce à l'interaction, je peux le faire très succinctement. Si vous ne croyez pas que j'ai une stratégie gagnante, jouons. Je vais te montrer que je vais gagner. Bien sûr, cela seul n'est pas convaincant - ce n'est pas parce que je peux gagner une fois contre vous que je peux gagner contre n'importe qui. Alors donnez-moi un grand maître. Je vais gagner contre un grand maître. Cela commence à démontrer la puissance de l'interaction.

Mais l'inconvénient d'une preuve interactive est qu'elle n'est pas transférable. Disons que vous me donnez un billet de cent dollars et prouvez, par l'interaction, qu'il vaut bien 100 $. Je veux pouvoir le transmettre. Je veux le donner à quelqu'un d'autre, qui le donne à quelqu'un d'autre. Mais si je n'avais qu'une preuve interactive, ça ne veut rien dire ; Je ne peux pas le donner à quelqu'un d'autre. Donc, la bonne chose à propos des SNARG est que vous pouvez les donner à quelqu'un d'autre.

Comme un certificat d'authenticité ?

Exactement. Les chaînes de blocs sont le principal endroit où elles sont utilisées aujourd'hui pour vérifier les transactions. Lorsque la blockchain est née, j'ai dit à mes étudiants que nous devrions envoyer au développeur du bitcoin, Satoshi Nakamoto, des fleurs et des chocolats, car il a vraiment rendu notre travail si pertinent.

Alors, comment supprimez-vous l'interaction pour créer ces certificats transférables ?

Avec la cryptographie. Permettez-moi d'essayer de vous donner une intuition de la façon dont cela fonctionne. Dans nos preuves interactives, le vérificateur envoie généralement un caractère aléatoire au prouveur - vous pouvez considérer cela comme le vérificateur vérifiant aléatoirement la preuve. Puis Amos Fiat et Adi Shamir ont eu une idée : pourquoi avez-vous besoin de ce vérificateur s'il ne fait qu'envoyer du hasard ? Peut-être pouvons-nous remplacer ce vérificateur par une fonction, comme quelque chose appelé une fonction de hachage - c'est une fonction qui semble aléatoire, et c'est un élément de base très important en cryptographie.

Et il s'avère que oui, nous le pouvons. Aujourd'hui, cela se fait tout le temps. Si vous avez un iPhone ou un Android, vous utilisez le paradigme Fiat-Shamir lorsque votre téléphone se connecte à des serveurs distants, ce qui peut se produire fréquemment tout au long de la journée. Et c'est ce paradigme que nous utilisons pour construire les preuves succinctes qui certifient que les calculs à distance sont corrects.

Vous avez parlé de machines devant être « post-quantum secure ». Qu'est-ce que cela signifie?

Les ordinateurs quantiques, s'ils venaient à exister à grande échelle, seraient beaucoup plus puissants que les ordinateurs classiques. Les ordinateurs classiques fonctionnent en bits, qui sont soit 0 soit 1. Dans les ordinateurs quantiques, vous avez des bits quantiques, qui sont en superposition entre 0 et 1. Et ces qubits sont intriqués, ce qui signifie qu'ils s'influencent les uns les autres. C'est ce qui donne vraiment leur pouvoir aux ordinateurs quantiques.

À l'avenir, il se peut que tout le monde n'ait pas un bureau quantique. Il peut y avoir quelques appareils quantiques coûteux qui effectuent des calculs à distance pour vous. Supposons que vous vouliez déléguer un calcul coûteux à l'un de ces appareils quantiques et que vous ayez besoin d'un certificat qui vérifie que la sortie est correcte - comment certifiez-vous l'exactitude des ordinateurs quantiques ? Maintenant qu'on veut utiliser des bits quantiques et non des bits classiques, tout change, surtout quand je veux que le vérificateur soit un ordinateur classique.

En 2018, il y a eu une première résultat par une étudiante de Berkeley, Urmila Mahadev. Elle a été la première à montrer une preuve classique et sécurisée sur le plan informatique pour vérifier les calculs quantiques.

Vous pouvez donc utiliser un ordinateur classique pour vérifier les calculs quantiques ? Cela semble impossible !

N'est-ce pas incroyable? J'étais membre du comité de programme quand Urmila a publié son article, et j'ai passé toute la nuit à le regarder - la quantité de caféine que j'ai bue ! J'étais époustouflé. À ce moment-là, j'étais un mannequin quantique complet. J'ai compris la partie crypto, mais il m'a fallu un certain temps pour comprendre comment cela s'articulait avec la partie quantique. Et c'était magnifique.

Passer de l'informatique classique à l'informatique quantique ressemble à une courbe d'apprentissage abrupte.

Je sais. En fait, je ne connais rien à la physique, et il y a beaucoup d'intuition en physique quantique impliquée. Je ne comprends pas les concepts les plus élémentaires, comme l'énergie et la température. Parfois je travaille avec des étudiants et dès qu'on parle d'informatique quantique, je deviens l'étudiant. Je commence à avoir un peu plus d'intuition. Et je dois dire que j'aime tellement ça, assis là avec un manuel sur l'information quantique. Il n'y a rien de mieux que d'être étudiant.