Alessandro Chiesa


Assistant Professor

Department of Electrical Engineering and Computer Science

University of California, Berkeley


alexch [at] berkeley [dot] edu

About Me


I am an assistant professor at UC Berkeley's Department of Electrical Engineering and Computer Science.
I am affiliated with the Theory, Cryptography, and Security research groups.
I cofounded SCIPR Lab, a multi-institutional research collaboration seeking to bring to practice cryptographic proof systems that provide succinct integrity and privacy.
I am an author of libsnark, a C++ library for zkSNARK proofs.

Research Interests


I am broadly interested in Theoretical Computer Science and Computer Security.
Specific interests include theoretical and applied cryptography, complexity theory, mechanism design, and others.

Teaching


Publications (DBLP, Scholar)


Preprints

  • [P1] The Hunting of the SNARK
    Cryptology ePrint Archive, Report 2014/580

    Abstract

    The existence of succinct non-interactive arguments for NP (i.e., non-interactive computationally-sound proofs where the verifier's work is essentially independent of the complexity of the NP nondeterministic verifier) has been an intriguing question for the past two decades. Other than CS proofs in the random oracle model [Micali, FOCS '94], the only existing candidate construction is based on an elaborate assumption that is tailored to a specific protocol [Di Crescenzo and Lipmaa, CiE '08].

    We formulate a general and relatively natural notion of an extractable collision-resistant hash function (ECRH) and show that, if ECRHs exist, then a modified version of Di Crescenzo and Lipmaa's protocol is a succinct non-interactive argument for NP. Furthermore, the modified protocol is actually a succinct non-interactive adaptive argument of knowledge (SNARK). We then propose several candidate constructions for ECRHs and relaxations thereof.

    We demonstrate the applicability of SNARKs to various forms of delegation of computation, to succinct non-interactive zero knowledge arguments, and to succinct two-party secure computation. Finally, we show that SNARKs essentially imply the existence of ECRHs, thus demonstrating the necessity of the assumption.

    Going beyond ECRHs, we formulate the notion of extractable one-way functions (EOWFs). Assuming the existence of a natural variant of EOWFs, we construct a 2-message selective-opening-attack secure commitment scheme and a 3-round zero-knowledge argument of knowledge. Furthermore, if the EOWFs are concurrently extractable, the 3-round zero-knowledge protocol is also concurrent zero-knowledge.

    Our constructions circumvent previous black-box impossibility results regarding these protocols by relying on EOWFs as the non-black-box component in the security reductions.

    More Info

    Available on ePrint; this paper is a merge of [BCCT11] and [GLR11].

Conference Publications

  • [C16] Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs
    S&P 2015 (36th IEEE Symposium on Security and Privacy)

    Abstract

    Non-interactive zero-knowledge proofs (NIZKs) are a powerful cryptographic tool, with numerous potential applications. However, succinct NIZKs (e.g., zk-SNARK schemes) necessitate a trusted party to generate and publish some public parameters, to be used by all provers and verifiers. This party is trusted to correctly run a probabilistic algorithm (specified by the the proof system) that outputs the public parameters, and publish them, without leaking any other information (such as the internal randomness used by the algorithm); violating either requirement may allow malicious parties to produce convincing "proofs" of false statements. This trust requirement poses a serious impediment to deploying NIZKs in many applications, because a party that is trusted by all users of the envisioned system may simply not exist.

    In this work, we show how public parameters for a class of NIZKs can be generated by a multi-party protocol, such that if at least one of the parties is honest, then the result is secure (in both aforementioned senses) and can be subsequently used for generating and verifying numerous proofs without any further trust. We design and implement such a protocol, tailored to efficiently support the state-of-the-art NIZK constructions with short and easy-to-verify proofs (Parno et al., IEEE S&P '13; Ben-Sasson et al., USENIX Sec '14; Danezis et al., ASIACRYPT '14). Applications of our system include generating public parameters for systems such as Zerocash (Ben-Sasson et al., IEEE S&P '13) and the scalable zero-knowledge proof system of (Ben-Sasson et al., CRYPTO '14).

    More Info

    The full version of the paper is forthcoming.

  • [C15] Cluster Computing in Zero Knowledge
    Alessandro Chiesa, Eran Tromer, Madars Virza
    EUROCRYPT 2015 (34th International Conference on the Theory and Applications of Cryptographic Techniques)

    Abstract

    Large computations, when amenable to distributed parallel execution, are often executed on computer clusters, for scalability and cost reasons. Such computations are used in many applications, including, to name but a few, machine learning, webgraph mining, and statistical machine translation. Oftentimes, though, the input data is private and only the result of the computation can be published. Zero-knowledge proofs would allow, in such settings, to verify correctness of the output without leaking (additional) information about the input.

    In this work, we investigate theoretical and practical aspects of zero-knowledge proofs for cluster computations. We design, build, and evaluate zero-knowledge proof systems for which: (i) a proof attests to the correct execution of a cluster computation; and (ii) generating the proof is itself a cluster computation that is similar in structure and complexity to the original one. Concretely, we focus on MapReduce, an elegant and popular form of cluster computing.

    Previous zero-knowledge proof systems can in principle prove a MapReduce computation's correctness, via a monolithic NP statement that reasons about all mappers, all reducers, and shuffling. However, it is not clear how to generate the proof for such monolithic statements via parallel execution by a distributed system. Our work demonstrates, by theory and implementation, that proof generation can be similar in structure and complexity to the original cluster computation.

    Our main technique is a bootstrapping theorem for succinct non-interactive arguments of knowledge (SNARKs) that shows how, via recursive proof composition and Proof-Carrying Data, it is possible to transform any SNARK into a distributed SNARK for MapReduce which proves, piecewise and in a distributed way, the correctness of every step in the original MapReduce computation as well as their global consistency.

    More Info

    The full version of the paper is on ePrint.

  • [C14] Scalable Zero Knowledge via Cycles of Elliptic Curves
    Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza
    CRYPTO 2014 (34th International Cryptology Conference)

    Abstract

    Non-interactive zero-knowledge proofs of knowledge for general NP statements are a powerful cryptographic primitive, both in theory and in practical applications. Recently, much research has focused on achieving an additional property, succinctness, requiring the proof to be very short and easy to verify. Such proof systems are known as zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs), and are desired when communication is expensive, or the verifier is computationally weak.

    Existing zk-SNARK implementations have severe scalability limitations, in terms of space complexity as a function of the size of the computation being proved (e.g., running time of the NP statement's decision program). First, the size of the proving key is quasilinear in the upper bound on the computation size. Second, producing a proof requires "writing down" all intermediate values of the entire computation, and then conducting global operations such as FFTs.

    The bootstrapping technique of Bitansky et al. (STOC '13), following Valiant (TCC '08), offers an approach to scalability, by recursively composing proofs: proving statements about acceptance of the proof system's own verifier (and correctness of the program's latest step). Alas, recursive composition of known zk-SNARKs has never been realized in practice, due to enormous computational cost.

    Using new elliptic-curve cryptographic techniques, and methods for exploiting the proof systems' field structure and nondeterminism, we achieve the first zk-SNARK implementation that practically achieves recursive proof composition. Our zk-SNARK implementation runs random-access machine programs and produces proofs of their correct execution, on today's hardware, for any program running time. It takes constant time to generate the keys that support all computation sizes. Subsequently, the proving process only incurs a constant multiplicative overhead compared to the original computation's time, and an essentially-constant additive overhead in memory. Thus, our zk-SNARK implementation is the first to have a well-defined, albeit low, clock rate of "verified instructions per second".

    More Info

    The full version of the paper is on ePrint.

  • [C13] Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture
    Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza
    USENIX Security 2014 (23rd USENIX Security Symposium)

    Abstract

    We build a system that provides succinct non-interactive zero-knowledge proofs (zk-SNARKs) for program executions on a von Neumann RISC architecture. The system has two components: a cryptographic proof system for verifying satisfiability of arithmetic circuits, and a circuit generator to translate program executions to such circuits. Our design of both components improves in functionality and efficiency over prior work, as follows.

    Our circuit generator is the first to be universal: it does not need to know the program, but only a bound on its running time. Moreover, the size of the output circuit depends additively (rather than multiplicatively) on program size, allowing verification of larger programs.

    The cryptographic proof system improves proving and verification times, by leveraging new algorithms and a pairing library tailored to the protocol.

    We evaluated our system for programs with up to 10,000 instructions, running for up to 32,000 machine steps, each of which can arbitrarily access random-access memory; and also demonstrated it executing programs that use just-in-time compilation. Our proofs are 230 bytes long at 80 bits of security, or 288 bytes long at 128 bits of security. Typical verification time is 5 milliseconds, regardless of the original program's running time.

    More Info

    The full version of the paper is on ePrint.

  • [C12] Knightian Self Uncertainty in the VCG Mechanism for Unrestricted Combinatorial Auctions
    Alessandro Chiesa, Silvio Micali, Zeyuan Allen Zhu
    EC 2014 (15th ACM Conference on Economics and Computation)

    Abstract

    We study the social welfare performance of the VCG mechanism in the well-known and challenging model of self uncertainty initially put forward by Frank H. Knight and later formalized by Truman F. Bewley. Namely, the only information that each player i has about his own true valuation consists of a set of distributions, from one of which i's valuation has been drawn.

    We assume that each player knows his true valuation up to an additive inaccuracy d, and study the social welfare performance of the VCG mechanism relative to d > 0. In this paper, we focus on the social welfare performance of the VCG mechanism in unrestricted combinatorial auctions, both in undominated strategies and regret-minimizing strategies. Denote by MSW the maximum social welfare.

    Our first theorem proves that, in an n-player m-good combinatorial auction, the VCG mechanism may produce outcomes whose social welfare is <= MSW - Ω(2^m d), even when n=2 and each player chooses an undominated strategy. We also geometrically characterize the set of undominated strategies in this setting.

    Our second theorem shows that the VCG mechanism performs well in regret-minimizing strategies: the guaranteed social welfare is >= MSW - 2min{m,n}d if each player chooses a pure regret-minimizing strategy, and >= MSW - O(n^2 d) if mixed strategies are allowed.

    Finally, we prove a lemma bridging two standard models of rationality: utility maximization and regret minimization. A special case of our lemma implies that, in any game (Knightian or not), every implementation for regret-minimizing players also applies to utility-maximizing players who use regret only to break ties among their undominated strategies. This bridging lemma thus implies that the VCG mechanism continues to perform very well also for the latter players.

    More Info

    The full version of this paper is here.

  • [C11] Zerocash: Decentralized Anonymous Payments from Bitcoin
    S&P 2014 (35th IEEE Symposium on Security and Privacy)

    Abstract

    Bitcoin is the first digital currency to see widespread adoption. While payments are conducted between pseudonyms, Bitcoin cannot offer strong privacy guarantees: payment transactions are recorded in a public decentralized ledger, from which much information can be deduced. Zerocoin (Miers et al., IEEE S&P 2013) tackles some of these privacy issues by unlinking transactions from the payment's origin. Yet, it still reveals payments' destinations and amounts, and is limited in functionality.

    In this paper, we construct a full-fledged ledger-based digital currency with strong privacy guarantees. Our results leverage recent advances in zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs).

    First, we formulate and construct decentralized anonymous payment schemes (DAP schemes). A DAP scheme enables users to directly pay each other privately: the corresponding transaction hides the payment's origin, destination, and transferred amount. We provide formal definitions and proofs of the construction's security.

    Second, we build Zerocash, a practical instantiation of our DAP scheme construction. In Zerocash, transactions are less than 1 kB and take under 6 ms to verify --- orders of magnitude more efficient than the less-anonymous Zerocoin and competitive with plain Bitcoin.

    More Info

    The full version of the paper is on ePrint. See the Zerocash project website.

  • [C10] SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
    CRYPTO 2013 (33rd International Cryptology Conference)

    Abstract

    An argument system for NP is a proof system that allows efficient verification of NP statements, given proofs produced by an untrusted yet computationally-bounded prover. Such a system is non-interactive and publicly-verifiable if, after a trusted party publishes a proving key and a verification key, anyone can use the proving key to generate non-interactive proofs for adaptively-chosen NP statements, and proofs can be verified by anyone by using the verification key.

    We present an implementation of a publicly-verifiable non-interactive argument system for NP. The system, moreover, is a zero-knowledge proof-of-knowledge. It directly proves correct executions of programs on TinyRAM, a random-access machine tailored for efficient verification of nondeterministic computations. Given a program $P$ and time bound T, the system allows for proving correct execution of $P$, on any input $x$, for up to T steps, after a one-time setup requiring $\tilde{O}(|P| T)$ cryptographic operations. An honest prover requires $\tilde{O}(|P| T)$ cryptographic operations to generate such a proof, while proof verification can be performed with only $O(|x|)$ cryptographic operations. This system can be used to prove the correct execution of C programs, using our TinyRAM port of the GCC compiler.

    This yields a zero-knowledge Succinct Non-interactive ARgument of Knowledge (zk-SNARK) for program executions in the preprocessing model -- a powerful solution for delegating NP computations, with several features not achieved by previously-implemented primitives.

    Our approach builds on recent theoretical progress in the area. We present efficiency improvements and implementations of two main ingredients:

    1. Given a C program, we produce a circuit whose satisfiability encodes the correctness of execution of the program. Leveraging nondeterminism, the generated circuit's size is merely quasilinear in the size of the computation. In particular, we efficiently handle arbitrary and data-dependent loops, control flow, and memory accesses. This is in contrast with existing "circuit generators", which in the general case produce circuits of quadratic size.

    2. Given a linear PCP for verifying satisfiability of circuits, we produce a corresponding SNARK. We construct such a linear PCP (which, moreover, is zero-knowledge and very efficient) by building on and improving on recent work on quadratic arithmetic programs.

    More Info

    The full version of the paper is on ePrint. An MIT News article about this paper can be found here.

  • [C09] On the Concrete Efficiency of Probabilistically-Checkable Proofs
    STOC 2013 (45th ACM Symposium on the Theory of Computing)

    Abstract

    Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables fast verification of long computations in many cryptographic constructions. Yet, despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these powerful cryptographic constructions from being used in practice. To address this problem, we present several results about the computational efficiency of PCPs.

    We construct the first PCP where the prover and verifier time complexities are quasi-optimal (i.e., optimal up to poly-logarithmic factors). The prover and verifier are also higly-parallelizable, and these computational guarantees hold even when proving and verifying the correctness of random-access machine computations. Our construction is explicit and has the requisite properties for being used in the cryptographic applications mentioned above.

    Next, to better understand the efficiency of our PCP, we propose a new efficiency measure for PCPs (and their major components, locally-testable codes and PCPs of proximity). We define a concrete-efficiency threshold that indicates the smallest problem size beyond which the PCP becomes “useful”, in the sense that using it is cheaper than performing naive verification (i.e., rerunning the computation); our definition accounts for both the prover and verifier complexity.

    We then show that our PCP has a finite concrete-efficiency threshold. That such a PCP exists does not follow from existing works on PCPs with polylogarithmic-time verifiers.

    As in [Ben-Sasson and Sudan, STOC '05], PCPs of proximity for Reed–Solomon (RS) codes are the main component of our PCP. We construct a PCP of proximity that reduces the concrete-efficiency threshold for testing proximity to RS codes from 2^{683} in their work to 2^{43}, which is tantalizingly close to practicality.

    More Info

    The full version of the paper is on ECCC. The Mathematica file with concrete-efficiency threshold computations is here.

  • [C08] Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data
    Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
    STOC 2013 (45th ACM Symposium on the Theory of Computing)

    Abstract

    Succinct non-interactive arguments (SNARGs) enable verifying NP statements with much lower complexity than required for classical NP verification (in fact, with complexity that is independent of the NP language at hand). In particular, SNARGs provide strong solutions to the problem of verifiably delegating computation.

    Despite recent progress in the understanding and construction of SNARGs, there remain unattained goals. First, publicly-verifiable SNARGs are only known either in the random oracle model, or in a model that allows expensive offline preprocessing. Second, known SNARGs require from the prover significantly more time or space than required for classical NP verification.

    We show that, assuming collision-resistant hashing, any SNARG having a natural proof of knowledge property (i.e., a SNARK) can be "bootstrapped" to obtain a complexity-preserving SNARK, i.e., one without expensive preprocessing and where the prover's time and space complexity is essentially the same as that required for classical NP verification. By applying our transformation to known publicly-verifiable SNARKs with expensive preprocessing, we obtain the first publicly-verifiable complexity-preserving SNARK in the plain model (and in particular, eliminate the expensive preprocessing), thereby attaining the aforementioned goals. We also show an analogous transformation for privately-verifiable SNARKs, assuming fully-homomorphic encryption. Curiously, our transformations do not rely on PCPs.

    At the heart of our transformations is recursive composition of SNARKs and, more generally, new techniques for constructing and using proof-carrying data (PCD) systems, which extend the notion of a SNARK to the distributed setting. Concretely, to bootstrap a given SNARK, we recursively compose the SNARK to obtain a "weak" PCD system for shallow distributed computations, and then use the PCD framework to attain stronger, complexity-preserving SNARKs and PCD systems.

    More Info

    The full version of the paper is on ePrint.

  • [C07] Succinct Non-Interactive Arguments via Linear Interactive Proofs
    TCC 2013 (10th Theory of Cryptography Conference)

    Abstract

    Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays researchers have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation.

    A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O(1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have "escaped the hegemony" of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments.

    We present a general methodology for the construction of preprocessing SNARGs, as well as resulting concrete efficiency improvements. Our contribution is three-fold:

    1. We introduce and study a natural extension of the interactive proof model that considers algebraically-bounded provers; this new setting is analogous to the common study of algebraically-bounded "adversaries" in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) linear-interactive proofs (LIPs) for NP. Our constructions are based on general transformations applied to both linear PCPs (LPCPs) and traditional "unstructured" PCPs.

    2. We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of linear targeted malleability (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain zero-knowledge LIPs and SNARGs. Our techniques yield SNARGs of knowledge and thus can benefit from known recursive composition and bootstrapping techniques.

    3. Following this methodology, we exhibit several constructions achieving new efficiency features, such as "single-ciphertext preprocessing SNARGs" and improved succinctness-soundness tradeoffs. We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.

    More Info

    The full version of the paper is on ePrint.

  • [C06] Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems
    ITCS 2013 (4th Symposium on Innovations in Theoretical Computer Science)

    Abstract

    Succinct arguments for NP are proof systems that allow a weak verifier to retroactively check computation done by a powerful prover. Constructions of such protocols prove membership in languages consisting of very large yet succinctly-represented constraint satisfaction problems that, alas, are unnatural in the sense that the problems that arise in practice are not in such form.

    For general computation tasks, the most natural representation is typically as random-access machine (RAM) algorithms, because such a representation can be obtained very efficiently by applying a compiler to code written in a high-level programming language. Thus, understanding the efficiency of reductions from RAM computations to other NP-complete problem representations for which succinct arguments (or proofs) are known is a prerequisite to a more complete understanding of the applicability of these arguments.

    Existing succinct argument constructions rely either on circuit satisfiability or (in PCP-based constructions) on algebraic constraint satisfaction problems. In this paper, we present new and more efficient reductions from RAM (and parallel RAM) computations to both problems that (a) preserve succinctness (i.e., do not "unroll" the computation of a machine), (b) preserve zero-knowledge and proof-of-knowledge properties, and (c) enjoy fast and highly-parallelizable algorithms for transforming a witness to the RAM computation into a witness for the corresponding problem. These additional properties are typically not considered in "classical" complexity theory but are often required or very desirable in the application of succinct arguments.

    Fulfilling all these efficiency requirements poses significant technical challenges, and we develop a set of tools (both unconditional and leveraging computational assumptions) for generically and efficiently structuring and arithmetizing RAM computations for use in succinct arguments. More generally, our results can be applied to proof systems for NP relying on the aforementioned problem representations; these include various zero-knowledge proof constructions.

    More Info

    The full version of the paper is on ePrint.

  • [C05] Succinct Arguments from Multi-Prover Interactive Proofs and their Efficiency Benefits
    Nir Bitansky, Alessandro Chiesa
    CRYPTO 2012 (32nd International Cryptology Conference)

    Abstract

    Succinct arguments of knowledge are computationally-sound proofs of knowledge for NP where the verifier's running time is independent of the time complexity t of the nondeterministic NP machine M that decides the given language. Existing succinct argument constructions are, typically, based on techniques that combine cryptographic hashing and probabilistically-checkable proofs (PCPs). Yet, even when instantiating these constructions with state-of-the-art PCPs, the prover needs Ω(t) space in order to run in quasilinear time (i.e., time t*poly(k)), regardless of the space complexity s of the machine M.

    We say that a succinct argument is complexity preserving if the prover runs in time t*poly(k) and space s*poly(k) and the verifier runs in time |x|*poly(k) when proving and verifying that a t-time s-space random-access machine nondeterministically accepts an input x. Do complexity-preserving succinct arguments exist? To study this question, we investigate the alternative approach of constructing succinct arguments based on multi-prover interactive proofs (MIPs) and stronger cryptographic techniques:

    (1) We construct a one-round succinct MIP of knowledge, where each prover runs in time t*polylog(t) and space s*polylog(t) and the verifier runs in time |x|*polylog(t).

    (2) We show how to transform any one-round MIP protocol to a succinct four-message argument (with a single prover), while preserving the time and space efficiency of the original MIP protocol; using our MIP protocol, this transformation yields a complexity-preserving four-message succinct argument.

    As a main tool for our transformation, we define and construct a succinct multi-function commitment that (a) allows the sender to commit to a vector of functions in time and space complexity that are essentially the same as those needed for a single evaluation of the functions, and (b) ensures that the receiver's running time is essentially independent of the function. The scheme is based on fully-homomorphic encryption (and no additional assumptions are needed for our succinct argument).

    (3) In addition, we revisit the problem of non-interactive succinct arguments of knowledge (SNARKs), where known impossibilities prevent solutions based on black-box reductions to standard assumptions. We formulate a natural (but non-standard) variant of homomorphic encryption having a homomorphism-extraction property. We show that this primitive essentially allows to squash our interactive protocol, while again preserving time and space efficiency, thereby obtaining a complexity-preserving SNARK. We further show that this variant is, in fact, implied by the existence of (complexity-preserving) SNARKs.

    More Info

    The full version of the paper is on ePrint.

  • [C04] From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again
    Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
    ITCS 2012 (3rd Symposium on Innovations in Theoretical Computer Science)

    Abstract

    The existence of succinct non-interactive arguments for NP (i.e., non-interactive computationally-sound proofs where the verifier's work is essentially independent of the complexity of the NP nondeterministic verifier) has been an intriguing question for the past two decades. Other than CS proofs in the random oracle model [Micali, FOCS '94], the only existing candidate construction is based on an elaborate assumption that is tailored to a specific protocol [Di Crescenzo and Lipmaa, CiE '08].

    We formulate a general and relatively natural notion of an extractable collision-resistant hash function (ECRH) and show that, if ECRHs exist, then a modified version of Di Crescenzo and Lipmaa's protocol is a succinct non-interactive argument for NP. Furthermore, the modified protocol is actually a succinct non-interactive adaptive argument of knowledge (SNARK). We then propose several candidate constructions for ECRHs and relaxations thereof.

    We demonstrate the applicability of SNARKs to various forms of delegation of computation, to succinct non-interactive zero knowledge arguments, and to succinct two-party secure computation. Finally, we show that SNARKs essentially imply the existence of ECRHs, thus demonstrating the necessity of the assumption.

    More Info

    The full version of the paper is on ePrint.

  • [C03] Mechanism Design with Approximate Valuations
    Alessandro Chiesa, Silvio Micali, Zeyuan Allen Zhu
    ITCS 2012 (3rd Symposium on Innovations in Theoretical Computer Science)

    Abstract

    We study single-good auctions in a setting where each player knows his own valuation only within a constant multiplicative factor δ in (0,1), and the mechanism designer knows δ. The classical notions of implementation in dominant strategies and implementation in undominated strategies are naturally extended to this setting, but their power is vastly different.

    On the negative side, we prove that no dominant-strategy mechanism can guarantee social welfare that is significantly better than that achievable by assigning the good to a random player.

    On the positive side, we provide tight upper and lower bounds for the fraction of the maximum social welfare achievable in undominated strategies, whether deterministically or probabilistically.

    More Info

    The ITCS 2012 version is only an introductory non-archival draft. The full version of the paper, with the title Knightian Auctions, is on the arXiv.

  • [C02] Proof-Carrying Data and Hearsay Arguments from Signature Cards
    Alessandro Chiesa, Eran Tromer
    ITCS 2010 (1st Symposium on Innovations in Theoretical Computer Science)

    Abstract

    The security of systems can often be expressed as ensuring that some property is maintained at every step of a distributed computation conducted by untrusted parties. Special cases include integrity of programs running on untrusted platforms, various forms of confidentiality and side-channel resilience, and domain-specific invariants.

    We propose a new approach, proof-carrying data (PCD), which sidesteps the threat of faults and leakage by reasoning about properties of a computation's output data, regardless of the process that produced it. In PCD, the system designer prescribes the desired properties of a computation's outputs. Corresponding proofs are attached to every message flowing through the system, and are mutually verified by the system's components. Each such proof attests that the message's data and all of its history comply with the prescribed properties.

    We construct a general protocol compiler that generates, propagates, and verifies such proofs of compliance, while preserving the dynamics and efficiency of the original computation. Our main technical tool is the cryptographic construction of short non-interactive arguments (computationally-sound proofs) for statements whose truth depends on "hearsay evidence": previous arguments about other statements. To this end, we attain a particularly strong proof-of-knowledge property.

    We realize the above, under standard cryptographic assumptions, in a model where the prover has black- box access to some simple functionality --- essentially, a signature card.

    More Info

    The conference paper can be found here.

  • [C01] A Security Analysis of the Boston T
    Zackary Anderson, Alessandro Chiesa, Samuel McVeety, Russell Ryan
    DEF CON 16 (hacker convention in Las Vegas in 2008)

    Abstract

    In this talk we go over weaknesses in common subway fare collection systems. We focus on the Boston T subway, and show how we reverse engineered the data on magstripe card; we present several attacks to completely break the CharlieCard, a MIFARE Classic smartcard used in many subways around the world; and we discuss physical security problems. We will discuss practical brute force attacks using FPGAs and how to use software-radio to read RFID cards. We survey 'human factors' that lead to weaknesses in the system, and we present a novel new method of hacking WiFi: WARCARTING. We will release several open source tools we wrote in the process of researching these attacks. With live demos, we will demonstrate how we broke these systems.

    More Info

    The talk had to be canceled!

Journal Publications

  • [J3] Knightian Robustness of the Vickrey Mechanism
    Alessandro Chiesa, Silvio Micali, Zeyuan Allen Zhu
    Econometrica, to appear

    Abstract

    We analyze the Vickrey mechanism for auctions of multiple identical goods when the players have both Knightian uncertainty over their own valuations and incomplete preferences. In this model, the Vickrey mechanism is no longer dominant-strategy, and we prove that all dominant-strategy mechanisms are inadequate. However, we also prove that, in undominated strategies, the social welfare produced by the Vickrey mechanism in the worst case is not only very good, but also essentially optimal.

    More Info

    Find the paper here.

  • [J2] Improved Soundness for QMA with Multiple Provers
    Alessandro Chiesa, Michael A. Forbes

    Abstract

    We present three contributions to the understanding of QMA with multiple provers:

    1. We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap Ω(N^{-2}). Our improvement is achieved without the use of an instance with a constant soundness gap (i.e., without using a "PCP").

    2. We give a tight soundness analysis of the protocol of [Chen and Drucker, ArXiV '10], thereby improving their result from a "monolithic" protocol where Θ(√N) provers are needed in order to have any soundness gap, to a protocol with a smooth trade-off between the number of provers k and a soundness gap Ω(k^{2}N^{-1}), as long as k >= Ω(log N). (And, when k <= Θ(√N), we recover the original parameters of Chen and Drucker.)

    3. We make progress towards an open question of [Aaronson et al., ToC '09] about what kinds of NP-complete problems are amenable to "sublinear" multiple-prover QMA protocols, by observing that a large class of such examples can easily be derived from results already in the PCP literature --- namely, at least the languages recognized by a non-deterministic RAMs in quasilinear time.

    More Info

    Find the paper on the arXiv and on CJTCS.

  • [J1] Proof-carrying data: Secure computation on untrusted platforms
    Alessandro Chiesa, Eran Tromer

    Abstract

    When running software applications and services, we rely on the underlying execution platform: the hardware and the lower levels of the software stack. The execution platform is susceptible to a wide range of threats, ranging from accidental bugs, faults, and leaks to maliciously induced Trojan horses. The problem is aggravated by growing system complexity and by increasingly pertinent outsourcing and supply chain consideration. Traditional mechanisms, which painstakingly validate all system components, are expensive and limited in applicability. What if the platform assurance problem is just too hard? Do we have any hope of securely running software when we cannot trust the underlying hardware, hypervisor, kernel, libraries, and compilers? This article will discuss a potential approach for doing just so: conducting trustworthy computation on untrusted execution platforms. The approach, proof-carrying data (PCD), circumnavigates the threat of faults and leakage by reasoning solely about properties of a computation's output data, regardless of the process that produced it. In PCD, the system designer prescribes the desired properties of the computation's outputs. These properties are then enforced using cryptographic proofs attached to all data flowing through the system and verified at the system perimeter as well as internal nodes.

    More Info

    Find the paper on NSA's website.

Theses

  • [T2] Succinct Non-Interactive Arguments
    Ph.D. thesis (September 2014)
    MIT EECS Department
    Advised by Prof. Silvio Micali

    Abstract

    Succinct non-interactive arguments (SNARGs), also known as "CS proofs" [Micali, FOCS 1994], enable verifying NP statements with much lower complexity than required for classical NP verification (in fact, with complexity that is independent of the NP language at hand). In particular, SNARGs provide strong solutions to the problem of verifiably delegating computation. A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase, independent of the statement to be proven later.

    In this thesis we present two main results:

    1. A general methodology for the construction of preprocessing SNARGs.

    2. A transformation, based on collision-resistant hashing, that takes any SNARG having a natural proof of knowledge property (i.e., a SNARK) as input and "bootstrapps" it to obtain a complexity-preserving SNARK, i.e., one without expensive preprocessing and where the prover's time and space complexity is essentially the same as that required for classical NP verification.

    These results provide the first publicly-verifiable complexity-preserving SNARK in the plain model. At the heart of our transformations is recursive composition of SNARKs and, more generally, new techniques for constructing and using proof-carrying data (PCD) systems, which extend the notion of a SNARK to the distributed setting. Concretely, to bootstrap a given SNARK, we recursively compose the SNARK to obtain a "weak" PCD system for shallow distributed computations, and then use the PCD framework to attain stronger, complexity-preserving SNARKs and PCD systems.

    More Info

    The thesis is available on DSpace@MIT.

  • [T1] Proof-Carrying Data
    M.Eng. thesis (June 2010)
    MIT EECS Department
    Advised by Prof. Ronald L. Rivest and Prof. Eran Tromer

    Abstract

    The security of systems can often be expressed as ensuring that some property is maintained at every step of a distributed computation conducted by untrusted parties. Special cases include integrity of programs running on untrusted platforms, various forms of confidentiality and side-channel resilience, and domain-specific invariants.

    We propose a new approach, proof-carrying data (PCD), which sidesteps the threat of faults and leakage by reasoning about properties of a computation’s output data, regardless of the process that produced it. In PCD, the system designer prescribes the desired properties of a computation’s outputs. Corresponding proofs are attached to every message flowing through the system, and are mutually verified by the system’s components. Each such proof attests that the message’s data and all of its history comply with the prescribed properties.

    We construct a general protocol compiler that generates, propagates, and verifies such proofs of compliance, while preserving the dynamics and efficiency of the original computation. Our main technical tool is the cryptographic construction of short non-interactive arguments (computationally-sound proofs) for statements whose truth depends on "hearsay evidence": previous arguments about other statements. To this end, we attain a particularly strong proof-of-knowledge property.

    We realize the above, under standard cryptographic assumptions, in a model where the prover has black- box access to some simple functionality --- essentially, a signature card.

    More Info

    The thesis is available on DSpace@MIT.

Short Bio


I joined UC Berkeley's faculty in the summer of 2015.
Prior to that, I spent one year as a postdoctoral researcher at ETH Zürich; my host was Prof. Thomas Holenstein.
I earned my Ph.D. in the Theory of Computation group in CSAIL at MIT; my doctoral thesis advisor was Prof. Silvio Micali.
I earned my M.Eng. in the same group; my master's thesis advisors were Prof. Eran Tromer and Prof. Ron Rivest.
I earned my S.B. in Mathematics and my S.B. in Computer Science at MIT; outside of classes and labs, I rowed for the heavyweight varsity crew team at MIT.
A list of my old coursework while at MIT can be found here.
Before coming to MIT, I lived in Varese, Italy, where I was born in 1987. While in Italy, I attended the European School of Varese from kindergarten through high school; this school is part of the system of European Schools, which awards students the European Baccalaureate.
I enjoy many outdoor sports, including biking, climbing, mountaineering, and running.

Contact


The best way to contact me is via the email at the top of this page.
My temporary office is located in 773 Soda Hall; I will relocate to 683 after that.



I proudly support:    ACLU logo    EFF logo    JREF logo    MIT logo    RDF logo