Kryptographie ohne Annahmen - auf der Suche nach einem Überblick

25

Angenommen, und ein schneller linearer Zeitalgorithmus für SAT erscheinen morgen. Plötzlich ist RSA unsicher, ein Großteil unseres modernen Kommunikationssystems ist kaputt und wir müssen überdenken, wie wir Geheimnisse voneinander fernhalten können.P=NP

Frage: Gibt es eine gute Einzelreferenz (oder Kurzliste), um einen umfassenden Überblick darüber zu erhalten, was in der Kryptografie (und im verwandten Bereich der "Sicherheit") ohne Annahmen zur Unlösbarkeit möglich ist? Dies könnte eines Tages die Zivilisation retten und wäre in der Zwischenzeit auch schön zu lesen.

Diskussion: Die meisten der derzeit untersuchten kryptografischen Aufgaben (OWFs, PRGs, PKE) sind in der Welt (einer Welt, die in einem einflussreichen Aufsatz von Impagliazzo als "Algorithmica" bezeichnet wird ) nachweislich unmöglich , aber einige Dinge bleiben möglich: Kommunikation mit eine einmalige Auflage ; verteilte geheime Weitergabe ; Abrufen privater Informationen ; und einige andere schöne Dinge. (Bestimmte physikalische Mechanismen, wie z. B. gesperrte Boxen , Geräte, die eine vergessene Übertragung implementieren , und Quantenzustände können ebenfalls nützlich sein. Natürlich gibt es immer eine physikalische Annahme darüber, wer welche Informationen sehen kann.)P=NP

Man kann zwischen informationstheoretischer Sicherheit (die gegen einen rechnerisch unbegrenzten Gegner arbeitet) und "bedingungsloser" Sicherheit (die möglicherweise einen begrenzten Gegner erfordert, aber dennoch Sicherheit ohne unbewiesene Annahmen zeigt) unterscheiden. Am meisten interessiert mich der info-theoretische Fall.

Für den Anfang ist hier eine Bibliographie zur informationstheoretischen Sicherheit (die für meine Zwecke unüberschaubar lang und unterschiedlich ist).

Andy Drucker
quelle
Schöne Frage, das ist nicht wirklich eine Antwort, aber es könnte von Interesse sein. Alfred Menezes und Neal Koblitz haben eine schöne Reihe von "Another Look" -Papieren, in denen sie einige Fragen stellen, die Ihren eigenen ähnlich sind, aber sich auch mit der gesamten Richtung "Sicherheitsmodelle" befassen. Ich habe es in dieser Antwort kurz besprochen , bin mir aber nicht sicher, ob dies für einen Ansatz zu zutreffend ist.
Artem Kaznatcheev
3
Ich würde vermuten, dass man mit einem solchen SAT-Algorithmus selbst Alternativen zu aktuellen PKCs und bedingungslos sicheren Systemen finden kann.
T ....
Beachten Sie, dass RSA nicht NP-vollständig ist. Wenn Sie also P = NP zum Faktorisieren benötigen, kann dies zu einem Overkill führen.
User834
ein großer Teil der modernen Krypto Scharniere auf Widerspenstigkeit Annahmen nicht zur Vereinfachung / Bequemlichkeit , sondern weil keine besseren Ergebnisse / beweisbar Grenzen sind aus der Komplexitätstheorie (va durchschnittlicher Fall Komplexität) zur Verfügung ... siehe auch crypto.se
VZN
3
Hier ist eine Umfrage von Ueli Maurer, die zwar schon etwas älter, ist recht informativ: ftp.inf.ethz.ch/pub/crypto/publications/Maurer99.pdf

Antworten:

16

Die Schlüsselphrasen, nach denen Sie wahrscheinlich suchen, sind "informationstheoretische Kryptographie" und "Quantenkryptographie". Das Durchsuchen der Literatur zu diesen Themen wird eine Menge Arbeit der Art ergeben, nach der Sie suchen. Einige beispielhafte Highlights:

  • Für die Vertraulichkeit: das One-Time-Pad, der Wyner-Abhörkanal, die geheime Freigabe, der Austausch von Quantenschlüsseln usw.

  • Für Integrität und Authentifizierung: universelle Hash-Funktionen.

  • Für Anonymität: anonyme Kommunikation (z. B. DC-Netze, zwiebelbasierte Schemata, p2p-Netze, die auf schnellem Mischen von Zufallsläufen basieren), entfernungsbegrenzende Protokolle.

  • Aus Sicherheitsgründen, die auf physikalischen Annahmen beruhen: PUFs (physikalisch nicht klonbare Funktionen), Integritätscodes (Capkun et al.), Quantenkryptographie, Sicherheit mit TPMs oder manipulationssichere Hardware.

Es gibt viele Artikel zu diesen Themen; zu viele, um alle Ergebnisse in der Literatur zusammenzufassen.

DW
quelle
Danke DW. Ich weiß, es ist zu viel Grund, eine Antwort zu formulieren. Ich hoffe, nützliche Bücher oder Umfragen zu finden.
Andy Drucker
@AndyDrucker, meine Empfehlung wäre, die wichtigsten oder neuesten Artikel zu den für Sie interessanten Themen zu lesen. Ich bin mir nicht sicher, ob Sie ein Buch finden werden, das alle Arbeiten in diesem Bereich behandelt (von denen einige in den letzten 5 bis 10 Jahren erschienen sind). Selbst wenn Sie Glück haben und ein Buch entdecken, wird es bereits in den Regalen hinter der neuesten Forschungsliteratur zurückbleiben.
DW
2
Ich strebe nicht einmal den Stand der Technik an. Es gibt kein wirklich aktuelles Lehrbuch für irgendeinen Bereich von TCS; Dennoch kann man Goldreichs Bücher aufgreifen und sich an den grundlegenden Ergebnissen und Konzepten der komplexitätsbasierten Krypto orientieren. Ich fragte mich, ob etwas Ähnliches für die info-theoretische Seite aufgetaucht war.
Andy Drucker
4

Dies ist eine ziemlich komplexe Frage, da wir wirklich keinen guten Überblick über das Gebiet haben. Dies liegt zum Teil daran, dass die Informationstheorie und die Krypto-Community an ähnlichen Themen gearbeitet haben, ohne wirklich genug miteinander zu interagieren. Viele gute Punkte wurden oben gegeben. Ich möchte nur ein paar zusätzliche Bemerkungen hinzufügen:

  • Wir hatten eine Vielzahl von Arbeiten, die sich mit dem Problem der Geheimschlüsselvereinbarung (und der sicheren Kommunikation) bei einem bestimmten Setup befassten. Hier bedeutet ein Setup zum Beispiel, dass die Parteien im System (etwa Alice, Bob und die gegnerische Eva) einige korrelierte Informationen teilen, die aus einer dreigliedrigen Wahrscheinlichkeitsverteilung stammen. Ein alternatives Setup kann aus lauten Kanälen bestehen (z. B. kann Alice Informationen über lauten Kanäle an Bob und Eve senden). Zusätzlich sind Alice und Bob über einen Kommunikationskanal verbunden (der authentifiziert sein kann oder nicht). Diese Linie begann mit Aaron Wyner in den 70er Jahren, der das Wiretap-Kanalmodell einführte, und wurde in den 90er Jahren von Maurer und anderen weiter aufgeräumt. Auch viele Techniken in diesem Bereich (Datenschutzerweiterung, Information Reconciliation) wurde in der Einstellung Quantum Key-Distribution (QKD) verwendet. Hier wird bis heute einiges an Arbeit geleistet, zum Beispiel in verwandten Bereichen wie nicht verformbaren Extraktoren usw. Das Modell der gebundenen Lagerung ist ebenfalls eine Einstellung, die sich von den obigen unterscheidet, jedoch ähnliche Techniken verwendet und ähnliche Eigenschaften aufweist Tore.

  • Abgesehen von der geheimen Weitergabe finden Sie eine Vielzahl von Arbeiten zur informationstheoretisch sicheren Mehrparteienberechnung (MPC). Insbesondere der durch das BGW-Protokoll initiierte Arbeitsbereich ist vollständig informationstheoretisch.

  • Ich bin mir auch nicht sicher, wie weit der Rahmen der Frage reicht: Wenn zum Beispiel P = NP tatsächlich gilt, wir aber die Anwesenheit eines zufälligen Orakels am Himmel irgendwie rechtfertigen können, ist symmetrische Kryptographie immer noch möglich. Manchmal werden solche Modelle tatsächlich verwendet, um die Sicherheit bestimmter kryptografischer Konstruktionen (wie Hash-Funktionen oder Blockchiffren) zu beweisen, und die Techniken sind vollständig informationstheoretisch.

  • Informationstheoretische Techniken in der Kryptographie kommen auch häufig als Zwischeninstrument für komplexitätstheoretische Ergebnisse zum Einsatz, aber ich denke, dies würde den Rahmen der Frage sprengen. (Siehe Maurers Arbeit zu Zufallssystemen und zur Verstärkung der Unterscheidbarkeit als Beispiel für diese Art von Arbeit.)

Stefano Tessaro
quelle
"wir können irgendwie das Vorhandensein eines zufälligen Orakels am Himmel rechtfertigen" wovon redest du hier genau? Wie ist hier eine symmetrische Krypta mit öffentlichem Schlüssel möglich?
T ....
1
@JA Ich glaube, er meint Bellares und Rogaways zufälliges Orakelmodell , siehe z . B. cseweb.ucsd.edu/~mihir/papers/ro.html . Dieses Modell ist heuristisch, oft nützlich, aber es gibt gute Gründe, skeptisch zu sein: arxiv.org/abs/cs/0010019
Sasho Nikolov
ic .. was genau ist hier los? Haben Sie eine konkrete Idee? Alle infotheoretischen symmetrischen Schlüsselschemata, die ich gesehen habe, basieren auf dem Extrahieren gemeinsamer Informationen aus korrelierten und können daher möglicherweise nicht in eine öffentliche Schlüsselversion umgewandelt werden. Gibt es hier eine grundlegende Idee, die eine praktikable Verschlüsselungslösung mit öffentlichem Schlüssel ermöglicht, die info-theoretisch sicher ist?
T ....
2
Lassen Sie mich näher ausführen: In dem Zufalls-Orakel-Modell, in dem alle Parteien Zugang zu einem Zufalls-Orakel RO haben, können ehrliche Parteien, die einen geheimen Schlüssel SK besitzen, eine Nachricht M sicher als (R, M + RO (SK || R)) verschlüsseln, wobei R ist die Zufälligkeit der Verschlüsselung (und wird bei jeder Verschlüsselung neu generiert), + bedeutet bitweise xoder (hier wird angenommen, dass die Ausgabelänge von RO gleich der Nachrichtenlänge ist). Die Sicherheit dieses Schemas beruht nur darauf, dass das Zufallsorakel zufällig ist. Im Gegensatz dazu ist nach den Arbeiten von Impagliazzo und Rudich bekannt, dass eine Verschlüsselung mit öffentlichen Schlüsseln im Zufalls-Orakel-Modell nicht erreichbar ist.
Stefano Tessaro
3

Einige Forschungsgruppen in Europa haben diese Forschungsrichtung verfolgt. Insbesondere bin ich aufgrund meines Interesses an der Informationstheorie auf die Arbeit von Ueli Maurer und seiner Schule gestoßen, die sowohl aus rein informationstheoretischer Sicht (mit der ich vertrauter bin) von Bedeutung ist als auch einige praktische Herangehensweisen an die Information bietet theoretische Sicherheit.

Im Zusammenhang mit der obigen Arbeit sind einige Orte, die Sie in Betracht ziehen sollten, die Doktorarbeit von Christian Cachin und auch Renato Renner (mehr Quantum).

Natürlich gibt es einen ganz anderen Ansatz mit Stichwörtern wie BB84, Preskill-Shor, Artur Ekert usw.

Das oben Gesagte spiegelt natürlich nur meine begrenzten Erfahrungen wider, und es gibt sicherlich noch viele weitere Ansätze und interessante Arbeitsbereiche.

Mohammad Bayer
quelle