Unknowable Math Can Help Hide Secrets
Kurt Gödel a montré que pour tout système raisonnable d'axiomes, on ne peut pas prouver qu'il ne produira pas de contradictions, révélant des limites fondamentales du connaissable en mathématiques. Les preuves à divulgation nulle de connaissance, inventées par Shafi Goldwasser, Silvio Micali et Charles Rackoff, permettent à un démonstrateur de convaincre un vérificateur qu'une solution à un problème de type NP est correcte sans en révéler la solution elle-même. En 1994 Oded Goldreich et Yair Oren ont démontré qu'une preuve non interactive ne peut satisfaire la définition classique de zéro-connaissance, ce qui semblait rendre impossibles des preuves non interactives aussi confidentielles que les preuves interactives. Le chercheur Rahul Ilango a exploité des assertions considérées comme pratiquement impossibles à prouver en complexité de preuve pour définir une notion de « zéro-connaissance effective » autorisant des preuves non interactives dont le secret repose sur les limites fondamentales des mathématiques. Ce résultat contourne l'impossibilité antérieure et a stimulé de nouvelles recherches sur les interactions entre logique mathématique, complexité des preuves et cryptographie.