Graphen Pebbling und Kryptographie
Pebbling Spiele haben sich seit langem in der theoretischen Informatik bewährt und auch in der Kryptographie haben sie in letzter Zeit immer mehr Anwendungen gefunden. Die Kryptographie am IST arbeitet an drei unterschiedlichen Themen, welche Graphen Pebbling benutzen.
Memory-hard functions
Sogenannte memory-hard functions (kurz MHF) sind Funktionen, deren Evaluierung viel Speicherplatz benötigt. Im Gegensatz zu Funktionen, deren Evaluierungskosten von Rechenaufwand dominiert werden, sind MHFs egalitär in dem Sinn, dass auch mithilfe von zweckbestimmter Hardware die Evaluierungskosten nicht wesentlich reduziert werden können. Die ursprüngliche Motivation für MHFs kommt aus dem Bereich des Password-hashing, in dem sogenannte Brute-force Angriffe verhindert werden sollen. Vor kurzem fanden MHFs auch Anwendung in der Litecoin Blockchain, wo sie zu besserer Dezentralisierung als in Bitcoin beitragen.
Um eine gute MHF zu konstruieren, genügt es, einen Graphen mit hohen Pebbling-Kosten zu definieren: Die Knoten des Graphen entsprechen den Zwischenwerten der Rechnung und hohe Pebbling Komplexität bedeutet, dass bei der Evaluierung der durch den Graphen definierten Funktion viele Zwischenwerte gespeichert werden müssen - man benötigt also viel Speicherplatz.
Lange Zeit war es nicht klar, wie man Graphen mit hoher Pebbling Komplexität konstruieren sollte. Im Jahre 2016 gelang es uns zu zeigen, dass es genügt, wenn der Graph eine einfache kombinatorische Eigenschaft erfüllt, welche wir als depth-robustness bezeichnen. Diesen Zusammenhang benutzten wir um nachweislich optimale MHFs zu definieren.
Auch im Zusammenhang mit Angriffen auf zuvor vorgeschlagene Konstruktionen war dieser Zusammenhang nützlich: Bis zum Jahr 2015 gab es einen Wettbewerb um eine gute MHF zu konstruieren und wir konnten zeigen, dass alle bestplatzierten Vorschläge welche “Daten-unabhängig” sind (eine Eigenschaft die notwendig ist um gewisse Angriffe zu verhindern) nicht so sicher sind wie behauptet, da sie schlichtweg nicht depth-robust sind.
Proofs of Space und nachhaltige Krypto-Währungen
Bitcoin ist die erste erfolgreiche digitale Währung. Ihre Popularität verdankt sie der Tatsache, dass sie dezentralisiert ist, also von keiner zentralen Autorität kontrolliert wird. Um trotz dieser Eigenschaft Sicherheit zu gewährleisten, werden fortwährend enorme Mengen an Rechenleistung verschwendet um sogenannte Proofs of work zu generieren. Das ist ökonomisch als auch ökologisch problematisch.
Um dieses Problem zu lösen, stellten wir ein neues Beweis-System vor, welches wir Proofs of space nennen und in dem anstelle von Rechenleistung Speicherplatz genutzt wird. Die Konstruktion basiert grundlegend auf Graphen mit hoher Pebbling Komplexität.
Wir sind in chia.net involviert, wo Proofs of space verwendet werden werden um eine Krypto-Währung ähnlich Bitcoin zu entwerfen, die dezentralisiert aber viel Energie-effizienter ist.
Adaptive Sicherheit
In der Kryptographie wird Sicherheit oft in Form eines Spieles zwischen einem Angreifer und einem Herausforderer definiert. Wir unterscheiden zwischen selektiven Sicherheits-Definitionen, wo der Angreifer bereits zu Beginn des Spiels gewisse Entscheidungen treffen muss, und adaptiven Sicherheit-Definitionen, wo der Angreifer all seine Entscheidungen erst im Verlauf des Spiels trifft. Während adaptive Sicherheit in den meisten Anwendungen unerlässlich ist, ist sie leider meist schwer zu beweisen.
Mithilfe von Pebbling konnten einige Systeme, deren Sicherheit lange Zeit nur gegen schwächere, selektive Angreifer garantiert werden konnte, als adaptiv sicher bewiesen werden. Die hierbei verwendeten Techniken haben wir in einem Framework zusammengefasst, welches sich bereits in einigen weiteren Fällen als nützlich erwiesen hat um adaptive Sicherheit zu beweisen.
Graph Pebbling and Cryptography
Graph pebbling has long been used in computer science, more recently also in cryptography. The cryptography at IST works on three topics involving graph pebbling
Memory-hard functions
A memory-hard function (MHF) is a function which requires a lot memory to evaluate. Unlike functions whose evaluation cost is dominated by computation, MHFs are egalitarian in the sense that one can’t evaluate them much cheaper when using dedicated hardware. The original motivation for MHFs comes from password-hashing, where we don’t want an adversary to be able to cheaply “brute-force” passwords. A more recent application is the Litecoin blockchain, where MHFs are used to achieve better decentralization as compared to Bitcoin.
To construct a good MHF it is sufficient to construct a graph with high pebbling complexity: the nodes of the graph then correspond to intermediate values in the computation, and if the graph has high pebbling complexity, one must keep around many values - and thus use much memory - for the computation.
It was not clear how to construct graphs with high pebbling complexity. In 2016 we showed that to have high pebbling complexity, it’s sufficient that the graph satisfies a simple combinatorial property called “depth-robustness”, and we used this connection to construct provably optimal MHFs.
This connection has also be used for attacks: there was a competition to construct a good MHF running until 2015, and we show that all the winners that are “data-independent” (a property required to prevent some kinds of attacks) are not as secure as claimed simply because they are not depth-robust.
Proofs of space and sustainable cryptocurrencies
Bitcoin is the first successful digital currency. Its popularity comes from the fact that it is decentralized, so no central authority controls it. To achieve security despite decentralization, a huge amount of computing power is constantly wasted towards generating “proofs of work”. This is economically and ecologically problematic.
We proposed a new proof system called “proofs of space” which is similar to proofs of work, but where instead of computation one uses disk-space. The construction crucially relies on graphs with high pebbling complexity.
We are involved in chia.net which will use proofs of space to construct a cryptocurrency which is similar to bitcoin, but much more energy efficient and decentralized.
Adaptive security
In cryptography, security is often defined in form of a game between a challenger and an adversary. We distinguish between selective and adaptive security definitions. In the first case, the adversary has to commit to some of its choices ahead of time before the game starts. In the latter, on the other hand, the adversary is free to do all its choices while the game proceeds. Clearly, adaptive security is required for most applications, but, unfortunately, it is often hard to prove.
By means of pebbling, some systems which for a long time were only known to satisfy security against weaker selective adversaries could be proven adaptively secure. Analyzing the techniques used in this context we found a unifying framework which was used also in follow-up work on adaptive security.