Certified Randomness with Optimal Rate

In der digitalen Welt ist Vertrauen ein fragiles Gut. Wenn wir online abstimmen, geheime Codes für das Banking generieren oder Anführer für dezentrale Netzwerke wählen, verlassen wir uns auf eine Zufälligkeit, die wahrhaft unvorhersehbar ist. Wenn diese Zufälligkeit vorhersagbar oder verzerrt ist, bricht das gesamte System zusammen. Seit Jahrzehnten suchen Wissenschaftler nach einem Weg, eine solche Zufälligkeit zu erzeugen, ohne darauf angewiesen zu sein, der Maschine vertrauen zu müssen, die sie generiert. Das ideale Szenario beinhaltet ein Gerät, das eine Folge von Bits – Nullen und Einsen – produziert, die so chaotisch und gleichmäßig ist, dass niemand, nicht einmal der Besitzer des Geräts, das Ergebnis im Voraus hätte erraten können. Dies ist der heilige Gral der „zertifizierten Zufälligkeit“: eine mathematische Garantie, dass der Output wahrhaft zufällig ist, überprüfbar für jeden, ohne die Notwendigkeit eines bereits existierenden geheimen Seeds.

Die Herausforderung bestand bisher darin, dass bestehende Methoden entweder eine schwache Zufälligkeit produzierten, die leicht manipuliert werden konnte, oder einen vertrauenswürdigen Menschen erforderten, der eine kleine, zufällige Startzahl bereitstellte. Eine neue Studie von Siddhartha Jain, Saachi Mutreja und Bhaskar Roberts adressiert diese fundamentale Einschränkung. Sie haben ein Protokoll entwickelt, das es einem Quantencomputer ermöglicht, zu beweisen, dass er eine Folge von Bits mit nahezu perfekter Zufälligkeit generiert hat, selbst wenn der Computer bösartig ist und die Person, die das Ergebnis prüft, vollkommen deterministisch ist und über keinerlei eigene Zufallszahlen verfügt. Dieser Durchbruch eliminiert die Notwendigkeit eines vertrauenswürdigen Startpunkts und erreicht eine Rate an Zufälligkeit, die so hoch ist, wie es theoretisch möglich ist.

Die Forscher arbeiteten innerhalb eines Rahmens, der als das Quanten-Random-Oracle-Modell bekannt ist, ein theoretisches Setting, in dem alle Parteien Zugang zu einer öffentlichen, perfekt zufälligen Funktion haben, die wie ein universeller Hash fungiert. In dieser Umgebung konstruierten sie ein System, in dem ein Quanten-Prover eine lange Bitfolge generieren und einen kurzen Beweis liefern kann, dass die Folge tatsächlich zufällig ist. Die entscheidende Innovation besteht darin, dass der Verifizierer, der den Beweis prüft, nicht selbst zufällig sein muss; er kann ein fixer, deterministischer Algorithmus sein. Frühere Versuche, dies zu erreichen, scheiterten entweder daran, eine hohe Qualität der Zufälligkeit zu garantieren, oder beruhten darauf, dass der Verifizierer einen kleinen, vertrauenswürdigen Zufalls-Seed benötigte, um den Prozess anzustoßen. Das neue Protokoll eliminiert diesen Seed vollständig und beweist, dass ein deterministischer Verifizierer dennoch von der Zufälligkeit einer langen Folge überzeugt werden kann, die von einem nicht vertrauenswürdigen Quantengerät generiert wurde.

Um die Bedeutung zu verstehen, muss man betrachten, was passiert, wenn ein System nicht perfekt zufällig ist. Wenn eine Bitfolge nur „schwach“ zufällig ist, mag sie zwar chaotisch erscheinen, könnte aber dennoch zu bestimmten Mustern verzerrt sein, was sie anfällig für Vorhersagen macht. Die Forscher bewiesen, dass ihre Methode ein Niveau an Entropie, oder Unordnung, garantiert, das nahezu maximal ist. In praktischen Begriffen bedeutet dies, dass für eine Bitfolge einer spezifischen Länge die Anzahl der Bits, die wahrhaft unvorhersehbar sind, fast der gesamten Länge der Folge entspricht. Der einzige winzige Verlust an Zufälligkeit ist eine logarithmische Menge, die aufgrund der Natur der Gesetze der Physik und der Berechnung unvermeidlich ist. Dies ist eine enorme Verbesserung gegenüber früheren Methoden, die oft Folgen produzierten, bei denen die Menge der garantierten Zufälligkeit nur einen winzigen Bruchteil der Gesamtlänge ausmachte.

Das Protokoll arbeitet in zwei Hauptphasen. Zuerst generiert das Quantengerät eine „schwach“ zufällige Quelle unter Verwendung einer spezifischen mathematischen Konstruktion, die als sicher gegen Quantenangriffe bewiesen wurde. Diese Quelle ist noch nicht gut genug für Anwendungen mit hohem Einsatz. In der zweiten Phase leitet das Gerät diese Quelle durch eine Kompressionsfunktion, die wie ein Filter wirkt. Dieser Filter verdichtet die schwache Quelle zu einer kürzeren, viel stärkeren Bitfolge. Die Forscher demonstrierten, dass selbst wenn ein Angreifer versucht, den Prozess durch die Wahl spezifischer Eingaben oder die Beobachtung des Verhaltens der Funktion zu manipulieren, er den endgültigen Output nicht vorhersagbar machen kann. Die finale Folge behält ein hohes Maß an Min-Entropie bei – ein Maß dafür, wie schwer es ist, das wahrscheinlichste Ergebnis zu erraten, selbst wenn der Angreifer die gesamte Historie der Interaktion gesehen hat.

Eine kritische Komponente dieser Arbeit ist das Konzept der „bedingten“ Min-Entropie. In vielen realen Anwendungen, wie etwa einem öffentlichen Zufalls-Beacon, der jede Stunde eine neue Zufallszahl überträgt, hängt die Sicherheit der aktuellen Zahl davon ab, dass sie nicht vorhergesagt werden kann, selbst wenn ein Angreifer alles über die vorangegangenen Zahlen weiß. Die Forscher zeigten, dass ihr Protokoll garantiert, dass jeder neue Impuls an Zufälligkeit unvorhersehbar ist, selbst wenn er auf alle Nachrichten und Daten konditioniert ist, die zuvor kamen. Dies ist essenziell für Anwendungen wie die Leader-Election in Blockchain-Netzwerken oder die Generierung gemeinsamer Zufallsstrings für kryptografische Protokolle, bei denen die Integrität der aktuellen Runde auf der Unvorhersehbarkeit der Vergangenheit beruht.

Das Team befasste sich auch mit der Ehrlichkeit bezüglich der Grenzen ihrer eigenen Arbeit. Sie bewiesen, dass es unmöglich ist, eine perfekte, uniforme Zufälligkeit mit einem deterministischen Verifizierer zu erreichen, wenn der Angreifer es erlaubt ist, für eine polynomielle Zeit zu operieren. Ein Angreifer könnte theoretisch eine Technik namens Rejection Sampling anwenden, um eine kleine Anzahl von Bits im Output festzulegen, was effektiv dazu führt, das System zu „überlisten“, um ein leicht verzerrtes Ergebnis zu erzeugen. Die Forscher zeigten jedoch, dass ihr Protokoll das bestmögliche Ergebnis unter diesen Einschränkungen erzielt: Es garantiert, dass die Anzahl der Bits, die ein Angreifer fixieren kann, so gering ist, dass die verbleibende Zufälligkeit für alle praktischen kryptografischen Zwecke immer noch ausreichend ist. Der Verlust ist vernachlässigbar, und die Sicherheit hält jedem Angreifer mit realistischer Rechenleistung stand.

Diese Arbeit hat unmittelbare Auswirkungen auf die Zukunft sicherer Kommunikation und dezentraler Systeme. Durch die Entfernung der Notwendigkeit eines vertrauenswürdigen Seeds ermöglicht das Protokoll die Erstellung von Zufalls-Beacons, die auf einem einzelnen, nicht vertrauenswürdigen Quantengerät laufen können. Ein solcher Beacon könnte periodisch frische, unvorhersehbare Zufallszahlen veröffentlichen, die von jedem überprüft werden können. Die Sicherheit dieser Zahlen würde nicht vom ehrlichen Verhalten des Gerätebetreibers abhängen, sondern von den Gesetzen der Quantenmechanik und der mathematischen Struktur des Protokolls selbst. Während die aktuelle Implementierung auf theoretischen Modellen beruht, ist der Weg zur praktischen Anwendung klarer denn je und bietet einen Weg, die vertrauenswürdige Zufälligkeit zu generieren, die die moderne digitale Gesellschaft dringend benötigt, ohne dass wir der Maschine vertrauen müssen.

Die Studie stellt eine definitive Antwort auf eine Frage dar, die von früheren Forschern hinsichtlich der Grenzen zertifizierter Zufälligkeit gestellt wurde. Sie bestätigt, dass, während perfekte Uniformität für einen deterministischen Verifizierer mathematisch unerreichbar ist, ein Niveau an Zufälligkeit, das praktisch ununterscheidbar von perfekter Zufälligkeit ist, erreichbar ist. Die Forscher haben nicht nur die Rate der Zufälligkeit verbessert, sondern die Grenzen dessen neu definiert, was in einer vertrauenslosen Umgebung möglich ist. Ihre Konstruktion bietet eine robuste, bedingungslose Sicherheitsgarantie im Quanten-Random-Oracle-Modell und setzt einen neuen Standard dafür, wie wir über Zufälligkeit im Quantenzeitalter denken. Das Ergebnis ist ein Protokoll, das sowohl theoretisch fundiert als auch praktisch relevant ist und die Lücke zwischen abstrakter Quantentheorie und den konkreten Bedürfnissen einer sicheren digitalen Infrastruktur schließt.