Limites sur les conséquences démontrables des permutations à sens unique

Nous présentons des preuves solides que l'implication, « si des permutations à sens unique existent, alors un accord de clé secrète sécurisé est possible », n'est pas démontrable par des techniques standard. Étant donné que les deux côtés de cette implication sont largement considérés comme vrais dans la vie réelle, prouver que l'implication est fausse nécessite un nouveau modèle. Nous considérons un monde où toutes les parties ont accès à une boîte noire pour une permutation choisie au hasard. Étant totalement aléatoire, cette permutation sera fortement à sens unique de manière démontrable et théorique de l'information. Nous montrons que, si P = NP, aucun protocole d'accord de clé secrète n'est sécurisé dans un tel cadre. Ainsi, prouver qu'un protocole d'accord de clé secrète utilisant une permutation à sens unique comme boîte noire est sécurisé est aussi difficile que prouver que P ≠ NP. Nous obtenons également, comme corollaire, qu'il existe un oracle par rapport auquel l'implication est fausse, c'est-à-dire qu'il existe une permutation à sens unique, pourtant l'échange secret est impossible. Ainsi, aucune technique qui relativise ne peut prouver que l'échange secret peut être basé sur une permutation à sens unique. Nos résultats présentent un cadre général pour prouver des énoncés du type, « L'application cryptographique X n'est probablement pas possible basé uniquement sur l'hypothèse de complexité Y ».