Zur Seitenansicht
 

Titelaufnahme

Titel
Das Millionärsproblem / eingereicht von Lukas Habring
AutorInnenHabring, Lukas
Beurteiler / BeurteilerinScharinger, Josef
ErschienenLinz, 2017
Umfang58 Blätter : Illustrationen
HochschulschriftUniversität Linz, Masterarbeit, 2017
SpracheDeutsch
DokumenttypMasterarbeit
Schlagwörter (GND)Informationsloses Beweissystem
URNurn:nbn:at:at-ubl:1-17362 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist gemäß den "Hinweisen für BenützerInnen" verfügbar
Dateien
Das Millionärsproblem [1.05 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Das Millionärsproblem befasst sich mit dem Vergleichen von geheimen Zahlen. Die Lösung dieses Problems gehört daher in die Kategorie der sogenannten Zero-Knowledge Protokolle. Das sind Protokolle, bei denen Alice geheime Daten besitzt, die sie Bob nicht zugänglich machen will. Trotzdem will Alice Bob gegenüber beweisen, dass diese geheimen Daten gewisse Eigenschaften erfüllen. Der Name „Millionärsproblem“ entstand aus dem Gedanken heraus, dass Alice und Bob Millionäre seien, die dem jeweils anderen den Erfolg nicht gönnen. Beide wollen nicht, dass der jeweils andere weiß, wie viel sie genau besitzen. Die Aufgabe ist nun, die Geldsummen zu vergleichen. Dabei soll mathematisch beweisbar auf keinen Fall mehr Information übertragen werden als das Ergebnis des Vergleichs. Im Wesentlichen gibt es zwei Arten von Vergleichen, die durchgeführt werden können. Einerseits kann man testen, ob die Werte gleich oder ungleich sind. Andererseits ist es auch möglich, zu prüfen, ob eine Zahl kleiner oder gleich der anderen ist oder nicht. Diese beiden Arten des Vergleichs führen zu grundlegend unterschiedlichen Algorithmen und werden daher im Folgenden getrennt behandelt. Das Prüfen auf Gleichheit wird auch als das sozialistische Millionärsproblem bezeichnet, während das Prüfen auf kleiner gleich einfach das Millionärsproblem ist. Bei beiden Testarten besteht das Ergebnis aus einem einzigen Bit an Information. Es ist selbstverständlich auch möglich, beide Tests durchzuführen, damit zwischen den drei möglichen Zuständen kleiner, gleich und größer unterschieden werden kann.

Statistik
Das PDF-Dokument wurde 38 mal heruntergeladen.