Méta : Ce billet est un rejeton d'un autre que j'ai commencé à rédiger sur un sujet technique (à savoir : les oracles en calculabilité au sens de Kihara) : en écrivant ce dernier je me suis dit que j'allais commencer par une introduction générale essentiellement grand public à la notion d'oracle (qu'est-ce que c'est que ce truc et pourquoi on les étudie ?). Mais finalement, comme cette introduction générale devenait un peu longue, et surtout comme elle ne vise en fait pas du tout le même public (ce qui suit ne se veut pas technique, le billet dont il est détaché présuppose des connaissances en calculabilité), et aussi parce qu'il y a toujours un risque que je ne finisse pas ce que je commence, je choisis de la publier séparément, plutôt que risquer de rebuter les lecteurs de l'un ou de l'autre. Du coup, je développe aussi un peu plus largement que ce qui était initialement prévu, au risque de rendre ce billet un peu bancal parce que j'ai repris plusieurs fois certains passages en changeant mon approche (notamment à force d'insérer des explications plus détaillées de choses que j'avais évoquées ailleurs, j'ai créé un certain nombre de redites : je pense qu'elles ne sont pas graves et j'ai la flemme de les traquer).
Quand (si !) je publierai l'autre billet, j'ajouterai un lien ici et réciproquement, pour qu'on puisse les lire successivement comme c'était initialement prévu. • Ajout : c'est ici.
À cause du fait que j'essaie de viser un public très large, je ne
vais pas donner de définitions mathématiques précises (si j'utilise un
terme technique comme exponentiel
, on peut se contenter d'une
idée très approximative de ce que c'est) ; mais du coup, il faut que
prévienne que je vais dire des choses qui seront parfois techniquement
incorrectes (même quand j'oublie de prendre les précautions oratoires
du type très grossièrement
, approximativement parlant
,
etc.). J'espère ne rien avoir dit de violemment faux, quand même,
mais tout est à prendre avec les pincettes de rigueur : il s'agit
juste de donner une toute petite idée du type de questions qu'on peut
se poser dans quelques parties de l'informatique théorique et d'un
outil intéressant (la notion d'oracle) pour y répondre et poser
d'autres questions, pas de rentrer dans le moindre détail technique
(pour ça, il y aura le deuxième volet, indépendant de celui-ci).
Pour les lecteurs qui ont la patience d'aller jusqu'au bout, il y a une petite énigme de logique(?) à la fin ; en fait, elle ne nécessite pas d'avoir lu ce qui précède, donc on peut la lire directement. (Bon, je ne sais pas si elle est intéressante, et je ne sais pas non plus à quel point elle est difficile. Je ne suis même pas complètement convaincu qu'elle ait un rapport avec le sujet, même si le contexte où je l'ai lue a clairement un rapport.)
Le concept d'oracle
dont il est question ici est vient de
l'informatique théorique (le terme oracle
apparaît dans la
thèse d'Alan Turing en 1938). Je voudrais essayer d'expliquer de
façon très informelle, très vague aussi malheureusement (mais,
j'espère, du coup, assez grand public) ce dont il est question.
Une partie de l'informatique théorique (l'algorithmique)
s'intéresse, de façon positive, à trouver des moyens de résoudre des
problèmes (mathématiquement bien définis), c'est-à-dire à concevoir
des algorithmes qui les résolvent : un algorithme est
un programme, un plan d'opération susceptible d'être mené dans un
ordinateur — mais aussi en principe par un humain particulièrement
patient — qui effectue une tâche calculatoire donnée. Par exemple, la
manière dont on apprend à faire des additions et des multiplications à
l'école primaire sont des algorithmes, même si ce ne sont pas
forcément les plus intéressants, ils ont le mérite de nous rappeler
qu'un algorithme ne tourne pas forcément sur un ordinateur, on peut
aussi l'exécuter à la main (ce sera juste quelques milliards de fois
plus lent…) ; d'ailleurs, le mot algorithme
fait référence au
mathématicien persan (écrivant en langue arabe) Muḥammad ibn Mūsá
al-H̱wārizmī parce qu'il a décrit toutes sortes de méthodes
systématiques pour résoudre des problèmes mathématiques, qu'on peut
donc légitimement qualifier d'algorithmes, et c'était plus de 1000 ans
avant l'invention des ordinateurs.
(Petite digression sur le terme algorithme
: il semble qu'un
mélange entre l'incompréhension des journalistes face à tout ce qui
est technique et l'approximation des termes utilisés dans le contexte
de l'intelligence artificielle ait
fait dévier le sens du mot, dans l'image qu'en a le grand public, vers
une sorte de synonyme de système opaque auquel on ne comprend
rien
. Certainement beaucoup de programmes utilisés dans
l'ingénierie informatique moderne (notamment tout ce qui relève de
l'IA) comportent énormément d'heuristiques et de méthodes
mal comprises, parfois même mal comprises de leurs programmeurs ou
concepteurs, et dont la réponse est parfois fausse ou mal spécifiée.
Mais le sens d'algorithme
en algorithmique désigne au contraire
un plan bien défini et bien compris qui arrive à un résultat bien
spécifié.)
Mais d'autres parties de l'informatique théorique s'intéressent non pas à concevoir des algorithmes efficaces pour résoudre tel ou tel problème, mais à se pencher sur la notion même d'algorithme et les limites théoriques du concept : que peut-on faire avec un ordinateur ?
Spécifiquement, on s'intéresse alors plutôt à des
résultats négatifs : plutôt que résoudre tel ou tel problème
c'est-à-dire concevoir un algorithme qui le résout, on s'attache à
montrer que tel ou tel problème est difficile (long et
coûteux) voire impossible à résoudre par un algorithme, ou au
moins, à étudier cette difficulté, à la classifier et à la jauger. Je
reste délibérément vague sur ce qu'un problème
peut recouvrir
ici et ce que difficile
veut dire, mais je peux délimiter ici
trois grands domaines où ce que je veux dire s'applique, et j'en
profite pour parler un peu plus longuement de chacun des trois, en
gros du plus théorique vers le plus appliqué (il n'est pas nécessaire
de lire tout ce que j'écris sur chacun ci-dessous pour passer à la
suite, mais je cherche à donner un minimum de contexte) :
-
La théorie de la calculabilité est la branche de l'informatique théorique (possiblement la plus proche des mathématiques pures, et notamment de la logique) qui étudie ce qu'on peut faire algorithmiquement avec des ressources illimitées, c'est-à-dire, en disposant d'un temps illimité et d'une mémoire illimitée. (Le mot
illimité
signifie icifini mais arbitrairement grand
,sans limite a priori
: c'est-à-dire que les algorithmes en question doivent s'arrêter un jour en disantj'ai terminé
, mais ils ont le droit de prendre autant de temps qu'ils veulent, tant que ce temps est fini ; idem pour la mémoire : ils ont le droit de stocker toutes les données qu'ils veulent tant que cet espace utilisé reste fini à tout moment. C'est donc la forme la plus abstraite et théorique de la questionque peut-on faire avec un ordinateur ?
qui est étudiée ici, et elle déborde sur des questions du typecomment peut-on imaginer des types de machines fondamentalement et théoriquement plus puissantes qu'un ordinateur même si elles ne sont pas réalisables en pratique ?
— mentionnons par exemple que même un ordinateur quantique, qui si on réussissait à en construire serait pour certains types de problèmes incroyablement plus efficace qu'un ordinateur tel que nous disposons actuellement, ne représente pas un saut qualitatif tel qu'il peut intéresser la calculabilité : pour la calculabilité, un ordinateur quantique, un ordinateur classique, un système d'engrenages mécaniques ou encore un humain extrêmement patient et systématique muni d'un stylo et d'un papier et exécutant mécaniquement des opérations prédéfinies valent exactement la même chose.)La calculabilité est un peu la mère de l'informatique, parce que c'est au travers de la recherche d'une formalisation de ce qu'est un algorithme, et ce qu'un algorithme peut faire, qu'Alonzo Church et son étudiant Alan Turing sont arrivés au concept de calculabilité ; la définition précise d'algorithme à laquelle Turing est arrivé, la machine de Turing, est considéré comme une préfiguration théorique de ce qu'est un ordinateur.
Un des thèmes majeurs de la calculabilité, donc, c'est de montrer que, pour des raisons théoriques, certains types de problèmes (mathématiquement bien posés) ne sont pas résolubles algorithmiquement : même avec un temps illimité(-mais-fini) à votre disposition, et autant de mémoire, vous ne pourrez pas écrire un algorithme qui répond à coup sûr à certaines questions qui admettent pourtant une réponse bien définie.
L'exemple archétypal à ce sujet est le problème de l'arrêt : très grossièrement, ce problème demande justement, donné un algorithme, i.e., une suite d'instructions à exécuter (qui peut, bien sûr, contenir des boucles, du type
répéter les instructions suivantes tant qu'une certaine condition n'est pas vérifiée
), et des valeurs à fournir en entrée à cet algorithme, si l'algorithme en question finit (i.e., si le calcul aboutit à un résultat). Le théorème majeur de Turing, qui est à la base de la théorie de la calculabilité (et donc, dans un certain sens, de l'informatique ; mais à l'origine il s'y intéressait pour des raisons liées à la logique mathématique et spécifiquement au théorème de Gödel), c'est qu'aucun algorithme ne peut résoudre le problème de l'arrêt : autrement dit, aucun algorithme ne peut dire à coup sûr si un autre algorithme s'arrête au bout d'un temps fini. (La seule façon de savoir est de l'exécuter, ce qu'on peut faire, mais quand on l'exécute, tant qu'il n'est pas fini, on n'est jamais sûr si le programme finira par terminer plus tard.) La raison de cette impossibilité est d'ailleurs étonnamment bête une fois qu'on a fait le travail de formalisation pour rendre rigoureuse la théorie : en gros, si un algorithme existait qui puisse dire à coup sûr si un algorithme donné s'arrête, on pourrait faire un algorithme qui l'interroge et fait le contraire de ce qu'il a prédit, ce qui le met en défaut. (C'est ce qu'on appelle unargument diagonal de Cantor
.)La calculabilité ne se contente pas, en fait, de définir des problèmes résolubles ou non résolubles algorithmiquement, et de le montrer : il y a des problèmes plus ou moins impossibles à résoudre, et l'étude des degrés d'impossibilité (par exemple les degrés de Turing dont je dirai un mot plus bas, et que je définirai précisément dans le volet technique de ce billet) est un sujet de recherche qui court depuis Turing, mais l'outil de base pour ne serait-ce que formuler ce genre de questions est la notion d'oracle que je vais chercher à introduire ici.
-
La théorie de la complexité [algorithmique], cherche à être plus fine que la calculabilité : alors que la calculabilité donne aux algorithmes l'accès à des ressources (temps, mémoire) illimitées-mais-finies, la complexité s'intéresse à des problèmes résolubles par un algorithme, mais cherche à mesurer combien de temps ou de mémoire (ou parfois d'autres ressources) un algorithme devra utiliser, en fonction de la taille du problème qu'on leur pose, lorsque cette taille devient très grande. (Par exemple, combien d'étapes faut-il pour multiplier deux nombres de 100 chiffres ? de 1000 chiffres ? de 10 000 chiffres ? Avec l'algorithme qu'on apprend à l'école primaire, la réponse est en gros 10 000, 1 000 000 et 100 000 000 respectivement, parce qu'il faut multiplier chaque chiffre du multiplicande par chaque chiffre du multiplicateur avant d'ajouter tout ça : en complexité on appelle ça un algorithme
quadratique
. En fait, on peut faire beaucoup plus efficacement, et d'ailleurs au moins un algorithme de multiplication plus efficace sur les grands nombres que l'algorithme appris à l'école primaire peut vraiment servir à la main — enfin, pourrait servir à la main si on était dans un monde où nous n'avions pas un ordinateur en permanence avec nous.)La complexité est donc une discipline un peu plus applicable au monde réel que la calculabilité : alors que la calculabilité va nous donner des réponses du type
vous ne pouvez pas résoudre ce problème avec un ordinateur, quel que soit le temps que vous soyez prêt à attendre
ououi vous pouvez, mais je n'ai aucune idée du temps nécessaire parce que ce n'est pas mon sujet
, la complexité va chercher à voir plus précisément dans la deuxième catégorie entre des problèmes théoriquement-résolubles-mais-absolument-pas-en-pratique (un peu comme si vous cherchiez à multiplier à la main deux nombres de 1 000 000 000 000 chiffres… oui, en principe c'est possible) et des problèmes un peu plus abordables en pratique. (La complexité va aussi faire la différence entre différents types d'ordinateurs qui, pour la calculabilité sont équivalents, par exemple un ordinateur quantique permet plus de choses du point de vue de la complexité parce qu'il peut en quelque sorte mener plein de calculs en parallèle ; alors qu'en calculabilité il ne change rien du tout par rapport à un ordinateur classique.)Néanmoins, la complexité reste une discipline assez théorique parce qu'elle se penche sur le temps (ou la mémoire, ou une autre ressource) utilisés
asymptotiquement
: ici,asymptotiquement
veut direquand la taille de l'entrée de notre problème (i.e. l'instance précise) devient extrêmement grande (tend vers l'infini)
. C'est-à-dire que le but de la complexité n'est pas de savoir si vous allez prendre exactement tel ou tel temps pour multiplier deux grands entiers (disons) mais comment ce temps grandit quand les entiers deviennent très grands (est-ce que doubler la taille des nombres double le temps qu'il faut pour faire la multiplication ? plus ? moins ?). Tout simplement parce que c'est un peu plus abordable comme type de question (et que c'est déjà utile dans la pratique).La complexité définit toutes sortes de catégories de problèmes en fonction de la difficulté à les résoudre, mesurée sous la forme des ressources qu'on accepte d'allouer à un algorithme qui les résout. (Par exemple, de façon approximative, un problème est dit EXPTIME ou EXPSPACE s'il existe un algorithme qui le résout et dont le temps d'exécution ou respectivement la mémoire utilisée croît au plus exponentiellement dans la taille de la donnée ; on peut faire énormément de choses avec un temps ou une mémoire exponentielle, donc énormément de problèmes sont dans ces classes, qui ne sont pas d'un grand intérêt pratique, mais c'est quand même plus restrictif que les problèmes tout simplement calculables en ressource illimitées que j'ai évoqués plus haut.)
Deux classes particulièrement importantes en calculabilité sont les classes P et NP. La classe P est très grossièrement celle des problèmes
faciles
(un peu plus précisément, ce sont ceux qui sont résolubles par un algorithme qui utilise un temps au plus polynomial dans la taille de l'entrée : linéaire, quadratique, cubique, quelque chose comme ça, mais exponentiel n'est pas permis) ; la classe NP est plus subtile : très grossièrement, ce sont les problèmesfaciles à vérifier
(mais pas forcément faciles à résoudre ; c'est-à-dire que si vous avez la réponse, la vérification qu'elle est correcte se fait essentiellement selon la classe P, mais par contre, si vous ne connaissez pas la réponse, il est possible qu'elle soit très difficile à trouver ; j'insiste sur le fait que mes explications sont très grossières et que je passe sur plein de subtilités théoriques).Un exemple de problème NP très simple à décrire est le suivant : je vous donne un tas de nombres (entiers positifs, disons) et un nombre-cible, et votre but est d'exprimer le nombre-cible comme somme de certains des nombres donnés. (C'est une variante très simple des « chiffres et les lettres » où on n'a le droit qu'à l'addition ! Ou bien imaginez que ce sont des pièces de monnaie dans un système monétaire bizarre, et vous voulez réussir à payer exactement un certain montant cible en ayant dans votre poche des pièces de certains montants donnés. Par exemple, si je vous donne les nombres 1, 3, 8, 17, 32, 51, 82, 127, 216, 329, 611, 956 et 1849, et que je vous demande de faire la somme 2146 avec, ce n'est pas évident d'y arriver sauf à tester énormément de combinaisons ; par contre, vérifier que 1 + 8 + 32 + 82 + 127 + 329 + 611 + 956 = 2146 est un calcul facile.)
Parmi les classes que j'ai pas-vraiment-définies-mais-un-peu-évoquées, on a P ⊆ NP ⊆ EXPTIME, le symbole ‘⊆’ signifiant ici
est inclus dans
, c'est-à-dire que tout problème P (facile à résoudre
) est en particulier NP (facile à vérifier
), et que tout problème NP est lui-même, en particulier, EXPTIME (résoluble en temps exponentiel
). (Ce dernier est à son tour inclus dans EXPSPACE mais peu importe.) On sait par ailleurs montrer qu'il existe des problèmes qui sont dans EXPTIME mais qui ne sont pas dans P (et on sait en décrire explicitement), autrement dit, des problèmes résolubles en temps exponentiels mais pas faciles pour autant (pas résolubles en temps polynomial) : ce n'est pas très surprenant, parce qu'une exponentielle grandit vraiment très vite, donc il n'est pas surprenant que certains problèmes puissent se résoudre en un temps exponentiel mais pas en un temps beaucoup plus limité, mais encore fallait-il le prouver (ce n'est pas très difficile, mais ce n'est pas complètement évident non plus). Bref, si voit P ⊆ NP ⊆ EXPTIME comme trois boîtes imbriquées, la plus à gauche est effectivement strictement plus petite que la plus à droite. Mais la question se pose de savoir comment est celle du milieu. En fait, on ne sait pas la situer ni par rapport à celle de gauche ni par rapport à celle de droite.Spécifiquement, une question centrale de la théorie de la complexité est de savoir si P=NP (en gros,
est-ce que tout problème facile à vérifier est, en fait, facile à résoudre ?
). On pense très fortement que la réponse estnon
(i.e., qu'il existe des problèmes qui sont dans NP et qui ne sont pas dans P ; on en a même plein de candidats, d'ailleurs celui que j'ai donné plus haut en est un), mais on ne sait pas le prouver (l'enjeu, ici, est de prouver rigoureusement qu'un problème est difficile au sens où il ne peut pas exister d'algorithme qui le résout facilement). Cette questionP≟NP
est même mise à prix à 1 000 000 $ (et attire régulièrement des « solutions » incorrectes de toutes parts).Pour en savoir plus sur la situation en complexité, cet article récent de vulgarisation (costaud !) dans le magazine Quanta, quoique long, n'est pas mauvais pour donner un aperçu, et expliquer un peu mieux que ce que je l'ai fait ce que c'est que cette histoire de P≟NP, ce qu'on sait dire à son sujet et quelle est la difficulté. Ce n'est pas vraiment mon propos ici d'en dire plus ici.
-
La cryptographie (enfin, peut-être que je devrais plutôt dire
cryptologie
ici) est l'étude scientifique de la sécurité de l'information : il s'agit de développer des techniques de chiffrement (comment transformer un message en unchiffré
qui ne puisse être déchiffré qu'en ayant accès à uneclé
) ou ayant trait à d'autres questions de sécurité de l'information (signature électronique, authenticité, non-répudiation, partage de secrets, ce genre de choses). Mais plus précisément, ici, au sein de la cryptographie, j'ai à l'esprit la cryptographie à clés publiques (voir ce billet récent pour une explication de ce que ça signifie ; ce n'est pas très important ici).Une différence importante entre la calculabilité/complexité et la cryptographie est qu'en cryptographie il y a un adversaire (par exemple, s'agissant d'un chiffrement, l'adversaire est un attaquant hypothétique qui essaie d'obtenir des informations sur le message sans avoir la clé de déchiffrement, ou peut-être sur la clé en ayant connaissance du message et du chiffré, ou des variantes autour de ces questions). En calculabilité ou en complexité on s'intéresse à la difficulté de problèmes parce que ça mettra une borne sur ce que nous pourrons faire. En cryptographie, on s'intéresse à la difficulté plutôt parce que ça peut représenter un travail pour l'attaquant (donc la difficulté est souhaitable !). Spécifiquement, on voudrait concevoir des méthodes de chiffrement qui soient faciles à utiliser (c'est-à-dire, peu coûteuses algorithmiquement) quand on connaît la clé, mais extrêmement difficiles à casser, c'est-à-dire pour l'attaquant qui ne connaît pas la clé, et si possible, on voudrait prouver cette difficulté, ou au moins avoir des raisons un peu plus tangibles que
je ne sais pas faire, donc c'est sans doute compliqué
.
Bref, dans ces trois domaines (et il y en a sans doute d'autres
dont j'ignore tout ou qui ne me viennent pas à l'esprit), pour des
raisons un peu différentes et avec des notions de problème
et
de difficulté
différentes, on peut chercher à montrer qu'un
certain problème est difficile (voire, s'agissant de la calculabilité,
impossible, mais je vais ranger ça sous l'étiquette
vague difficile
), ou étudier sa difficulté.
Bon, mais comment montre-t-on qu'un problème est difficile ?
Souvent, c'est aussi très difficile. Il y a quantité de
problèmes qu'on soupçonne fortement d'être très difficiles (qu'il
s'agisse au sens de la calculabilité, de la complexité ou de la
cryptographie, ou d'un autre sens), qui le sont assurément en
pratique, mais dont on ne sait pas prouver qu'ils sont
difficiles. Des trois domaines que j'ai évoqués ci-dessus
(calculabilité, complexité et cryptographie), la situation est de plus
en plus défavorable dans l'ordre que je viens de dire. En
calculabilité, il y a plein de problèmes dont on sait prouver
qu'ils sont difficiles (c'est-à-dire, dans ce contexte, pas résolubles
du tout), le problème archétypal à ce sujet étant le « problème de
l'arrêt » que j'ai évoqué, et les autres se « ramènent » souvent à lui
au sens que je vais tenter d'expliquer plus bas. En complexité, on ne
sait prouver rigoureusement la difficulté que de problèmes vraiment
ridiculement difficiles (par exemple les problèmes qu'on construit
pour être dans EXPTIME mais pas dans P), et toutes les
questions un peu fines, notamment celle emblématique
de P≟NP
, demeurent ouvertes ; en cryptographie,
je crois que personne n'a vraiment d'espoir d'arriver à des
preuves absolues de difficulté (il n'est même pas très clair
comment on devrait formellement énoncer la question,
d'ailleurs).
Il y a néanmoins une idée extrêmement féconde dans les trois
domaines que j'ai évoqués (calculabilité, complexité, cryptographie)
qui permet de contourner de contourner un certain nombre de questions
auxquelles on ne sait pas répondre (et aussi d'en ouvrir d'autres !),
c'est la notion de réduction ou de
difficulté relative. Je vais dire dans un instant au moins
grossièrement de quoi il s'agit (et de toute façon il y a plein de
variations autour de ce thème), mais c'est une façon de formaliser
l'idée qu'un problème Q est « au moins aussi difficile »
qu'un problème P en montrant que si on me fournit un
moyen de résoudre le problème Q alors je peux m'en servir
pour résoudre facilement le problème P
. Et comme il
s'agit cette fois d'un résultat positif, on arrive beaucoup
plus facilement à obtenir de tels résultats de « réduction ». Qui
font au moins avancer un peu des questions de difficulté qu'on ne sait
pas résoudre de façon « absolue ».
Par exemple :
- En calculabilité, une fois qu'on a établi que le problème « de
l'arrêt » est indécidable (c'est-à-dire, n'est pas résoluble par un
algorithme quelconque en temps fini-mais-illimité), on se sert de
réductions pour montrer qu'énormément de problèmes sont eux aussi
indécidables : le schéma de raisonnement est à chaque fois
si je savais résoudre le problème Q, en faisant de <telle façon> je pourrais m'en servir pour résoudre le problème de l'arrêt, or celui-ci n'est pas résoluble, donc le problème Q ne l'est pas non plus
. - En complexité, on appelle
NP-dur
un problème dont la résolution permet de résoudre facilement tout problème NP (peu importe exactement ce que c'est : seule importe l'approche générale). On ne sait pas montrer que ces problèmes NP-durs sont effectivement difficiles dans l'absolu (c'est, en gros, la question à 1 000 000 $ de savoir siP≟NP
), mais ceci donne un indice : si un problème NP-dur quelconque était facile, alors tout problème NP serait facile (P=NP), ce qui serait très surprenant ; en tout état de cause, montrer qu'un problème est NP-dur est souvent le mieux qu'on sache faire pour expliquer qu'il est difficile : ceci donne un fort indice, et on sait qu'on ne pourra pas aller plus loin sans trancher un problème ouvert célèbre. - En cryptographie, on ne sait jamais prouver la sécurité absolue
d'un système de chiffrement ou signature (note en petits caractères :
sauf quand elle l'est pour des raisons de théorie de l'information,
comme le masque
jetable). Ce qu'on appelle
preuve de sécurité
est toujours une preuve de difficulté relative, c'est-à-dire une réduction à un problème postulé difficile (la factorisation des entiers, le problème du log discret, le problème de Diffie-Hellman ou sa variante décisionnelle — peu importe ce que ce sont exactement). C'est-à-dire que l'approche par réduction est la suivante : je montre que si quelqu'un sait casser le cryptosystème étudié (là aussi, il y a plein de variantes sur ce quecasser
veut dire, avec des noms de code du styleIND-CCA2
), alors on peut s'en servir pour résoudre tel problème standard réputé difficile ; et comme implicitement on admet que le problème en question est effectivement très difficile dans l'absolu (même si on ne sait pas le prouver), ceci suggère que le cryptosystème est effectivement très difficile à casser : comme on n'a guère d'espoir d'avoir des preuves de sécurité « absolues », ces preuves par réduction sont un peu le mieux qu'on peut espérer. (Si vous voulez en savoir plus sur le sujet, je renvoie par exemple à ces slides introductives par Damien Vergnaud.)
Je passe sur énormément de détails. La manière de faire les
réductions n'est pas tout à fait la même, la terminologie n'est pas
tout à fait la même (c'est d'ailleurs un peu agaçant), mais dans les
trois cas l'approche est globalement la même : ayant accès à un
problème P que je crois difficile (dans mon premier exemple
je sais même le prouver dans l'absolu), pour argumenter qu'un
problème Q est difficile, je montre que si je sais
résoudre Q je peux m'en servir pour résoudre
facilement P
.
Bon, mais qu'est-ce que ça veut dire qu'on peut réduire
(ou ramener
) le problème P au
problème Q ? Et quel rapport avec le
mot oracle
?
Il y a toutes sortes de petites variations autour de la définition (et le but du billet technique qui est censé suivre sera de décrire certaines de ces variations), mais l'idée générale très grossière est que :
Le problème P est réductible (ou
ramenable) au problème Q quand, si on me fournit un moyen magique pour résoudre le problème Q, je peux utiliser ce moyen pour résoudre (« facilement ») le problème P.Ce moyen magique hypothétisé s'appelle un oracle.
Voici un exemple complètement stupide mais qui illustre peut-être
ce que je veux dire : le problème de trouver l'âge du capitaine est
réductible au problème de trouver l'état-civil précis du capitaine,
parce que si je trouve l'état-civil précis du capitaine, il y a sa
date de naissance dedans, et je peux facilement en déduire son âge.
(Donc, si on me donne un oracle qui est capable de me fournir
l'état-civil du capitaine d'un bateau alors cet oracle me permet de
donner l'âge du capitaine.) Et indiscutablement, ceci est une façon
d'expliquer qu'il est au moins aussi difficile de trouver
l'état-civil précis du capitaine que de trouver son âge. Les
réductions utilisées en informatique théorique sont rarement aussi
triviales (encore que parfois elles le sont), et les problèmes dont on
parle sont des problèmes mathématiquement bien définis (et
paramétriques, c'est-à-dire qu'il y a une entrée au problème — ici ça
pourrait être le bateau dont on demande l'âge du capitaine), mais
l'idée est là. Il me semble que même dans la vie courante on fait
occasionnellement appel à ce genre de raisonnements : tu te doutes
bien que je ne peux pas faire Q, sinon je pourrais aussi
faire P et je le ferais
.
Ce qu'on appelle un oracle
, c'est donc un objet théorique
(une boîte noire
, c'est-à-dire qu'on ne se préoccupe pas de
comment elle fonctionnerait à l'intérieur : « c'est magique ») qui,
quand on lui demande la réponse à un certain problème
(Q dans ma notation ci-dessus), la fournit immédiatement et
parfaitement. Et on s'interroge sur ce qu'on peut faire, ensuite,
donné un tel oracle.
Mais si c'est l'idée approximative, que j'ai décrite ici de façon
délibérément vague, il existe toutes sortes de variations autour de
cette idée. Déjà, en cryptographie, la terminologie est un peu
différente : le terme d'oracle
est le plus souvent utilisé
spécifiquement dans l'expression spécifique oracle aléatoire
,
c'est-à-dire que l'oracle répond aléatoirement (si on veut, il tire un
dé parfait à chaque fois qu'on l'interroge, à ceci près que le tirage
est enregistré en face de la question qu'on lui a posée, et que toute
répétition de la même question conduira à la même réponse), ce qui ne
semble pas très utile, et de fait ça ne l'est pas (et c'est assez
indépendant de la question de réduire un problème P à un
problème Q), mais c'est une façon de contourner le fait
qu'un ordinateur idéalisé ne possède pas de source de vrai aléa (les
primitives cryptographiques comme des fonctions de hachage sont des
imitations en plastique d'un oracle aléatoire) ; néanmoins, la notion
de réduction que j'ai évoquée ci-dessus est quand même largement
utilisée en cryptographie.
Questions de terminologie mises à part, le premier intérêt de la
notion d'oracle, c'est pour définir la notion de réduction
que
j'ai discutée ci-dessus : on dit qu'un problème P est
calculable, ou facile, ou je ne sais quoi, relativement au
problème Q, lorsqu'une machine doté d'un oracle répondant
à Q peut, ou peut facilement, ou quelque chose comme ça,
répondre au problème P : c'est là la notion de
réductibilité définie plus haut.
Si on sait (« facilement ») résoudre le problème P en disposant d'un oracle qui résout le problème Q, cette « réduction » montre que le problème Q est au moins aussi difficile que le problème P, et comme je l'ai dit cette démarche est utile en calculabilité (pour montrer que certains problèmes ne sont pas résolubles, en y réduisant un problème connu pour ne pas l'être, par exemple le problème de l'arrêt), en complexité (faute de savoir montrer que certains problèmes NP sont vraiment durs dans l'absolu, on peut au moins montrer que tout problème NP se ramène à eux) et en cryptographie (comme argument tendant à établir la sécurité d'un chiffrement).
Mais une fois qu'on a dégagé cette notion de difficulté relative, et de calcul avec oracle, on peut bien sûr l'étudier plus loin et pour elle-même : que peut-on faire avec tel ou tel oracle ?
C'est-à-dire qu'on peut se pencher sur la puissance de ce nouveau
type de dispositif de calcul : un ordinateur (enfin, une machine de
Turing
, c'est-à-dire un ordinateur idéalisé) disposant d'un oracle
résolvant tel ou tel problème fixé. C'est une généralisation de la
notion de machine sans oracle, parce qu'une machine sans oracle est
essentiellement la meme chose qu'une machine avec un oracle qui
fournit des réponses sans intérêt (par exemple, qui ne répond rien, ou
qui répond toujours 0
, quand on l'interroge). Du coup, on peut
aussi reprendre plein de questions qu'on se posait sur les machines de
Turing sans oracle et s'interroger sur la même question pour les
machines de Turing disposant d'un oracle répondant à tel ou tel
problème (soit pour un problème précis, soit n'importe quel oracle,
soit des catégories générales). Ça s'appelle relativiser la
question.
L'enjeu est alors un petit peu différent. Les oracles considérés
ne résolvent plus forcément un problème utile : on se pose plutôt des
questions du type si je donne à un ordinateur accès à un oracle qui
calcule telle fonction f, que peut-il en faire ?
(peut-être que la fonction f est faite exprès pour qu'il se
passe des choses bizarres, ou peut-être qu'on cherche à démontrer des
choses pour toute fonction f ou quelque chose comme
ça).
À titre d'exemple, en complexité, j'ai dit qu'on ne savait pas
répondre à la question P≟NP (en gros est-ce que tout
problème vérifiable facilement est résoluble facilement ?
— on
pense bien sûr que la réponse est non, ce serait trop beau, mais on ne
sait pas le prouver) ; mais cette question concerne les ordinateurs
usuels, sans oracle : on peut reposer exactement la même question en
donnant à l'ordinateur accès à un oracle (résolvant tel ou tel
problème ou telle ou telle catégorie de problèmes) : on peut montrer
que pour certains types d'oracles (fabriqués
exprès), P=NP devient vrai, et pour certains on a au
contraire P≠NP : ceci ne nous donne pas la réponse à ce
qui se passe sans oracle, mais ceci donne un indice expliquant
pourquoi la question P≟NP est difficile : une réponse ne
peut pas venir d'un argument très général, elle doit forcément faire
appel aux particularités du modèle de calcul.
En calculabilité (où, de façon générale, on sait dire beaucoup plus
de choses qu'en complexité), la notion de machines avec oracle donne
naissance à la théorie des degrés de Turing : on dit que deux
problèmes sont dans le même degré de Turing lorsqu'on
peut réduire chacun des deux à l'autre, c'est-à-dire qu'on peut
calculer la réponse à chacun des deux si on dispose d'un oracle qui
répond à l'autre : c'est une façon de dire que les deux problèmes ont
la même difficulté calculatoire (mais au sens de la calculabilité,
c'est-à-dire sans aucune limite sur les ressources disponibles :
disons peut-être plutôt la même impossibilité
calculatoire).
La notion de réduction définit un ordre sur les degrés de Turing :
dire que le problème P se réduit au problème Q
(i.e., est résoluble avec lui pour oracle) peut aussi se dire sous la
forme que le degré de Turing de P est inférieur ou égal à
celui de Q (i.e., est plus facile au sens large). L'étude
des degrés de la structure des degrés de Turing et de leur ordre est
un sujet important : si tout ce qui est calculable constitue un degré
de Turing noté 0 (le plus petit) et le problème « de l'arrêt »
en définit un autre noté 0′, ceci ouvre la voie à plein
d'autres questions et à
une vaste
théorie. Par exemple : existe-t-il des degrés entre 0
et 0′ ? (c'est-à-dire des problèmes insolubles
algorithmiquement mais auxquels on ne puisse pas non plus ramener le
problème de l'arrêt — la réponse est oui, mais il y a des variantes
autour de cette question qui sont très subtiles). On peut aussi
définir le problème de l'arrêt sur les machines à oracle : pour tout
degré de Turing d ceci définit un nouveau degré de
Turing d′, strictement plus grand, qui correspond au problème
de l'arrêt pour les machines disposant d'un oracle du degré d.
Notamment, le problème de l'arrêt pour les machines ayant elles-mêmes
accès à un oracle pour le problème de l'arrêt appartient au
degré 0′′, et on peut chercher à répéter la manœuvre de façon
transfinie (là aussi il y a des questions subtiles).
En cherchant à donner juste un aperçu (sans vraies définitions, et
juste en agitant les mains) de certaines des questions qu'on peut se
poser en théorie de la calculabilité et de la complexité, j'ai
évidemment énormément simplifié et parfois dit des choses un peu
fausses. Par exemple, j'ai agité les mains en utilisant le terme
excessivement vague de problème
, mais il aurait au moins fallu
distinguer les problèmes de décision (ceux dont la réponse
est oui
ou non
) des autres.
Je dois aussi signaler qu'il y a beaucoup de variations autour de la notion de réduction. J'ai laissé comprendre (enfin, j'espère qu'on l'aura compris) qu'elle est différente en calculabilité, où on dit que P est réductible à Q quand, donné un oracle qui répond à Q, je peux utiliser ce moyen pour résoudre le problème P algorithmiquement (en temps fini-mais-illimité), et en complexité, où on exige en plus que l'algorithme ne prenne pas trop de temps ou de mémoire (typiquement, qu'il soit de complexité P relative à l'oracle fourni). Mais il y a un autre type de distinction qui peut jouer, et qui vaut la peine d'être mentionné :
- dans la réduction de Turing, que j'avais implicitement à l'esprit en écrivant l'essentiel de ce qui précède, l'oracle fourni est interrogeable ad libitum, c'est-à-dire qu'il n'y a pas de limite sur son nombre d'utilisations (l'algorithme qui l'utilise a le droit de l'interroger autant de fois qu'il le souhaite ; bien sûr, si on parle de théorie de la complexité, il y a un coût en temps associé à cette interrogation, mais il n'est pas plus élevé que n'importe quelle opération normale de l'algorithme) ;
- dans la réduction de Weihrauch [le terme n'est pas complètement habituel, parce qu'il sert plutôt dans un contexte un peu différent, mais je n'en connais pas de meilleur], l'oracle ne peut servir qu'une seule fois, i.e., il n'acceptera de répondre qu'à une seule question (et du coup, évidemment, on peut s'interroger sur la réduction de Weihrauch à 2, 3, 4… copies du même oracle, pour autoriser de poser 2, 3, 4… questions) ;
- dans
la réduction many-to-one
(ou
réduction applicative
, je ne connais pas vraiment le terme français, s'il y en a), non seulement l'oracle ne répond qu'à une seule question mais en plus son interrogation est terminale, c'est-à-dire que la réponse de l'oracle à la question qu'on lui pose doit nécessairement fournir la réponse au problème posé initialement, on n'a pas le droit de la modifier derrière ni de travailler dessus (i.e., on dit que P est réductible many-to-one à Q lorsqu'il existe un algorithme qui, donnée une instance du problème P, fournit une instance du problème Q qui ait exactement la même réponse).
(Il y a même la réduction one-to-one qui est encore plus restrictive en ce sens que les questions posées à l'oracle pour différentes instances du problème doivent être distinctes, mais elle ne me semble pas très intéressante.)
Ces notions existent à la fois en calculabilité et en complexité,
même si en complexité on utilise parfois une terminologie gratuitement
différente (réduction de Cook
pour la réduction de Turing en
temps P et réduction de Karp
pour la
réduction many-to-one en temps P ; je ne
sais pas pourquoi la réduction de Weihrauch n'est pas plus populaire
alors qu'elle semble quand même très naturelle dès qu'on n'a pas
affaire à un problème de décision).
On peut aussi évoquer différentes variations autour de l'oracle
lui-même, et pas tellement sur son mode d'interrogation. Par exemple,
certains types d'oracles peuvent avoir des « questions interdites »
(si vous la posez, l'oracle explose et vous mourez, mais ça peut être
un problème lui-même difficile de savoir quelles questions sont
interdites) : on parle ici d'oracles partiellement définis ; certains
types d'oracles peuvent avoir plusieurs réponses possibles pour une
question (et ils vont chercher à vous embêter en vous fournissant
celle qui vous arrange le moins, ou au moins toute stratégie pour s'en
servir doit tenir compte de cette possibilité) : on parle ici
d'oracles non-déterministes. Un oracle peut éventuellement renvoyer
une information sur une infinité de questions à la fois : j'avais
notamment évoqué autrefois la notion de
machine hyperarithmétique qu'on peut voir comme une machine
disposant d'une sorte d'oracle permettant de tester une infinité de
valeurs d'une fonction (la fonction étant elle-même définie par une
machine hyperarithmétique, donc il faut être soigneux dans la
définition) : le terme technique ici est calculabilité dans une
fonctionnelle de type 2
(de type 2
parce qu'on peut aller
encore plus loin).
Je ne vais pas plus loin, mon but dans ce billet étant juste
d'expliquer comment cette notion d'oracle
ouvre la porte à
plein de questions théoriques, et je vais m'arrêter là. Mais
auparavant, voici une petite énigme que je trouve amusante et
intéressante, et qui a un rapport avec une certaine notion d'oracle
(et notamment celle que je dois expliquer dans le deuxième
volet) :
Vous êtes dans un donjon face à cinq (5) portes identiques. Deux (2) d'entre elles (au maximum) conduisent à la mort, et les autres conduisent au trésor que vous convoitez. Vous ne savez pas lesquelles. Votre but est d'ouvrir une porte au trésor.
Vous avez heureusement la possibilité d'interroger un petit lutin (plus exactement, l'Omniscient Rouspéteur Aventurier Coquin Lutin Extraordinaire) qui connaît les bonnes portes. Mais ce petit lutin n'accepte de répondre aux questions que sous une forme très particulière : pour l'interroger il faut lui dire trois (3) phrases dont au maximum une (1) est fausse : le lutin répond alors en vous disant une phrase vraie parmi celles que vous lui avez proposées. Si on enfreint la règle (en proposant au lutin des phrases dont >1 soit fausse), alors il vous tue et vous mourez, de même que si vous ouvrez une mauvaise porte.
En revanche, vous avez le droit d'interroger le lutin autant de fois que vous voulez. Mais il cherche à vous embêter en vous fournissant les réponses les moins utiles possibles (ou du moins, il faut se préparer à cette possibilité ; par exemple si on lui propose les trois phrases
la première porte est mortelle,la première porte n'est pas mortelleet2+2=4, ce qui vérifie effectivement la contrainte exigée, il va vous répondre que 2+2=4 est vrai).Comment faire pour identifier à coup sûr une porte non-mortelle ?
En tant que tel, ce problème n'est pas forcément terriblement
intéressant (je ne sais pas dire à quel point il est difficile), mais
on peut s'interroger sur la question plus générale : si on remplace 5,
2, 3, 1 dans l'énigme par
respectivement k, m, k′, m′
(avec 0<k<m et
0<k′<m′), à quelle condition peut-on
obtenir la réponse à coup sûr ? Et quelle est la bonne façon de
formuler le problème ? À quel type d'oracle
ceci
correspond-il, et peut-on en donner des exemples différents de la même
nature ? Je donnerai une réponse dans la suite prévue à ce billet,
mais je demeure perplexe quant à savoir quel est le bon cadre
théorique pour étudier ce genre de problèmes.