2023

1. TCC

   Cryptography from Planted Graphs: Security with Logarithmic-Size Messages

   Damiano Abram, Amos Beimel, Yuval Ishai, Eyal Kushilevits, and Varun Narayanan

   In Theory of Cryptography Conference – TCC 2023.

   Abs

   We tackle the following broad question about cryptographic primitives: is it possible to achieve security against arbitrary poly(n) circuit-size adversaries with O(log n) size messages? It is common knowledge that the answer is unless information-theoretic security is possible. In this work, we revisit this question by considering the setting of cryptography with public information and computational security. Our main results include the following:
   

   1. For the task of constructing protocols in the Private Simultaneous Message (PSM) model. We show that O(log n) bits suffice if we allow public information and computational security.

   2. For the task of 3-party MPC, where 2 parties have inputs and the third party receive the output, we present a protocol with an offline stage that produces shared randomness for the input parties and public information, followed by a one-round protocol after receiving the input (a single message from each input party to the output party) with very short, i.e. O(log n) bits, online communication. Previously known solutions (even allowing correlated randomness) used at least two rounds of communication.

   3. For the task of constructing so-called Forbidden Graph Secret-Sharing, the best known computational scheme without public information has share size poly(n) (assuming one-way functions). We present a computational Forbidden Graph Secret-Sharing scheme with public information and share size of only O(log n). On the negative side, we show that computational threshold secret-sharing schemes even with public information require share size Ω(log log n).

   Our constructions are based on the conjectured hardness of variants of the planted clique problem, that was extensively studied in the Complexity Theory and Statistical Inference communications but was less commonly used in Crypto. We believe that such conjectures have the potential of finding other cryptographic applications.

2. C

   Security-Preserving Distributed Samplers: How to Generate any CRS in One Round without Random Oracles

   Damiano Abram, Brent Waters, and Mark Zhandry

   In CRYPTO 2023.

   Abs PDF

   A distributed sampler is a way for several mutually distrusting parties to non-interactively generate a common reference string (CRS) that all parties trust. Previous work constructs distributed samplers in the random oracle model, or in the standard model with very limited security guarantees. This is no accident, as standard model distributed samplers with full security were shown impossible. In this work, we provide new definitions for distributed samplers which we show achieve meaningful security guarantees in the standard model. In particular, our notion implies that the hardness of a wide range of security games is preserved when the CRS is replaced with a distributed sampler. We also show how to realize our notion of distributed samplers. A core technical tool enabling our construction is a new notion of single-message zero knowledge.

2022

1. C

   An Algebraic Framework for Silent Preprocessing with Trustless Setup and Active Security

   Damiano Abram, Ivan Damgård, Claudio Orlandi, and Peter Scholl

   In CRYPTO 2022.

   Abs PDF

   Recently, number-theoretic assumptions including DDH, DCR and QR have been used to build powerful tools for secure computation, in the form of homomorphic secret-sharing (HSS), which leads to secure two-party computation protocols with succinct communication, and pseudorandom correlation functions (PCFs), which allow non-interactive generation of a large quantity of correlated randomness. In this work, we present a group-theoretic framework for these classes of constructions, which unifies their approach to computing distributed discrete logarithms in various groups. We cast existing constructions in our framework, and also present new constructions, including one based on class groups of imaginary quadratic fields. This leads to the first construction of two- party homomorphic secret sharing for branching programs from class group assumptions. Using our framework, we also obtain pseudorandom correlation functions for generating oblivious transfer and vector-OLE correlations from number-theoretic assumptions. These have a trustless, public-key setup when instantiating our framework using class groups. Previously, such constructions either needed a trusted setup in the form of an RSA modulus with unknown factorisation, or relied on multi-key fully homomorphic encryption from the learning with errors assumption. We also show how to upgrade our constructions to achieve active security using appropriate zero-knowledge proofs. In the random oracle model, this leads to a one-round, actively secure protocol for setting up the PCF, as well as a 3-round, actively secure HSS-based protocol for secure two-party computation of branching programs with succinct communication.

2. S&P

   Low-Bandwidth Threshold ECDSA via Pseudorandom Correlation Generators

   Damiano Abram, Ariel Nof, Claudio Orlandi, Peter Scholl, and Omer Shlomovits

   In 2022 IEEE Symposium on Security and Privacy.

   Abs PDF

   Digital signature schemes are a fundamental component of secure distributed systems, and the theft of a signing-key might have huge real-world repercussions e.g., in applications such as cryptocurrencies. Threshold signature schemes mitigate this problem by distributing shares of the secret key on several servers and requiring that enough of them interact to be able to compute a signature. In this paper, we provide a novel threshold protocol for ECDSA, arguably the most relevant signature scheme in practice. Our protocol is the first one where the communication complexity of the preprocessing phase is only logarithmic in the number of ECDSA signatures to be produced later, and it achieves therefore a so-called silent preprocessing. Our protocol achieves active security against any number of arbitrarily corrupted parties.

3. EC

   Distributed (Correlation) Samplers: How to Remove a Trusted Dealer in One Round

   Damiano Abram, Peter Scholl, and Sophia Yakoubov

   In EUROCRYPT 2022.

   Abs PDF

   Structured random strings (SRSs) and correlated randomness are important for many cryptographic protocols. In settings where interaction is expensive, it is desirable to obtain such randomness in as few rounds of communication as possible; ideally, simply by exchanging one reusable round of messages which can be considered public keys. In this paper, we describe how to generate any SRS or correlated randomness in such a single round of communication, using, among other things, indistinguishable obfuscation. We introduce what we call a distributed sampler, which enables n parties to sample a single public value (SRS) from any distribution. We construct a semi-malicious distributed sampler in the plain model, and use it to build a semi-malicious publickey PCF (Boyle et al., FOCS 2020) in the plain model. A public-key PCF can be thought of as a distributed correlation sampler; instead of producing a public SRS, it gives each party a private random value (where the values satisfy some correlation). We introduce a general technique called an anti-rusher which compiles any one-round protocol with semi-malicious security without inputs to a similar one-round protocol with active security by making use of a programmable random oracle. This gets us actively secure distributed samplers and public-key PCFs in the random oracle model. Finally, we explore some tradeoffs. Our first PCF construction is limited to reverse-sampleable correlations (where the random outputs of honest parties must be simulatable given the random outputs of corrupt parties); we additionally show a different construction without this limitation, but which does not allow parties to hold secret parameters of the correlation. We also describe how to avoid the use of a random oracle at the cost of relying on sub-exponentially secure indistinguishability obfuscation.

4. PKC

   Low-Communication Multiparty Triple Generation for SPDZ from Ring-LPN

   Damiano Abram, and Peter Scholl

   In Public-Key Cryptography – PKC 2022.

   Abs PDF

   The SPDZ protocol for multi-party computation relies on a correlated randomness setup consisting of authenticated, multiplication triples. A recent line of work by Boyle et al. (Crypto 2019, Crypto 2020) has investigated the possibility of producing this correlated randomness in a silent preprocessing phase, which involves a “small” setup protocol with less communication than the total size of the triples being produced. These works do this using a tool called a pseudorandom correlation generator (PCG), which allows a large batch of correlated randomness to be compressed into a set of smaller, correlated seeds. However, existing methods for compressing SPDZ triples only apply to the 2-party setting. In this work, we construct a PCG for producing SPDZ triples over large prime fields in the multi-party setting. The security of our PCG is based on the ring-LPN assumption over fields, similar to the work of Boyle et al. (Crypto 2020) in the 2-party setting. We also present a corresponding, actively secure setup protocol, which can be used to generate the PCG seeds and instantiate SPDZ with a silent preprocessing phase. As a building block, which may be of independent interest, we construct a new type of 3-party distributed point function supporting outputs over arbitrary groups (including large prime order), as well as an efficient protocol for setting up our DPF keys with active security.

2021

1. CT-RSA

   Oblivious TLS via Multi-party Computation

   Damiano Abram, Ivan Damgård, Peter Scholl, and Sven Trieflinger

   In Topics in Cryptology - CT-RSA 2021 - Cryptographers’ Track at the RSA Conference 2021.

   Abs PDF

   In this paper, we describe Oblivious TLS: an MPC protocol that we prove UC secure against a majority of actively corrupted parties. The protocol securely implements TLS 1.3. Thus, any party P who runs TLS can communicate securely with a set of servers running Oblivious TLS; P does not need to modify anything, or even be aware that MPC is used. Applications of this include communication between servers who offer MPC services and clients, to allow the clients to easily and securely provide inputs or receive outputs. Also, an organization could use Oblivious TLS to improve in-house security while seamlessly connecting to external parties. Our protocol runs in the preprocessing model, and we did a preliminary non-optimized implementation of the on-line phase. In this version, the hand-shake completes in about 1 second. Performance of the record protocol depends, of course, on the encryption scheme used. We designed an MPC friendly scheme which achieved a throughput of about 300 KB/sec. Based on implementation results from other work, the standard AES-GCM can be expected to be as fast, although our implementation did not do as well.