peer-reviewed publications
2025
- STOCSuccinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All CircuitsDamiano Abram , Giulio Malavolta , and Lawrence RoySTOC 2025 , 2025
We propose the notion of succinct oblivious tensor evaluation (OTE), where two parties compute an additive secret sharing of a tensor product of two vectors x⊗y, exchanging two simultaneous messages. Crucially, the size of both messages and of the CRS is independent of the dimension of x. We present a construction of OTE with optimal complexity from the standard learning with errors (LWE) problem. Then we show how this new technical tool enables a host of cryptographic primitives, all with security reducible to LWE, such as:
1. Adaptively secure laconic function evaluation for depth-D functions
f:{0, 1}m→{0, 1}L with communication m+L+D⋅poly(λ).2. A trapdoor hash function for all functions.
3. An (optimally) succinct homomorphic secret sharing for all functions.
4. A rate-1/2 laconic oblivious transfer for batch messages, which is best possible.
In particular, we obtain the first laconic function evaluation scheme that is adaptively secure from the standard LWE assumption, improving upon Quach, Wee, and Wichs (FOCS 2018). As a key technical ingredient, we introduce a new notion of adaptive lattice encodings, which may be of independent interest.
- CKey-Homomorphic Computations for RAM: Fully Succinct Randomised Encodings and MoreDamiano Abram , Giulio Malavolta , and Lawrence RoyCRYPTO 2025 , 2025
We propose a new method to construct a public-key encryption scheme, where one can homomorphically transform a ciphertext encrypted under a key x into a ciphertext under (P, P(x)), for any polynomial-time RAM program P: x ↦ y with runtime T and memory L. Combined with other lattice techniques, this allows us to construct:
1. Succinct-randomised encodings from RAM programs with encoder complexity (|x|+ |y|) ⋅poly(log T, log L) and rate-1 encodings.
2. Laconic function evaluation for RAM programs, with encoder runtime bounded by (|x|+ |y|) ⋅poly(log T, log L) and rate-1 encodings.
3. Key-policy attribute-based encryption for RAM programs, with ciphertexts of size O(T). The same scheme can be converted to the register setting, obtaining linear CRS size in the number of parties.
All of our schemes rely on the hardness of the decomposed learning with errors (LWE) problem, along with other standard computational assumptions on lattices. The decomposed LWE problem can be interpreted as postulating the circular-security of a natural lattice-based public-key encryption scheme. To gain confidence in the assumption, we show that it is implied by the hardness of the succinct LWE problem of Wee (CRYPTO’24).
2024
- ECConstant-Round Simulation-Secure Coin Tossing Extention with Guaranteed OutputDamiano Abram , Jack Doerner , Yuval Ishai , and 1 more authorEUROCRYPT 2024 , 2024
Common randomness is an essential resource in many applications. However, a celebrated result of Cleve (STOC 86) rules out the possibility of tossing a fair coin from scratch in the presence of a dishonest majority. A second-best alternative is a Coin Tossing Extension (CTE) protocol, which uses an “online” oracle that produces a small number of common random bits to generate a large number of common random-looking bits. This work initiates the systematic study of fully-secure CTE, which guarantees output even in the presence of malicious behavior. A fully-secure two-party statistical CTE protocol with black-box simulation was implicit in Hofheinz et al. (Eurocrypt 06), but its round complexity is nearly linear in its output length. The problem of constant-round CTE with superlogarithmic stretch remained open. We prove that any statistical CTE with full black-box security and superlogarithmic stretch must have superconstant rounds. To circumvent this impossibility we investigate fully-secure computational CTE, and prove that with N parties and any polynomial stretch:
1. One round suffices for CTE under subexponential LWE, even with Universally Composable security against adaptive corruptions.
2. One-round CTE is implied by DDH or the hidden subgroup assumption in class groups, with a short, reusable Uniform Random String, and by both DCR and QR, with a reusable Structured Reference String.
3. One-way functions imply CTE with O(N) rounds, and thus constant-round CTE for any constant number of parties.
Such results were not known even in the two-party setting with standalone, static security. Furthermore, we extend one-round CTE to sample from any efficient distribution, via strong assumptions that include indistinguishability obfuscation. Our one-round CTE protocols can be interpreted as explainable variants of classical randomness extractors, wherein a (short) seed and a source instance can be efficiently reverse-sampled given a random output. Such explainable extractors may be of independent interest.
- ECSuccinct Homomorphic Secret SharingDamiano Abram , Lawrence Roy , and Peter SchollEUROCRYPT 2024 , 2024
This work introduces homomorphic secret sharing (HSS) with succinct share size. In HSS, private inputs are shared between parties, who can then homomorphically evaluate a function on their shares, obtaining a share of the function output. In succinct HSS, a portion of the inputs from one party can be distributed using shares whose size is sublinear in the number of such inputs. The parties can then locally evaluate a function f on the shares, with the restriction that f must be linear in the succinctly shared inputs. We construct succinct, two-party HSS for branching programs, based on either the decisional composite residuosity assumption, a DDH-like assumption in class groups, or learning with errors with a superpolynomial modulus-to-noise ratio. We then give several applications of succinct HSS, which were only previously known using fully homomorphic encryption, or stronger tools:
1. Succinct vector oblivious linear evaluation (VOLE): Two parties can obtain secret shares of a long, arbitrary vector x, multiplied by a scalar ∆, with communication sublinear in the size of the vector.
2. Batch, multi-party distributed point functions: A protocol for distributing a batch of secret, random point functions among N parties, for any polynomial N, with communication sublinear in the number of DPFs.
3. Sublinear MPC for any number of parties: Two new constructions of MPC with sublinear communication complexity, with N parties for any polynomial N: (a) For general Boolean circuits of size s, with communication O(N s/ log log s), and (b) For layered, sufficiently wide Boolean circuits, with communication O(N s/ log s).
2023
- TCCCryptography from Planted Graphs: Security with Logarithmic-Size MessagesDamiano Abram , Amos Beimel , Yuval Ishai , and 2 more authorsTheory of Cryptography Conference – TCC 2023 , 2023
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.
- CSecurity-Preserving Distributed Samplers: How to Generate any CRS in One Round without Random OraclesDamiano Abram , Brent Waters , and Mark ZhandryCRYPTO 2023 , 2023
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
- CAn Algebraic Framework for Silent Preprocessing with Trustless Setup and Active SecurityDamiano Abram , Ivan Damgård , Claudio Orlandi , and 1 more authorCRYPTO 2022 , 2022
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.
- S&PLow-Bandwidth Threshold ECDSA via Pseudorandom Correlation GeneratorsDamiano Abram , Ariel Nof , Claudio Orlandi , and 2 more authors2022 IEEE Symposium on Security and Privacy , 2022
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.
- ECDistributed (Correlation) Samplers: How to Remove a Trusted Dealer in One RoundDamiano Abram , Peter Scholl , and Sophia YakoubovEUROCRYPT 2022 , 2022
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.
- PKCLow-Communication Multiparty Triple Generation for SPDZ from Ring-LPNDamiano Abram , and Peter SchollPublic-Key Cryptography – PKC 2022 , 2022
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
- CT-RSAOblivious TLS via Multi-party ComputationDamiano Abram , Ivan Damgård , Peter Scholl , and 1 more authorTopics in Cryptology - CT-RSA 2021 - Cryptographers’ Track at the RSA Conference 2021 , 2021
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.
preprints
2025
- ePrintTrapdoor Hash Functions and PIR from Low-Noise LPNDamiano Abram , Giulio Malavolta , and Lawrence Roy2025
Trapdoor hash functions (TDHs) are compressing hash functions, with an additional trapdoor functionality: Given a encoding key for a function f, a hash on x together with a (small) input encoding allow one to recover f(x). TDHs are a versatile tool and a useful building block for more complex cryptographic protocols. In this work, we propose the first TDH construction assuming the (quasi-polynomial) hardness of the LPN problem with noise rate ε= O(log1+βn / n) for β>0, i.e., in the so-called low-noise regime. The construction achieves 2Θ(log1-βλ) compression factor. As an application, we obtain a private-information retrieval (PIR) with communication complexity L / 2Θ(log1-βL), for a database of size L. This is the first PIR scheme with non-trivial communication complexity (asymptotically smaller than L) from any code-based assumption.
2024
- ePrintOn the (Im)possibility of Distributed SamplersDamiano Abram , Serge Fehr , Maciej Obremski , and 1 more author2024
Distributed samplers, recently introduced by Abram, Scholl and Yakoubov (Eurocrypt 2022), are a one-round, multi-party protocol for securely sampling from any distribution. We give new lower and upper bounds for constructing distributed samplers in challenging scenarios. First, we consider the feasibility of distributed samplers with a malicious adversary in the standard model; the only previous construction in this setting relies on a random oracle. We show that for any UC-secure construction in the standard model, even with a CRS, the output of the sampling protocol must have low entropy. This essentially implies that this type of construction is useless in applications. Secondly, we study the question of building distributed samplers in the party-dynamic setting, where parties can join in an ad-hoc manner, and the total number of parties is unbounded. Here, we obtain positive results. First, we build a special type of unbounded universal sampler, which after a trusted setup, allows sampling from any distributed with unbounded size. Our construction is in the shared randomness model, where the parties have access to a shared random string, and uses indistinguishability obfuscation and somewhere statistically binding hashing. Next, using our unbounded universal sampler, we construct distributed universal samplers in the party-dynamic setting. Our first construction satisfies one-time selective security in the shared randomness model. Our second construction is reusable and secure against a malicious adversary in the random oracle model. Finally, we show how to use party-dynamic, distributed universal samplers to produce ideal, correlated randomness in the party-dynamic setting, in a single round of interaction.
- ePrintTime-Based Cryptography From Weaker Assumptions: Randomness Beacons, Delay Functions and MoreDamiano Abram , Lawrence Roy , and Mark Simkin2024
The assumption that certain computations inherently require some sequential time has established itself as a powerful tool for cryptography. It allows for security and liveness guarantees in distributed protocols that are impossible to achieve with classical hardness assumptions. Unfortunately, many constructions from the realm of time-based cryptography are based on new and poorly understood hardness assumptions, which tend not to stand the test of time (cf. Leurent et al. 2023, Peikert & Tang 2023). In this work, we make progress on several fronts. We formally define the concept of a delay function and present a construction thereof from minimal assumptions. We show that these functions, in combination with classical cryptographic objects that satisfy certain efficiency criteria, would allow for constructing delay encryption, which is otherwise only known to exist based on a new hardness assumption about isogenies. We formally define randomness beacons as they are used in the context of blockchains, and we show that (linearly homomorphic) time-lock puzzles allow for efficiently constructing them. Our work puts time-based cryptography on a firmer theoretical footing, provides new constructions from simpler assumptions, and opens new avenues for constructing delay encryption.