Go to page
 

Bibliographic Metadata

Title
Das Millionärsproblem / eingereicht von Lukas Habring
AuthorHabring, Lukas
CensorScharinger, Josef
PublishedLinz, 2017
Description58 Blätter : Illustrationen
Institutional NoteUniversität Linz, Masterarbeit, 2017
LanguageGerman
Document typeMaster Thesis
Keywords (GND)Informationsloses Beweissystem
URNurn:nbn:at:at-ubl:1-17362 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Das Millionärsproblem [1.05 mb]
Links
Reference
Classification
Abstract (German)

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.

Stats
The PDF-Document has been downloaded 35 times.