Abstract: Reliable Broadcast is a fundamental problem of communication networks. We study this problem in incomplete networks against a Byzantine adversary and with respect to player’s topology knowledge. We examine the problem under the locally bounded adversary model of Koo (2004) and the general adversary model of Hirt and Maurer (1997) and explore the tradeoff between the level of topology knowledge and the solvability of the problem. We refine the local pair-cut technique of Pelc and Peleg (2005) in order to obtain impossibility results for every level of topology knowledge and any type of corruption dis- tribution. On the positive side we devise protocols that match the obtained bounds and thus, exactly characterize the classes of graphs in which Reliable Broadcast is possible. Among others, we show that Koo’s Certified Propagation Algorithm (CPA) is unique against locally bounded adversaries in ad hoc networks, that is, it can tolerate as many local corruptions as any other non-faulty algorithm; this settles an open question posed by Pelc and Peleg. We also provide an adaptation of CPA against general adversaries and show its uniqueness. To the best of our knowledge this is the first optimal algorithm for Reliable Broadcast in generic topology ad hoc networks against general adversaries.

Abstract: Due to the widespread deployment of ubiquitous devices, end users are burgeoning service providers with massive amount of data. This proliferation of information has enabled new paradigms in data collection and processing. However this new paradigm acts as a double-edged sword: on the one hand the collection of information empowers service providers to compute useful aggregate statistics, but on the other hand serious privacy and security concerns are undermined. In this presentation we will focus on privacy and security issues in computations performed by untrusted aggregators on highly sensitive data whereby the untrusted aggregators learn the result of the computation. We will first review current state of the art work for privacy preserving computations in the multi-user setting and we will describe a novel solution that tackles for dynamic populations with a more powerful threat model. Moreover we will extend the aforementioned scenario in order to address security issues with respect to the verifiability of computations by first showing why existing solutions in verifiable computations do not fit in our scenario and then by presenting our technique.

In this talk we describe a formal security model for bitcoin and other related “cryptocurrencies" that utilize a blockchain data structure. We describe two properties, called common prefix and chain quality and we provide a cryptographic analysis of the core of the bitcoin protocol (that we term the bitcoin backbone) with respect to those properties. We then provide various directions and applications that enable the realization of functionalities in a highly decentralized - anarchic - fashion. Importantly we argue how coordination and consensus can be reached in a scalable fashion without the help of a higher authority.

Event-Release Encryption (ERE) is dealing with the problem of sending a message so that recipients can only decrypt it if a specific event occurs. In the same sense, Timed-Release Encryption (TRE) studies the problem of “sending information into the future”, i.e., encrypting a message so that it cannot be decrypted by anyone, including the designated recipients, until a time instant in the future. The aforementioned problems are considered closely related; TRE is in fact a special case of ERE, where a specific time instant has the role of an occurred event. The literature offers a variety of mechanisms that provide such functionality. Some of them rely on performing immense non-parallelizable computations, called Time-Lock Puzzles. However, for practical reasons, the majority of proposals make use of third parties synchronizing users and decryption keys. In this talk a set of practical ERE and TRE solutions will be presented. More specifically, we will focus on a practical threshold ERE system based on bilinear pairings over elliptic curve groups and we will also describe a set of real-life applications related to ERE or TRE, such as secure e-lottery, e-contests and blind auctions.

Joint work with Stavros Papadopoulos from Intel & MIT and Nikos Triandopoulos from RSA Laboratories & Boston University.
Abstract: Outsourcing of data and computation has emerged as common practice for enterprises and individuals, in particular in the context of cloud computing. One security concern that arises in this context is that of integrity-of-computation; how can parties querying the outsourced data be certain for the correctness of the results they receive, even in the presence of a malicious distributing server. In this talk I will go over cryptographic tools that provide secure constructions in a particular model of delegation, that can accommodate various classes of functions. As an example, I will present in detail our recent result for the case of multi-dimensional range queries that appeared in ACM CCS'14.

Abstract: We introduce a new class of protocols where a prover wants to convince a verifier that either she has performed work or that she possesses knowledge of a witness to a public statement. We call this primitive an argument of work or knowledge (AWorK). In an AWorK, the prover and the verifier agree on a public relation and a class of cryptographic puzzles. At the end of the protocol, the verifier that accepts, will be convinced that the prover either knows the witness or she has invested sufficient computational effort required for solving a puzzle without being able to distinguish which of the two has taken place. We formalize AWorK protocols in terms of their three basic properties, completeness, f -soundness and indistinguishability (where f is a function that determines the tightness of the proof of work as- pect) and we provide a three move protocol that instantiates our definition. Our AWorK protocol employs cryptographic puzzles that adhere to certain uniformity conditions that may be of indepen- dent interest. We instantiate our puzzles in the random oracle (RO) model as well as in the standard model via discrete-logarithm problems over generic groups. We then present applications of AWorK protocols: (i) we first show that any AWorK proto- col implies concurrent quasi-polynomial simulatable arguments of knowledge; by applying this re- sult to our construction we obtain an efficient straight-line concurrent three-move O(λpoly(log λ))- simulatable argument of knowledge, improving the round complexity of the previously known four- move protocol of Pass from Eurocrypt 2003, (ii) we present an anonymous credential system where users may choose to prove their identity or alternatively perform work in order to receive service. The system provides a novel way of tiering users in anonymous credential systems in two classes, those that prefer to be perfectly anonymous (but have to perform work) and those that have regular subscriptions (and hence possess credentials that enable them to avoid work).

Joint work with Sanjam Garg.
Abstract: Adaptively secure Multi-Party Computation (MPC) first studied by Canetti, Feige, Goldreich, and Naor in 1996, is a fundamental notion in cryptography. Adaptive security is particularly hard to achieve in settings where arbitrary number of parties can be corrupted and honest parties are not trusted to properly erase their internal state. We did not know how to realize constant round protocols for this task even if we were to restrict ourselves to semi-honest adversaries and to the simpler two-party setting. Specifically the round complexity of known protocols grows with the depth of the circuit the parties are trying to compute. In this work, using indistinguishability obfuscation, we construct a UC two-round Multi-Party computation protocol secure against any adaptive, active adversary corrupting an arbitrary number of parties.