Zur Proof-Technik von Boneh-Lynn-Shacham-Gap-Signaturen

In dem Papier "Kurze Unterschriften aus der Weil-Paarung" von Boneh, Lynn und Shacham habe ich den Sicherheitsnachweis wie jede andere Unterschrift durchgesehen.

Die in diesem Artikel verwendete Technik ist jedoch ziemlich einzigartig. Anstatt die normale Interaktion zwischen Herausforderern und Gegnern zu verwenden, haben sie den Beweis in 6 Spiele unterteilt, in denen jedes Spiel nacheinander gegenüber den vorherigen Spielen erweitert wird.

Ich bin mir nicht sicher, warum sie diesen Ansatz anstelle des normalen Spiels verwendet haben. Hilft diese Art von Sicherheitsnachweis dabei, die Wahrscheinlichkeit zu verringern, oder haben sie sie nur unter dem Gesichtspunkt "leicht zu lesen und zu verstehen" gegeben?

Vielen Dank!

Die Technik, von einem Spiel zum anderen zu "hüpfen" und die Sicherheit durch eine "Abfolge von Spielen" zu beweisen, ist nicht neu. Insbesondere gibt es mehrere Artikel, in denen diese Techniken erörtert und anhand verschiedener Sicherheitsnachweise veranschaulicht werden. Die berühmten Beispiele sind:

• Sequenzen von Spielen; Ein Werkzeug zur Zähmung der Komplexität von Sicherheitsnachweisen von Victor Shoup (2006)
• Code-basierte Gameplay-Beweise und die Sicherheit der dreifachen Verschlüsselung von Mihir Bellare und Phillip Rogaway (2008). Randnotiz: Dieses Papier ist etwas schwer zu verstehen, also fangen Sie nicht mit diesem an! Die erweiterte Zusammenfassung dieses Dokuments wird in Eurocrypt 2006 unter dem Namen The Security of Triple Encryption und einem Framework für Code-basierte Gameplay-Beweise veröffentlicht .
• Ein Hinweis zu Game-Hopping-Beweisen von Alexander W. Dent (2007). Randnotiz: In diesem Artikel wird eine andere berühmte Technik vorgestellt, die in den beiden oben genannten Artikeln weggelassen wurde.

In Bezug auf Ihre Frage verwende ich ein Zitat aus dem zuletzt oben zitierten Artikel:

In einem Game-Hopping-Beweis stellen wir fest, dass ein Angreifer, der in einer bestimmten Angriffsumgebung ausgeführt wird, eine unbekannte Erfolgswahrscheinlichkeit hat. Wir ändern dann langsam die Angriffsumgebung, bis die Erfolgswahrscheinlichkeit des Angreifers berechnet werden kann. Wir haben auch die Erhöhung der Erfolgswahrscheinlichkeit des Angreifers begrenzt, die durch die Änderungen an der Angriffsumgebung verursacht wird. Somit können wir eine Grenze für die Erfolgswahrscheinlichkeit des Angreifers in der ursprünglichen Umgebung ableiten.

Der Grund für die Verwendung mehrerer Spiele ist daher, dass wir in jedem Spiel die Berechnung einer unbekannten Wahrscheinlichkeit vereinfachen, ohne sie wesentlich zu verändern. Dies geht so lange weiter, bis wir ein Spiel erreichen, in dem die Berechnung der Wahrscheinlichkeit einfach genug ist.

Die Idee, eine Folge von Spielen als Teil eines reduktionistischen Sicherheitsnachweises zu verwenden, geht den gegebenen Referenzen voraus (sie ist implizit in Arbeiten enthalten, die bis in die frühen 80er Jahre zurückreichen, wenn nicht sogar früher, und zumindest bis Ende der 90er Jahre explizit).