Project Results
Below are highlights from CODAMODA publications
Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol
Aggelos Kiayias and Alexander Russell and Bernardo David and Roman Oliynykov [paper] Crypto 2017.
Abstract: 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.
The Bitcoin Backbone Protocol with Chains of Variable Difficulty
Juan A. Garay and Aggelos Kiayias and Nikos Leonardos [paper] Crypto 2017.
Abstract: Bitcoin’s innovative and distributedly maintained blockchain data structure hinges on the adequate degree of difficulty of so-called “proofs of work,” which miners have to produce in order for transactions to be inserted. Importantly, these proofs of work have to be hard enough so that miners have an opportunity to unify their views in the presence of an adversary who interferes but has bounded computational power, but easy enough to be solvable regularly and enable the miners to make progress. As such, as the miners’ population evolves over time, so should the difficulty of these proofs. Bitcoin provides this adjustment mechanism, with empirical evidence of a constant block generation rate against such population changes. In this paper we provide the first (to our knowledge) formal analysis of Bitcoin’s target (re)calculation function in the cryptographic setting, i.e., against all possible adversaries aiming to subvert the protocol’s properties. We extend the q-bounded synchronous model of the Bitcoin backbone protocol [Eurocrypt 2015], which posed the basic properties of Bitcoin’s underlying blockchain data structure and shows how a robust public transaction ledger can be built on top of them, to environments that may introduce or suspend parties in each round. We provide a set of necessary conditions with respect to the way the population evolves under which the “Bitcoin backbone with chains of variable difficulty” provides a robust transaction ledger in the presence of an actively malicious adversary controlling a fraction of the miners strictly below 50% in each instant of the execution. Our work introduces new analysis techniques and tools to the area of blockchain systems that may prove useful in analyzing other blockchain protocols.
Fair and Robust Multi-Party Computation using a Global Transaction Ledger
Aggelos Kiayias and Hong-Sheng Zhou and Vassilis Zikas. [paper] Eurocrypt 2016.
Abstract: Classical results on secure multi-party computation (MPC) imply that fully secure computation, including fairness (either all parties get output or none) and robustness (output delivery is guaranteed), is impossible unless a majority of the parties is honest. Recently, cryptocurrencies like Bitcoin where utilized to leverage the fairness loss in MPC against a dishonest majority. The idea is that when the protocol aborts in an unfair manner (i.e., after the adversary receives output) then honest parties get compensated by the adversarially controlled parties.
Our contribution is three-fold. First, we put forth a new formal model of secure MPC with compensation and we show how the introduction of suitable ledger and synchronization functionalities makes it possible to express completely such protocols using standard interactive Turing machines (ITM) circumventing the need for the use of extra features that are outside the standard model as in previous works. Second, our model, is expressed in the universal composition setting with global setup and is equipped with a composition theorem that enables the design of protocols that compose safely with each other and within larger environments where other protocols with compensation take place; a composition theorem for MPC protocols with compensation was not known before. Third, we introduce the first robust MPC protocol with compensation, i.e., an MPC protocol where not only fairness is guaranteed (via compensation) but additionally the protocol is guaranteed to deliver output to the parties that get engaged and therefore the adversary, after an initial round of deposits, is not even able to mount a denial of service attack without having to suffer a monetary penalty. Importantly, our robust MPC protocol requires only a {\em constant } number of (coin-transfer and communication) rounds.
Indistinguishable Proofs of Work or Knowledge
Foteini Baldimtsi and Aggelos Kiayias and Thomas Zacharias and Bingsheng Zhang [paper] Asiacrypt 2016.
Abstract: We introduce a new class of protocols called Proofs of Work or Knowledge (PoWorKs). In a PoWorK, a prover can convince a verifier that she has either performed work or that she possesses knowledge of a witness to a public statement without the verifier being able to distinguish which of the two has taken place.
We formalize PoWorK in terms of three properties, completeness, f-soundness and indistinguishability (where f is a function that determines the tightness of the proof of work aspect) and present a construction that transforms 3-move HVZK protocols into 3-move public-coin PoWorKs. To formalize the work aspect in a PoWorK~protocol we define cryptographic puzzles that adhere to certain uniformity conditions, which may also be of independent interest. We instantiate our puzzles in the random oracle (RO) model as well as via constructing ``dense'' versions of suitably hard one-way functions.
We then showcase PoWorK~protocols by presenting a number of applications. We first show how non-interactive PoWorKs can be used to reduce spam email by forcing users sending an e-mail to either prove to the mail server they are approved contacts of the recipient or to perform computational work. As opposed to previous approaches that applied proofs of work to this problem, our proposal of using PoWorKs is privacy-preserving as it hides the list of the receiver's approved contacts from the mail server. Our second application, shows how PoWorKs can be used to compose cryptocurrencies that are based on proofs of work (``Bitcoin-like'') with cryptocurrencies that are based on knowledge relations (these include cryptocurrencies that are based on ``proof of stake'', and others). The resulting PoWorK-based cryptocurrency inherits the robustness properties of the underlying two systems while PoWorK-indistinguishability ensures a uniform population of miners. Finally, we show that PoWorK~protocols imply straight-line quasi-polynomial simulatable arguments of knowledge and based on our construction we obtain an efficient straight-line concurrent 3-move statistically quasi-polynomial simulatable argument of knowledge.
The rupture framework (Black-Hat Asia 2016, Black-Hat Europe 2016)
read about our attacks
The Bitcoin Backbone Protocol: Analysis and Applications
by Juan Garay and Aggelos Kiayias and Nikos Leonardos, [paper] Eurocrypt 2015.
Abstract. Bitcoin is the first and most popular decentralized cryptocurrency to date. In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin {\em backbone}, and prove two of its fundamental properties which we call {\em common prefix} and {\em chain quality}. Our proofs hinge on appropriate and novel assumptions on the ``hashing power'' of the adversary relative to network synchronicity; our results are shown to be tight under high synchronization. Next, we propose and analyze applications that can be built ``on top'' of the backbone protocol, specifically focusing on Byzantine agreement (BA) and on the notion of a public transaction ledger. Regarding BA, we observe that Nakamoto's suggestion falls short of solving it, and present a simple alternative which works assuming that the adversary's hashing power is bounded by $1/3$. The public transaction ledger captures the essence of Bitcoin's operation as a cryptocurrency, in the sense that it guarantees the ``liveness'' and ``persistence'' of committed transactions. Based on this notion we describe and analyze the Bitcoin system as well as a more elaborate BA protocol, proving them secure assuming high network synchronicity and that the adversary's hashing power is strictly less than $1/2$, while the adversarial bound needed for security decreases as the network desynchronizes.
Communication Optimal Tardos-based Asymmetric Fingerprinting.
by Aggelos Kiayias, Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk and Qiang Tang, CT-RSA 2015.
Abstract. Asymmetric fingerprinting schemes were first introduced by Pfitzmann and Schunter in Eurocrypt 1996, and these schemes enable the transmission of a file stored in a server to a set of users so that each user obtains a variation of the file. The security considerations of these schemes are as follows: if any (appropriately bounded) subset of users collude to produce a “pirate” copy of the file it is always possible for the server to prove to a third party judge their implication, while a malicious server can never implicate innocent users. Given that asymmetric fingerprinting is supposed to dis- tribute files of substantial size (e.g., media files including video and audio) any communication rate (defined as the size of the file over the total number of transmission) less than 1 would render them practically useless. The existence of such schemes is currently open. Building on a rate close to 1 obliv- ious transfer (constructed from recently proposed rate optimal homomorphic encryption), we present the first asymmetric fingerprinting scheme that is communication optimal, i.e., its communication rate is arbitrarily close to 1 (for sufficiently large files) thus resolving this open question. Our scheme is based on Tardos code, and we prove our scheme secure in an extended formal security model where we also deal with the important but previously unnoticed (in the context of asymmetric fingerprinting) security considerations of accusation withdrawal and adversarial aborts.
Round-Optimal Password-Protected Secret Sharing and T-PAKE in the Password-Only Model
by Stanislaw Jarecki and Aggelos Kiayias and Hugo Krawczyk, [paper] Asiacrypt 2014.
Abstract. In a Password-Protected Secret Sharing (PPSS) scheme with parameters (t,n) (formalized by Bagherzandi et al), a user Alice stores secret information s among n servers so that she can later recover the information solely on the basis of her password. The security requirement is similar to a (t,n)-threshold secret sharing, i.e., Alice can recover her secret as long as she can communicate with t + 1 honest servers but an attacker gaining access to t servers cannot learn information about the secret. In particular, the system is secure against online attacks by an attacker controlling up to t servers. On the other hand, accounting for inevitable on-line attacks one allows the attacker an advantage proportional to the fraction of dictionary passwords tested in on-line interactions with the user and servers. We present the first round-optimal PPSS scheme, requiring just one message from user to server, and from server to user, and that works in the password-only setting where users do not have access to an authenticated public key. The scheme uses an Oblivious PRF whose security we define using a UC-style ideal functionality and denote as V-OPRF due to its verifi ability, and for which we show concrete, very practical realizations in the random oracle model, as well as standard-model instantiations. As an important application we use this scheme to build the first single-round password-only Threshold-PAKE protocol in the CRS and ROM models for arbitrary (t,n) parameters with no PKI requirements for any party (clients or servers) and no inter-server communication. Our T-PAKE protocols are built by combining suitable key exchange protocols on top of our V-OPRF-based PPSS schemes. We prove T-PAKE security via a generic composition theorem showing the security of any such composed protocol.
Distributing the setup in universally composable multi-party computation
by Jonathan Katz, Aggelos Kiayias, Hong-Sheng Zhou and Vassilis Zikas, [paper] PODC 2014.
Abstract. Universally composable (UC) protocols retain their security properties even when run concurrently alongside arbitrary other protocols. Unfortunately, it is known that UC multiparty computation (for general functionalities, and without assuming honest majority) is impossible without some form of setup. To circumvent this impossibility, various complete setup assumptions have been proposed. With only a few exceptions, past work has viewed these setup assumptions as being implemented by some ideal, incorruptible entity. Any such entity is thus a single point of failure, and security fails catastrophically in case the setup entity is subverted by an adversary. We propose here a clean, general, and generic approach for distributing trust among m arbitrary setups, by modeling potential corruption of setups within the UC framework, where such corruption might be fail-stop, passive, or arbitrary and is in addition to possible corruption of the parties themselves. We show several feasibility and impossibility results in this model, for different specifications of the corruptible sets. For example, we show that given m complete setups, up to t of which might be actively corrupted in an adaptive manner, general multiparty computation with no honest majority is possible if and only if t < m/2.
Tamper Resilient Circuits: The Adversary at the Gates
by Aggelos Kiayias and Yiannis Tselekounis, [paper] Asiacrypt 2013.
Abstract. We initiate the investigation of {\em gate}-tampering attacks against cryptographic circuits. Our model is motivated by the plausibility of tampering directly with circuit gates and by the increasing use of {\em tamper resilient gates} among the known constructions that are shown to be resilient against {\em wire-tampering} adversaries. We prove that gate-tampering is {\em strictly} stronger than wire-tampering. On the one hand, we show that there is a gate-tampering strategy that perfectly simulates any given wire-tampering strategy. On the other, we construct families of circuits over which it is impossible for any wire-tampering attacker to simulate a certain gate-tampering attack (that we explicitly construct). We also provide a tamper resilience impossibility result that applies to both gate and wire tampering adversaries and relates the amount of tampering to the depth of the circuit. Finally, we show that defending against gate-tampering attacks is feasible by appropriately abstracting and analyzing the circuit compiler of Ishai et al. \cite{Ishai:2006a} in a manner which may be of independent interest. Specifically, we first introduce a class of compilers that, assuming certain well defined tamper resilience characteristics against a specific class of attackers, can be shown to produce tamper resilient circuits against that same class of attackers. Then, we describe a compiler in this class for which we prove that it possesses the necessary tamper-resilience characteristics against gate-tampering attackers.
How to Keep a Secret: Leakage Deterring Public-key Cryptosystems
by Aggelos Kiayias and Qiang Tang, [paper] ACM-CCS 2013.
Abstract. How is it possible to prevent the sharing of cryptographic functions? This question appears to be fundamentally hard to address since in this setting the owner of the key is the adversary: she wishes to share a program or device that (po- tentially only partly) implements her main cryptographic functionality. Given that she possesses the cryptographic key, it is impossible for her to be prevented from writing code or building a device that uses that key. She may though be deterred from doing so. We introduce leakage- deterring public-key cryptosystems to address this problem. Such primitives have the feature of enabling the embedding of owner-specific private data into the owner’s public-key so that given access to any (even partially functional) imple- mentation of the primitive, the recovery of the data can be facilitated. We formalize the notion of leakage-deterring in the context of encryption, signature, and identification and we provide efficient generic constructions that facilitate the recoverability of the hidden data while retaining privacy as long as no sharing takes place.
Delegatable Pseudorandom Functions and Applications
by Aggelos Kiayias and Stavros Papadopoulos and Nikos Triandopoulos and Thomas Zacharias, [paper], ACM-CCS 2013.
Abstract. We put forth the problem of delegating the evaluation of a pseudorandom function (PRF) to an untrusted proxy. A {\em delegatable PRF}, or DPRF for short, is a new primitive that enables a proxy to evaluate a PRF on a strict subset of its domain using a trapdoor derived from the DPRF secret-key. PRF delegation is \emph{policy-based}: the trapdoor is constructed with respect to a certain policy that determines the subset of input values which the proxy is allowed to compute. Interesting DPRFs should achieve \emph{low-bandwidth delegation}: Enabling the proxy to compute the PRF values that conform to the policy should be more efficient than simply providing the proxy with the sequence of all such values precomputed. The main challenge in constructing DPRFs is in maintaining the pseudorandomness of unknown values in the face of an attacker that adaptively controls proxy servers. A DPRF may be optionally equipped with an additional property we call \emph{policy privacy}, where any two delegation predicates remain indistinguishable in the view of a DPRF-querying proxy: Achieving this raises new design challenges as policy privacy and efficiency are seemingly conflicting goals.
For the important class of policies described as (1-dimensional) \emph{ranges}, we devise two DPRF constructions and rigorously prove their security. Built upon the well-known tree-based GGM PRF family~\cite{GGM86}, our constructions are generic and feature only logarithmic delegation size in the number of values conforming to the policy predicate. At only a constant-factor efficiency reduction, we show that our second construction is also policy private. As we finally describe, their new security and efficiency properties render our delegated PRF schemes particularly useful in numerous security applications, including RFID, symmetric searchable encryption, and broadcast encryption.
Resource Access Control in the Facebook Model
by Konstantinos Chronopoulos, Maria Gouseti and Aggelos Kiayias, [paper], CANS 2013.
Abstract. We study the fundamental security properties of {\em resource access control} as suggested by the operation of current social networks including Facebook. The ``facebook model'', which treats the server as a trusted party, suggests two fundamental properties, ``owner privacy'' and ``server consistency'', and two different modes of revocation, implicit and explicit. Through black-box experimentation, we determine Facebook's implementation for resource access control and we analyze its security properties within our formal model. We demonstrate, by the construction of explicit attacks, that the current implementation is not secure: specifically, we attack privacy with implicit revocation and server consistency. We evaluate the implications of the attacks and we propose amendments that can align the current implementation with all its intended security properties. To the best of our knowledge this is the first time that a security analysis of the Facebook resource access control mechanism is performed within a proper security model.
Resource-based Corruptions and the Combinatorics of Hidden Diversity
by Juan Garay - David Johnson - Aggelos Kiayias - Moti Yung, [paper], Innovations in Theoretical Computer Science - ITCS 2013.
Abstract. In the setting of cryptographic protocols, the corruption of a party has traditionally been viewed as a simple, uniform and atomic operation, where the adversary decides to get control over a party and this party immediately gets corrupted. In this paper, motivated by the fact that different players may require different resources to get corrupted, we put forth the notion of resource-based corruptions, where the adversary must invest some resources in order to corrupt a player. If the adversary has full information about the system con- figuration then resource-based corruptions would provide no fundamental difference from the standard corruption model. However, in a resource “anonymous” setting, in the sense that such configuration is hidden from the adversary, much is to be gained in terms of efficiency and security. We showcase the power of such hidden diversity in the con- text of secure multiparty computation (MPC) with resource- based corruptions and prove that anonymity it can effec- tively be used to circumvent known impossibility results. Specifically, if OPT is the corruption budget that violates the completeness of MPC (the case when half or more of the players are corrupted), we show that if hidden diversity is available, the completeness of MPC can be made to hold against an adversary with as much as a B · OP T budget, for any constant B > 1. This result requires a suitable choice of parameters (in terms of number of players and their hardness to corrupt), which we provide and further prove other tight variants of the result when the said choice is not available. Regarding efficiency gains, we show that hidden diversity can be used to force the corruption threshold to drop from 1/2 to 1/3, in turn allowing the use of much more efficient (information-theoretic) MPC protocols.
Randomness attacks against PHP applications.
by George Argyros - Aggelos Kiayias, [paper], USENIX Security 2012. [more information]
Abstract. We provide a number of practical techniques and algorithms for exploiting randomness vulnerabilities in PHP applications.We focus on the predictability of password reset tokens and demonstrate how an attacker can take over user accounts in a web application via pre- dicting or algorithmically derandomizing the PHP core randomness generators. While our techniques are designed for the PHP language, the principles behind our techniques and our algorithms are independent of PHP and can readily apply to any system that utilizes weak randomness generators or low entropy sources. Our results include: algorithms that reduce the entropy of time variables, identifying and exploiting vulnerabilities of the PHP system that enable the recovery or reconstruction of PRNG seeds, an experimental analysis of the H ̊astad-Shamir framework for breaking truncated linear variables, an optimized online Gaussian solver for large sparse linear systems, and an algorithm for recovering the state of the Mersenne twister generator from any level of truncation. We demonstrate the gravity of our attacks via a number of case studies. Specifically, we show that a number of cur- rent widely used web applications can be broken using our techniques including Mediawiki, Joomla, Gallery, osCommerce and others.
Lower Bounds for Private Broadcast Encryption
by Aggelos Kiayias - Katerina Samari, [paper], Information Hiding 2012.
Abstract. Broadcast encryption is a type of encryption where the sender can choose a subset from a set of designated receivers on the fly and en- able them to decrypt a ciphertext while simultaneously preventing any other party from doing so. The notion of private broadcast encryption extends the primitive to a setting where one wishes to thwart an attacker that additionally attempts to extract information about what is the set of enabled users (rather than the contents of the ciphertext) In this work we provide the first lower bounds for the ciphertext size of private broadcast encryption. We first formulate various notions of pri- vacy for broadcast encryption, (priv-eq, priv-st and priv-full) and classify them in terms of strength. We then show that any private broadcast encryption scheme in the sense of priv-eq (our weakest notion) that sat- isfies a simple structural condition we formalize and refer to as “atomic” is restricted to have ciphertexts of size Ω(s · k) where s is the cardinality of the set of the enabled users and k is the security parameter. We then present an atomic private broadcast encryption scheme with ciphertext size Θ(s · k) hence matching our lower bound that relies on key privacy of the underlying encryption. Our results translate to the setting priv-full privacy for a ciphertext size of Θ(n · k) where n is the total number of users while relying only on KEM security. We finally consider arbitrary private broadcast encryption schemes and we show that in the priv-full privacy setting a lower-bound of Ω(n+k) for every ciphertext is imposed. This highlights the costs of privacy in the setting of broadcast encryp- tion where much shorter ciphertexts have been previously attained with various constructions in the non-privacy setting.
Key Efficient Steganography
by Aggelos Kiayias, Alexander Russell, Narasimha Sashidar, [paper], Information Hiding 2012.
Abstract. Steganographic protocols enable one to embed covert messages into inconspicuous data over a public communication channel in such a way that no one, aside from the sender and the intended receiver, can even detect the presence of the secret message. In this paper, we provide a new provably-secure, private-key steganographic encryption protocol secure in the framework of Hopper et al.. We first present a ``one-time stegosystem'' that allows two parties to transmit messages of length at most that of the shared key with information-theoretic security guarantees; employing a pseudorandom generator (PRG) then permits secure transmission of longer messages in a striaghtforward manner. The advantage of our construction in comparison with previous work is key-length efficiency: in the information-theoretic setting our protocol embeds a $n$ bit message using a shared secret key of length $(1+o(1))n$ while achieving security $2^{-n/\log^{O(1)}n}$: this gives a rate of key length over message length that converges to 1 as $n\rightarrow\infty$; the previous best result achieved a constant rate $>1$ regardless of the security offered. In this sense, our protocol is the first truly key-length efficient steganographic system. Furthermore, in our protocol, we can permit a portion of the shared secret key to be public while retaining precisely $n$ private key bits. In this setting, by separating the public and the private randomness of the shared key, we achieve security of $2^{-n}$. Our result comes as an effect of a novel application of randomness extractors to stegosystem design.