Graph Pebbling and Cryptography.
Graph pebbling has long been used in computer science, more recently also in cryptography. The cryptography at IST http://pub.ist.ac.at/crypto/ 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. For this reason, they have found applications for password-hashing (where we don’t want an adversary to be able to cheaply “brute-force” passwords) and cryptocurrencies like Litecoin, where it’s assumed that an MHF will lead to more decentralization.
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.
There has been a competition to construct a good MHF https://password-hashing.net/ running until 2015, but as we show in https://eprint.iacr.org/2016/783 all the winners that are “data-independent” (a property required to prevent some kinds of attacks) are not as secure as claimed because the underlying graphs actually can be pebbled much better than anticipated.
We show in https://eprint.iacr.org/2016/875 that to have high pebbling complexity, a graph must be “depth-robust”, and in follow up work proposed the first provably secure MHFs using this connection.
"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” https://eprint.iacr.org/2013/796.pdf 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 https://www.chia.net/ which will use proofs of space to construct a cryptocurrency which is similar to bitcoin, but much more energy efficient and decentralized.