Cryptographie sans hypothèses - recherche d'un aperçu

Supposons que et qu'un algorithme de temps linéaire rapide pour SAT apparaisse demain. Soudainement, RSA n'est pas sûr, une grande partie de notre système de communication moderne est cassé et nous devons reconsidérer comment garder les secrets les uns des autres.$P = NP$

Question: Existe - t-il une bonne référence unique (ou une liste restreinte) pour obtenir une vue d'ensemble de ce qui est possible en crypto (et dans le domaine connexe de la "sécurité") sans hypothèses d'intractabilité? Cela pourrait sauver la civilisation un jour et serait également agréable à parcourir entre-temps.

Discussion: La plupart des tâches cryptographiques que nous étudions maintenant (OWF, PRG, PKE) sont prouvablement impossibles dans le monde (un monde surnommé "Algorithmica" dans un essai influent d'Impagliazzo), mais certaines choses restent possibles: communication avec un tampon à usage unique ; partage secret distribué ; récupération d'informations privées ; et quelques autres belles choses. (Certains types de mécanismes physiques tels que les boîtes verrouillées , les dispositifs implémentant le transfert inconscient et les états quantiques peuvent également être utiles. Bien sûr, il existe toujours une sorte d'hypothèse physique sur qui peut voir quelles informations.)$P = NP$

On peut distinguer la sécurité théorique de l'information (qui fonctionne contre un adversaire sans limite de calcul) et la sécurité "inconditionnelle" (qui peut nécessiter un adversaire borné, mais qui montre toujours la sécurité sous aucune hypothèse non prouvée). Je m'intéresse surtout au cas de l'info-théorie.

Pour commencer, voici une bibliographie de la sécurité de la théorie de l'information (qui, pour mes besoins, est indiscutablement longue et disparate).

Les phrases clés que vous recherchez probablement sont "cryptographie théorique de l'information" et "cryptographie quantique". La recherche de la littérature sur ces sujets se révélera beaucoup de travail du type que vous recherchez. Quelques exemples de faits saillants ci-dessous:

• Pour la confidentialité: le bloc unique, le canal d'écoute électronique Wyner, le partage secret, l'échange de clés quantiques, etc.

• Pour l'intégrité et l'authentification: fonctions de hachage universelles.

• Pour l'anonymat: communication anonyme (par exemple, réseaux DC, schémas à base d'oignons, réseaux p2p basés sur un mélange rapide de marches aléatoires), protocoles de délimitation de distance.

• Pour la sécurité basée sur des hypothèses physiques: PUF (fonctions physiquement non clonables), codes d'intégrité (Capkun et al.), Cryptographie quantique, sécurité utilisant des TPM ou du matériel inviolable.

Il existe de nombreux articles sur ces sujets; trop nombreux pour résumer tous les résultats de la littérature.

C'est une question assez complexe, car nous n'avons vraiment pas une bonne vue d'ensemble de la région. Cela est dû en partie au fait que la théorie de l'information et la communauté cryptographique ont travaillé sur des sujets similaires sans vraiment interagir suffisamment. De nombreux bons points ont été mentionnés ci-dessus. Je voudrais juste ajouter quelques observations supplémentaires:

• Nous avons eu un grand nombre d'ouvrages traitant du problème de l'accord à clé secrète (et de la communication sécurisée) avec une configuration donnée. Ici, une configuration signifie par exemple que les parties du système (disons Alice, Bob et l'adversaire Eve) partagent des informations corrélées provenant d'une distribution de probabilité tripartite. Une configuration alternative pourrait consister en des canaux bruyants (par exemple, Alice peut envoyer des informations à Bob et Eve via des canaux bruyants). De plus, Alice et Bob sont connectés via un canal de communication (qui peut ou non être authentifié). Cette ligne de travail a commencé avec Aaron Wyner dans les années 70, qui a introduit le modèle de canal d'écoute électronique, et a été nettoyé par Maurer et d'autres dans les années 90. En outre, de nombreuses techniques dans ce domaine (amplification de la confidentialité, rapprochement des informations) a finalement été utilisé dans le paramètre Quantum Key-Distribution (QKD). À ce jour, une quantité considérable de travail est en cours, par exemple dans des domaines connexes tels que les extracteurs non malléables, etc. buts.

• Au-delà du partage secret, vous trouverez un grand nombre d'ouvrages sur le calcul multipartite (MPC) théoriquement sécurisé. En particulier, la ligne de travaux initiée par le protocole BGW est tout à fait théorique.

• De plus, je ne sais pas jusqu'où va la portée de la question: si, par exemple, P = NP est vrai, mais que nous pouvons en quelque sorte justifier la présence d'un oracle aléatoire dans le ciel, alors la cryptographie symétrique est toujours possible. Parfois, de tels modèles sont en effet utilisés pour prouver la sécurité de certaines constructions cryptographiques (comme les fonctions de hachage ou les chiffrements de blocs), et les techniques sont complètement théoriques de l'information.

• Les techniques théoriques de l'information en cryptographie apparaissent également souvent comme un outil intermédiaire dans les résultats théoriques de la complexité, mais je pense que cela dépasse le cadre de la question. (Voir les travaux de Maurer sur les systèmes aléatoires et sur l'amplification indiscernable comme exemple de ce type de travail.)

Certains groupes de recherche en Europe ont poursuivi cette ligne de recherche; plus précisément, en raison de mon intérêt pour la théorie de l'information, j'ai rencontré le travail d'Ueli Maurer et de son école, qui est à la fois significatif du point de vue purement théorique de l'information (que je connais mieux) et propose également des approches pratiques de l'information sécurité théorique.

En ce qui concerne la ligne de travail ci-dessus, certains endroits que vous voudrez peut-être envisager sont la thèse de doctorat de Christian Cachin et également de Renato Renner (plus quantique).

Bien sûr, il existe une approche complètement différente avec des mots clés tels que BB84, Preskill-Shor, Artur Ekert, etc.

Ce qui précède ne reflète bien sûr que mon expérience limitée, et il existe certainement de nombreuses autres approches et lignes de travail intéressantes.