Bay Area Crypto Day

We present the first protocols for private information retrieval that allow fast (sublinear-time) database lookups without increasing the server-side storage requirements. To achieve these efficiency goals, our protocols work in an offline/online model. In an offline phase, which takes place before the client has decided which database bit it wants to read, the client fetches a short string from the servers. In a subsequent online phase, the client can privately retrieve its desired bit of the database by making a second query to the servers. By pushing the bulk of the server-side computation into the offline phase (which is independent of the client's query), our protocols allow the online phase to complete very quickly—in time sublinear in the size of the database. Finally, we prove that our protocols are optimal in terms of the trade-off they achieve between communication and running time.

Joint work with Henry Corrigan-Gibbs. Paper available here.

We construct the first fully-homomorphic encryption (FHE) scheme with message-to-ciphertext length ratio (i.e., rate) 1− o(1). Our scheme is based on the hardness of the Learning with Errors (LWE) problem. As an application, we obtain the first general-purpose secure function evaluation protocol (in the preprocessing model) where the communication complexity is within an additive factor of the optimal insecure protocol.

Joint work with Zvika Brakerski, Nico Doettling, and Sanjam Garg.

TBA

Position based cryptography (PBC), proposed in the seminal work of Chandran et al. (SIAM J. Computing, 2014), aims at constructing cryptographic schemes in which the identity of the user is his geographic position. Chandran et al. construct PBC schemes in Maurer’s bounded-storage model. Apart from bounded storage, their security proofs need a strong additional restriction on the power of the adversary: he cannot compute joint functions of his inputs. Removing this assumption is left as an open problem.

In this talk (based on a joint paper with Joshua Brody, Sebastian Faust, and Krzysztof Pietrzak published at TCC 2017) I will present a connection between PBC and the theory of multiparty communication complexity. In particular, I will show that a positive answer to the open problem of Chandran et al. would resolve a long standing hypothesis in multiparty communication complexity. On a more positive side: I will also discuss some implications in the other direction, i.e., a proof that lower bounds on the communication complexity of certain multiparty problems imply the existence of some PBC primitives.

Data-sharing systems are often used to store sensitive data. Both academia and industry have proposed numerous solutions to protect the user privacy and data integrity from a compromised server. Practical state-of-the-art solutions, however, use weak threat models based on centralized trust---they assume that part of the server will remain uncompromised, or that the adversary will not perform active attacks. We propose Ghostor, a data-sharing system that, using only decentralized trust, (1) hides user identities from the server, and (2) allows users to detect server-side integrity violations. To achieve (1), Ghostor avoids keeping any per-user state at the server, requiring us to redesign the system to avoid common paradigms like per-user authentication and user-specific mailboxes. To achieve (2), Ghostor develops a technique called verifiable anonymous history. Ghostor leverages a blockchain rarely, publishing only a single hash to the blockchain for the entire system once every epoch. We empirically demonstrate that Ghostor incurs only a modest performance overhead over weaker alternatives. We believe that Ghostor has the potential to significantly boost security in practical, commercially-available data sharing systems.

The Fiat-Shamir transform applied to Kilian’s protocol (and its extension that supports interactive oracle proofs) is at the heart of both theoretical results as well as practical implementations of highly efficient non-interactive proof systems. In this work, we demonstrate significant obstacles to establishing the soundness of this approach. We exhibit a particular (contrived) interactive oracle proof (IOP) for NP for which Fiat-Shamir is unsound for any concrete hash function and any Merkle tree commitment. We also show that if Kilian’s original protocol for PCPs is instantiated with a particular (contrived) Merkle tree commitment and any “natural” PCP, then the Fiat-Shamir transform cannot be soundly applied using any concrete hash function. Put together, our results suggest that provably-secure PCP/IOP-based SNARGs will require a synergistic choice of the PCP/IOP, the Merkle tree commitment, and Fiat-Shamir hash function.

Joint work with Liron Bronfman, Justin Holmgren, Fermi Ma, and Ron D. Rothblum.

We construct a new polynomial commitment scheme for univariate and multivariate polynomials over finite fields, with public-coin evaluation proofs that have logarithmic communication and verification cost in the number of coefficients of the polynomial. The underlying technique is a \emph{Diophantine Argument of Knowledge} (DARK), leveraging integer representations of polynomials and groups of unknown order. Security is shown from the strong RSA and the adaptive root assumption. Moreover, the scheme does not require a trusted setup if instantiated with class groups. We apply this new cryptographic compiler to a restricted class of algebraic linear IOPs in order to obtain doubly-efficient public-coin IPs with succinct communication and witness-extended emulation for any NP relation. Allowing for linear preprocessing, the online verifier's work is logarithmic in the circuit complexity of the relation.

In particular, we obtain quasi-linear prover time when compiling the IOP employed in Sonic (CCS 19). Applying the Fiat-Shamir transform in the random oracle model results in a SNARK system with quasi-linear preprocessing, quasi-linear (online) prover time, logarithmic proof size, and logarithmic (online) verification time for arbitrary circuits. The SNARK is also concretely efficient with 7.8 KB proof size (70 times reduction over state of the art) and 75 ms verification time for circuits with one million gates. Most importantly, this SNARK is transparent: it does not require a trusted setup. We also obtain zk-SNARKs by applying a variant of our polynomial commitment scheme that is hiding and offers zero-knowledge evaluation proofs. This construction is the first transparent zk-SNARK that has both a practical prover time as well as asymptotically logarithmic proof size and verification time. The system is called Supersonic.