Abstract: We present DAG-Rider, the first asynchronous Byzantine Atomic Broadcast protocol that achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity. DAG-Rider is post-quantum safe and ensures that all messages proposed by correct processes eventually get decided. We construct DAG-Rider in two layers: In the first layer, processes reliably broadcast their proposals and build a structured Directed Acyclic Graph (DAG) of the communication among them. In the second layer, processes locally observe their DAGs and totally order all proposals with no extra communication. Afterwards we propose Narwhal and Tusk. Where we separate the task of reliable transaction dissemination from transaction ordering of DAG-Rider, to enable high-performance Byzantine fault-tolerant quorum-based consensus. We design and evaluate a mempool protocol, Narwhal, specializing in high-throughput reliable dissemination and storage of causal histories of transactions. Narwhal tolerates an asynchronous network and maintains high performance despite failures. Narwhal is designed to easily scale-out using multiple workers at each validator, and we demonstrate that there is no foreseeable limit to the throughput we can achieve.

Abstract: Payment channels effectively move the transaction load off-chain thereby successfully addressing the inherent scalability problem most cryptocurrencies face. A major drawback of payment channels is the need to ``top up'' funds on-chain when a channel is depleted. Rebalancing was proposed to alleviate this issue, where parties with depleting channels move their funds along a cycle to replenish their channels off-chain. Protocols for rebalancing so far either introduce local solutions or compromise privacy. In this work, we present an opt-in rebalancing protocol that is both private and globally optimal, meaning our protocol maximizes the total amount of rebalanced funds. We study rebalancing from the framework of linear programming. To obtain full privacy guarantees, we leverage multi-party computation in solving the linear program, which is executed by selected participants to maintain efficiency. Finally, we efficiently decompose the rebalancing solution into incentive-compatible cycles which conserve user balances when executed atomically.

Abstract: We study the notion of indistinguishability obfuscation for null quantum circuits (quantum null-iO). We present a construction assuming: - The quantum hardness of learning with errors (LWE). - Post-quantum indistinguishability obfuscation for classical circuits. - A notion of ''dual-mode'' classical verification of quantum computation (CVQC). We give evidence that our notion of dual-mode CVQC exists by proposing a scheme that is secure assuming LWE in the quantum random oracle model (QROM). Then we show how quantum null-iO enables a series of new cryptographic primitives that, prior to our work, were unknown to exist even making heuristic assumptions. Among others, we obtain the first witness encryption scheme for QMA, the first publicly verifiable non-interactive zero-knowledge (NIZK) scheme for QMA, and the first attribute-based encryption (ABE) scheme for BQP.

Abstract: I will present reward sharing schemes (RSS) for stake pools, a reward mechanism that we introduced in https://ieeexplore.ieee.org/document/9230398 and is used in the Cardano blockchain platform. Reward sharing schemes promote the fair formation of stake pools in collaborative projects that involve a large number of stakeholders, such as the maintenance of a proof-of-stake (PoS) blockchain. They are parameterized by a target value k for the desired number of pools, and they make the underlying system stabilize at a Nash equilibrium, where the users are organised in k pools of equal size. Our equilibria exhibit also an efficiency / security tradeoff via a parameter that calibrates between including pools with the smallest cost and providing protection against Sybil attacks, the setting where a single stakeholder creates a large number of pools in the hopes to dominate the collaborative project. Finally, we experimentally demonstrate fast convergence to equilibria in dynamic environments where players react to each other's strategic moves over an indefinite period of interactive play. We also show how simple reward sharing schemes that are seemingly more “fair” converge to centralized equilibria with just one pool.

Abstract: In this talk I will examine how to protect the identity of communicating parties in quantum networks. Starting from the two party case, I will show what are the necessary components in order to perform anonymous key distribution. I will then extend this to the multiparty case, and examine what notions of anonymity we can achieve when multiple parties want to establish a common secret key, also known as conference key agreement. I will finally present the outcomes of the first experimental demonstration of anonymous conference key agreement between three parties, using an optical setup.

Abstract: Applying cryptographic operations in a distributed and collaborative fashion has been for more than four decades a dominant paradigm in the design of privacy-preserving communications systems and specifically mix-nets. The design of such systems present to the end user a guarantee that typically involves a threshold condition. For instance, such condition could have the form “as long as x out of a certain set of y cryptographic keys remain uncompromised then privacy is maintained.” Enforcing the condition is typically out of scope for the system design and the end-user has no tools whatsoever to assess whether the condition holds. As a result, it is typically taken at face value. This is unfortunate as it may lead to deployments where privacy fails – and to make matters worse, no-one may even be aware of it. In this talk, I will present ongoing work (in collaboration with Claudia Diaz and Harry Halpin) that is pursued in the context of Nym (https://nymtech.net/), an incentivised mix-network system. The design is based on new techniques in the context of mix-nets as well as it suitably adapts concepts first developed in the context of blockchain protocols, and offers an incentive-driven privacy preserving communication infrastructure that aims to provide privacy via a novel “cryptoeconomic” mechanism.

Abstract: The vast majority of the literature on fault-tolerant distributed computing and multi-party computation (in short, MPC) considers threshold adversaries - up to a certain number of faults are assumed - corrupting parties actively (byzantine faults) and/or fail-stop (crash failures). Arguably, the above fault types are inadequate for capturing correct parties/processes that might suffer temporary network failures and/or localized faults-these are particularly relevant for (secure) distributed computation over large, global scale networks. Omission faults and general adversary structures have been proposed as more suitable alternatives. However, to date, there is no characterization of the fault-tolerance landscape combining the above ramifications of fault types and patterns.In this work we provide a tight characterization of feasibility of synchronous Byzantine agreement tolerating general adversary structures with (adversaries that combine) omission and byzantine faults. We also initiate the investigation of information-theoretic MPC against such adversaries: First, we show the common techniques used in the threshold MPC literature do not work in this setting, not even for proving bounds that would appear trivial, such as sufficiency of the well known $Q^3$ condition on omission-only general adversaries. We then prove the first feasibility and necessity result for MPC tolerating such an adversary, under a mild atomicity assumption on the omission faults.

Abstract: Prominent blockchain systems such as Bitcoin and Ethereum have experienced explosive growth in transaction volume, leading to frequent surges in demand for limited block space, causing transaction fees to fluctuate by orders of magnitude. Many approaches have been proposed, each with different goals such as to keep the prices down or make the choice easier for the user. However, so far none have been particularly effective in practice; often, even the target objective is unclear. In this talk we will go over the current literature (including the most prominent mechanisms used), formulate a more sophisticated model for transaction fees and discuss alternative solutions.

Abstract: In this talk we are going to present our multi-party Prime Match solution for matching orders in a stock exchange while maintaining the privacy of the orders. Information is revealed only if there is a match. To achieve our solution, we present a new protocol for secure comparison with malicious security which can be of independent interest. Prime Match has been running in production since September 2021.

Abstract: Geo-redundancy protects customer data and provides high availability in cloud storage systems. This paper presents the design, implementation and evaluation of Gus, a strongly consistent object storage system that supports high performance atomic read, write, and remove operations, while preserving low tail latency. Gus achieves that through the following three properties. (i) Leaderless design: operations can be ordered in a decentralized way, without relying on a single leader. (ii) Optimal commit latency: all three operations can be completed in 1 RTT, by contacting a simple majority, in the common case (when there is no conflicting write). (iii) Instant execution:whenever the operation is committed, the operation can be executed. It was demonstrated that leaderless systems often suffer from long tail latency owing to delayed execution of some operations. To the best of our knowledge, Gus is the first protocol to achieve all three properties. Our evaluation shows that Gus provides lower tail latency and higher throughput than EPaxos, Gryff, and Giza, under various workloads. In addition, I will sketch some high-level ideas of making Gus Byzantine-tolerant and how Gus could be applied to Blockchain applications.

Abstract: We study the fundamental task of estimating the median of an underlying distribution from a finite number of samples, under pure differential privacy constraints. We focus on distributions satisfying the minimal assumption that they have a positive density at a small neighborhood around the median. In particular, the distribution is allowed to output unbounded values and is not required to have finite moments. We compute the exact, up-to-constant terms, statistical rate of estimation for the median by providing nearly-tight upper and lower bounds. Furthermore, we design a polynomial-time differentially private algorithm which provably achieves the optimal performance. At a technical level, our results leverage a Lipschitz Extension Lemma which allows us to design and analyze differentially private algorithms solely on appropriately defined "typical" instances of the samples.

Joint work with Christos Tzamos and Ilias Zadik.

Abstract: Game-theoretic analyses of cryptocurrencies and---more generally---blockchain-based decentralized ledgers offer insight on their economic robustness and behavior when even their underpinning cryptographic assumptions fail. In this work we utilize the recently proposed blockchain adaptation of the rational protocol design (RPD) framework [EUROCRYPT'18] to analyze 51% double-spending attacks against Nakamoto-style proof-of-work based cryptocurrencies. We first observe a property of the originally proposed utility class that yields an unnatural conclusion against such attacks, and show how to devise a utility that avoids this pitfall and makes predictions that match the observable behavior---i.e., that renders attacking a dominant strategy in settings where an attack was indeed observed in reality. We then propose a generic remedy to the underlying protocol parameters that provably deter adversaries controlling a majority of the system's resources from attacks on blockchain con! sistency, including the 51% double-spending attack. This can be used as guidance to patch systems that have suffered such attacks, e.g., Ethereum Classic and Bitcoin Cash, and serves as a demonstration of the power of game-theoretic analyses.

This is joint work wit Christian Badertscher and Yun Lu.

Abstract: In this presentation, we explore the Time-Lock Encryption (TLE) cryptographic primitive. The concept of TLE involves a party initiating the encryption of a message that everyone can decrypt, only after a certain amount of time has elapsed. Following the Universal Composability (UC) paradigm introduced by Canetti [IEEE FOCS 2001], we formally abstract the concept of TLE into an ideal functionality. In addition, we provide a standalone definition for secure TLE schemes in a game-based style and we devise a hybrid UC protocol that relies on such a secure TLE scheme. The hybrid functionalities we consider are (i) a global clock, (ii) a random oracle, (iii) a broadcast channel, and (iv) a wrapper that models the limited resources of each party. We show that if the underlying TLE scheme satisfies the standalone game-based security definition, then our hybrid protocol UC realises the TLE functionality. Finally, we present Astrolabous, a TLE construction that satisfies our security definition, leading to the first UC realisation of the TLE functionality.

Abstract: We present gOTzilla, a protocol for interactive zero-knowledge proofs for large disjunctive statements of the following format: given publicly known circuit $C$, and set of values $Y = \{y_1, \ldots, y_n\}$, prove knowledge of a witness $x$ such that $C(x) = y_1 \lor C(x) = y_2 \lor \cdots \lor C(x) = y_n$. These type of statements are extremely important for the proof of assets (PoA) problem in cryptocurrencies where a prover wants to prove the knowledge of a secret key $sk$ that associates with the hash of a public key $H(pk)$ posted on the ledger.

gOTzilla is based on the MPC in the head (MPCitH) paradigm and is based on the observation that if we restructure the proof statement to an equivalent of proving knowledge of $(x,y)$ such that $(C(x) = y) \land (y = y_1 \lor \cdots \lor y = y_n))$, then we can reduce the disjunction of equalities to 1-out-of-N oblivious transfer (OT). We additionally provide a concrete, efficient extension of our protocol for the case where $C$ combines algebraic and non-algebraic statements (which is the case in the PoA application). We achieve an asymptotic communication cost of $O(\log n)$ plus the proof size of the underlying MPCitH protocol. While related work has similar asymptotic complexity, our approach results in concrete performance improvements. We implement our protocol and provide benchmarks. Concretely, for a set of size 1 million entries, the total run-time of our protocol is 14.89 seconds using 48 threads, with 6.18 MB total communication, which is about 4x faster compared to the state of the art when considering a disjunctive statement with algebraic and non-algebraic elements.

Abstract: We put forth a keyless wallet, a cryptocurrency wallet in which money can be spent using a password alone, and no private keys are required. It requires a smart contract blockchain. We propose two schemes. In the first, the user sets a short wallet password and can spend their money at a prespecified maturity date using the password alone. Using this as a stepping stone, we propose a second scheme, in which the user uses an OTP authenticator seed to generate a long series of time-based OTP passwords for the foreseeable future. These are encrypted and organized in a Merkle tree whose root is stored in a smart contract. The user can spend funds at any time by simply visually providing the current OTP password from an air gapped device. These OTPs can be relatively short: Just 6 alphanumeric characters suffice. Our OTP scheme can work in proof-of-stake as well as static and variable difficulty proof-of-work blockchains. The low-entropy in the passwords and OTPs in our scheme is protected from brute force attempts by requiring that an adversary accompany any brute force attempt by a transaction on the chain. This quickly incurs enormous economic costs for the adversary. Thus, we develop the first decentralized rate limiting scheme. We use Witness Encryption (WE) to construct a timelock encryption scheme in which passwords are encrypted from past into future blocks by leveraging the NP-language expressing proof-of-work or proof-of-stake performed as the witness. Witness Encryption is a currently impractical cryptographic primitive, but our scheme may become practical as these primitives are further developed.