Cryptography and information theory

Elham Kashefi and Luka Music – Garbled Quantum Computation

We present a protocol for secure two party quantum computation, that we refer to as QYao. This protocol involves two parties with asymmetric roles, that wish to securely compute any given unitary on a joint quantum input. Our protocol is interactive, but only classical online communication is required between the garbler and the evaluator. This feature will allow us to construct a simple universal one-time compiler for any quantum computation using one-time memory. Apart from the initial input exchange where classical OT is needed, the rest of the protocol is unconditionally secure. If one could replace the classical OT’s in our QYao protocol with new primitives, such as the unconditionally secure relativistic primitives, the security would be extended to fully unconditional.

This is a joint work with Petros Wallden.

Aggelos Kiayias – Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol

We present “Ouroboros,” the first blockchain protocol based on proof of stake with rigorous security guarantees. We establish security properties for the protocol comparable to those achieved by the bitcoin blockchain protocol. As the protocol provides a “proof of stake” blockchain discipline, it offers qualitative efficiency advantages over blockchains based on proof of physical resources (e.g., proof of work). We showcase the practicality of our protocol in real world settings by providing experimental results on transaction processing time obtained with a prototype implementation in the Amazon cloud. We also present a novel reward mechanism for incentivizing the protocol and we prove that given this mechanism, honest behavior is an approximate Nash equilibrium, thus neutralizing attacks such as selfish mining and block withholding. We also report on how it is possible to adapt the protocol to protect against adaptive and semi-synchronous adversaries. Based on joint works with Alexander Russell, Bernardo David, Roman Oliynykov, Peter Gazi, Chris Moore, Saad Quader.

Ivan Visconti – Delayed-Input Cryptographic Protocols

The delayed-input witness-indistinguishable proof of knowledge of Lapidot and Shamir (LS) [CRYPTO 1989] is a powerful tool for designing round-efficient cryptographic protocols. Since LS was designed for the language of Hamiltonian graphs, when used as subprotocol it usually requires expensive NP reductions. We first overview how LS works and how can it can be used for round efficiency as shown by Ostrovsky and Visconti [ECCC 2012]. We point out the intrinsic efficiency limits of LS due to the tight connection with the language of Hamiltonian graphs. Then we will overview some recent advances on efficient delayed-input cryptographic protocols and their applications. We will in particular consider the efficient witness-indistinguishable proofs of knowledge of Ciampi, Persiano, Scafuro, Siniscalchi and Visconti [TCC 2016a, Eurocrypt 2016].