Abstract:
Die meisten Sicherheitsbegriffe, die heutzutage benutzt werden, stammen aus den 1980ern.
Doch durch ein seitdem besseres Verständnis der Theorie stellt sich die Frage, ob sie nicht weiterentwickelt werden können.
Ein begrenzender Faktor sind hierbei sogenannte Unmöglichkeitsbeweise, die mathematisch beweisen, welche Sicherheitsgarantien nicht erfüllt werden können.
Diese liefern einen begrenzenden Faktor, ihre Aussage sollte jedoch nicht übertrieben werden.
Der Beweis ist nur in seinem eigenen Setting gültig und deckt nur genau den einen Sicherheitsbegriff ab.
Historisch haben sich die etablierten Sicherheitsbegriffe jedoch zu etwas deutlich schwächerem entwickelt, wodurch eine Lücke zwischen dem entstanden ist, was praktisch benutzt wird, und dem, was bekanntermaßen unmöglich ist.
... mehr
In dieser Promotion zeigen wir einige dieser Lücken auf und untersuchen Sicherheitsbegriffe, die mit Sicherer Mehrparteienberechnung (MPC) zusammenhängen,
und die zwischen den Etablierten und den Unmöglichen liegen.
Abbildung von Geschäftsmodellen und Gesetzlichen Regelungen in MPC.
Mit Sicherer Mehrparteienberechnung (MPC) können Parteien eine Funktion über privaten Eingaben auf sichere Weise so berechnen, dass nichts über die Eingaben der anderen Parteien bekannt wird außer die Ausgabe der Funktion.
Heutzutage hat MPC nur einen vergleichsweise geringen Mehraufwand im Vergleich zur direkten Berechnung.
Und obwohl Datensparsamkeit in der Praxis belohnt wird, wird MPC kaum benutzt.
Wir glauben dass einer der Gründe dafür, dass MPC in Praxis kaum benutzt wird, darin liegt, dass es Geschäftsmodelle und gesetzliche Regelungen ignoriert die eine gewisse Leakage der Daten benötigen, während allgemeines MPC auf fast-perfekte Privatsphäre hinarbeitet.
Wir präsentieren einen neuen Baustein, der es Geschäften---die durch einen zentralen Operator repräsentiert werden---ermöglicht, effizient die gewünschte Menge an Leakage abzubilden, die benötigt wird, um das Geschäft aufrechtzuerhalten oder um gesetzliche Vorgaben zu erfüllen, während Nutzer anonym und ohne durch mehrere Interaktionen hinweg verlinkt werden können Daten sammeln.
Wir modellieren die Anforderungen im Universal Composability (UC) Framework.
Dadurch wird garantiert, dass die Sicherheitsgarantien unabhängig davon halten, welche Protokolle parallel ausgeführt werden.
Trotz dieser starken Sicherheitsgarantien ist das Protokoll dabei effizient genug, um auf moderner Hardware ausgeführt zu werden, selbst wenn der Nutzer die Daten auf Smartphones mit beschränkter Rechenleistung sammeln.
(Fetzer, Keller, Maier, Raiber, Rupp, Schwerdt, PETS 2022)
Eine Instantiierung stärkerer Commitments.
Mit einem Bit Commitment Schema kann sich ein Sender gegenüber eines Empfängers auf ein Bit festlegen, ohne das dabei zu offenbaren (hiding), aber auf eine Art die es dem Sender nicht erlaubt, den Empfänger später davon zu überzeugen, dass das Commitment auf ein anderes Bit festgelegt wurde (binding).
In der Quantenwelt sind Commitments stark genug, um MPC zu konstruieren, weswegen es einen Anreiz gibt, Commitments so sicher wie möglich zu machen;
jedoch sagen Unmöglichkeitsbeweise aus, dass beide Sicherheitsbegriffe -- hiding und binding -- gleichzeitig nicht bedingungslos halten können.
Als Konsequenz weichen moderne Bit Commitment Schemas eine Sicherheitseigenschaft auf, die dann nur noch computationally halten, also auf Grundlage komplexitätstheoretischer Annahmen.
Wir stellen das erste Bit Commitment Protokoll im Quantum Random Oracle Modle (QROM) vor, das bedingungslose Sicherheit für den Empfänger (binding) und langfristige Sicherheit für den Sender (hiding) bietet und das dabei keine Zusatzhardware benötigt.
Unser Resultat basiert auf einer neuen Annahme über die Schwierigkeit, Quantenzustände über einen langen Zeitraum zu speichern.
Langfristige Sicherheit modelliert technischen Fortschritt des Angreifers, da Transkripte, die heutzutage nicht effizient gebrochen werden können, in Zukunft vielleicht einfach extrahierbar sind, sobald schnellere Maschinen verfügbar sind.
Wir beweisen die Sicherheit des Commitment Protokolls im QROM unter oben genannter Annahme und zeigen, dass eine Instantiierung im Standardmodell zu einem neuen Angriff auf die langfristige Hiding-Eigenschaft zulässt.
(Döttling, Koch, Maier, Mechler, Müller, Müller-Quade, Tiepelt, IN EINREICHUNG)
Undetectable Multi-Party Computation.
Covert MPC ist eine Erweiterung von MPC, die nicht nur die Eingaben versteckt, sondern das gesamte Vorhandensein der Berechnung.
Teilnehmer lernen nur dann die Ausgabe, wenn alle anderen Parteien das Protokoll ausgeführt haben und die Ausgabe für alle Parteien vorteilhaft ist.
Anderenfalls lernen die Teilnehmer nichts, nicht mal, welche anderen Parteien versucht haben, an der Berechnung teilzunehmen.
Ein einzelner Nichtteilnehmer kann unabsichtlich die gesamte Berechnung abbrechen.
Daher stellt sich die Frage:
können $N$ Teilnehmer eine Berechnung ausführen, während $K > N$ Parteien anwesend sind, und bei der die Ausgabe nur von den Eingaben der $N$ Teilnehmer abhängt, während die Identität der anderen Teilnehmer unter den anwesenden Parteien versteckt wird?
Dies sollte insbesondere dann gelten, wenn die restlichen Parteien nicht wissen, dass eine Berechnung im Gang ist.
Wir verknüpfen diese Frage mit der theoretischen Machbarkeit von Anonymen Whistleblowing, bei dem eine einzelne Partei versucht, eine Nachricht preiszugeben, ohne dabei die eigene Identität zu offenbaren und ohne dass sich die anderen Parteien auf irgendeine besondere Art verhalten müssen.
Leider zeigen wir dass keine Primitive sowohl Korrektheit und Anonymität mit überwältigender Wahrscheinlichkeit im asymptotischen Setting erreichen kann, selbst unter sehr starken Annahmen.
Jedoch konstruieren wir eine heuristische Instantiierung im Fine-Grained setting mit überwältigender Korrektheit und jeder beliebigen Ziel-Anonymität.
Unsere Ergebnisse liefern starke Grundlagen für die Untersuchung der Möglichkeit von Anonymen Nachrichtentransfer durch authentifizierte Kanäle, ein faszinierendes Ziel von dem wir glauben, dass es von grundlegendem Interesse ist.
(Agrikola, Couteau, Maier, TCC 2022)
Abstract (englisch):
Most of the security notions used which are currently used originate from the 1980s.
Yet a better understanding of the theory since then opens the question whether they can be refined.
A limiting factor here are so-called impossibility proofs, which prove mathematically which security guarantees cannot be fulfilled.
These provide a limiting factor, yet their statement should not be overstated.
The proof is only valid in its own setting and only covers one specific security notion.
Historically, the established security notions settled for something much weaker, leaving a gap between what is practically used and what is known to be impossible.
... mehr
In this thesis, we shed light on some of these gaps and investigate security notions related to Secure Multi-Party Computation (MPC) lying between those that have been established and those that are known to be impossible.
Modelling Business Models and Legal Regulations with MPC.
With Secure Multi-Party Computation (MPC), parties can securely compute a function on private inputs in such a way, that no information on the other parties inputs is leaked except for the functions output.
Nowadays, MPC only has a relatively small overhead over the direct computation.
Yet even though data economy is incentivized in practice, MPC is not often used in practice.
We believe that one of the reasons MPC is rarely used in practice is that it ignores business models and legal requirements that require a certain amount of leakage for the data, while generic MPC aims for near-perfect privacy.
We present a novel building block that enables businesses---represented by a central \emph{operator}---to model the desired amount of leakage required to maintain business or to fulfill the legal requirements efficiently, while letting users collect data anonymously and without being linked throughout interactions.
We model the requirements in the Universal Composability (UC) framework.
This guarantees that security holds regardless which protocols are executed in parallel.
Despite strong security guarantees the protocol is still efficient enough to be executed on state-of-the-art hardware, even if the user collect data on smartphones which have limited computation power.
Fetzer, Keller, Maier, Raiber, Rupp, Schwerdt, PETS 2022
An Instantiation of Stronger Commitments.
A bit commitment scheme allows a sender to fix a bit towards a receiver without revealing it in the process (hiding), but such that the sender cannot convince the receiver that the commitment was on a different bit (binding).
In the quantum world, commitments are strong enough to provide MPC, so there is a strong incentive to make commitments as secure as possible;
yet impossibility results state that both security properties---hiding and binding---cannot simultaneously hold unconditionally.
As a consequence, modern bit commitment schemes relax one property to hold only computationally, i.e. based on a computational hardness assumption.
We introduce the first bit commitment protocol in the QROM that achieves unconditional security for the receiver (binding) and everlasting security for the sender (hiding) and that does not require additional hardware.
Our result is based on a new assumption on the hardness of storing quantum states over a long period of time.
Everlasting security models technical progress of the adversary, as a transcript that cannot be efficiently broken nowadays might be easy to extract once faster machines are available.
We prove the commitment protocol secure in the QROM under the aforementioned assumption and note that an instantiation in the standard model leads to a new attack on the everlasting hiding property.
Döttling, Koch, Maier, Mechler, Müller, Müller-Quade, Tiepelt, IN SUBMISSION
Undetectable Multi-Party Computation.
Covert MPC is an extension to MPC that not only hides the inputs, but the entire presence of the computation.
Parties only learn the output if all other parties followed the protocol correctly, and if the output is favorable for all parties.
Otherwise the parties learn nothing, not even which parties tried to participate.
A single non-participant can accidentally abort the entire computation.
The question arises:
Can $N$ parties perform the computation while $K>N$ parties are present, where the output only depends on the inputs of the $N$ participants, while hiding the identity of the other participants among all individuals present?
This should hold in particular if the remaining parties are unaware that a computation is in progress.
We relate this question to the theoretical feasibility of anonymous whistleblowing, where a single party discloses a message without revealing the own identity and without other parties having to act in any special way.
Unfortunately, we show that no primitive can fulfill both correctness and anonymity with overwhelming probability in the asymptotic setting, even under very strong assumptions.
Yet we provide a heuristic instantiation in the fine-grained setting with overwhelming correctness and any given target anonymity.
Our results provide strong foundations for the study of the possibility of anonymous communications through authenticated channels, an intriguing goal which we believe to be of fundamental interest.
Agrikola, Couteau, Maier, TCC 2022
