As usual in Cryptography, most publications below are in alphabetical order. Contribution ordering is used otherwise, and marked explicitly.
Non Peer-Reviewed Research Items (Under Submission)
-
Edabits Generation with Quasi-Linear Communication Complexity
- Authors: Alexander Bienstock, Daniel Escudero, Qijia Fan, Fengrun Liu and Yifan Song
- ePrint
Abstract
The work of (Escudero et al., CRYPTO 2020) introduces the so-called edabits, which are defined as a secret sharing of an integer over an arithmetic domain, together with its bit decomposition secret shared over a binary domain. In the same work, it is shown how edabits can be used to securely evaluate advanced primitives such as comparison, bit decomposition, and truncation, which are essential building blocks in more complex applications such as privacy-preserving machine learning and beyond. Edabits are general and can be defined over any secret-sharing scheme or corruption model. Such flexibility, coupled with their wide range of applications, makes edabits a powerful target correlation.
Escudero et al. introduced a protocol to generate edabits that works in the arithmetic black-box (ABB) model, that is, it is agnostic to the concrete secret-sharing scheme and even works both for fields and rings , as well as both for honest majority and dishonest majority . Unfortunately, the communication complexity of their approach grows as bits with being the bit-length of an element in the arithmetic domain. This becomes a bottleneck in larger protocols since most MPC primitives such as multiplications or openings can be done with linear communication of bits.
In this work we present a novel approach for generating edabits in the ABB model that achieves quasi-linear communication complexity of bits, for the setting where for a constant . This includes the honest majority case , but also dishonest majority with an (arbitrarily small) constant fraction of honest parties. Our result is achieved via novel applications of randomness extraction methods, as well as better edabit aggregation for the binary components. Along the way and of independent interest, we improve the communication complexity of dabit generation (dabits are bits shared in both binary and arithmetic domains) from bits achieved in (Rotaru and Wood, INDOCRYPT 2019), to linear bits.
-
Kettle: Short Post-Quantum Threshold Signatures from the HAWK Signature Scheme
- Authors: Calvin Abou Haidar, Daniel Escudero, Thomas Espitau, Clément Hoffmann, Kaoru Takemure, Mehdi Tibouchi and Hernán Darío Vanegas Madrigal
- ePrint
Abstract
HAWK is a lattice-based hash-and-sign signature scheme that was a third round candidate in the NIST additional call for post-quantum signatures. It has short signatures and keys, as well as fast and portable signing and verification. However, in response to a highly-publicized AI-driven cryptanalytic result that reduced its security (roughly doubling the required dimension to achieve a given security level), the authors decided to withdraw from the competition. The need to increase parameters was seen as limiting the size advantage of HAWK compared to the already selected lattice schemes ML-DSA and Falcon, which was one of its primary selling points alongside speed and the lack of floating-point arithmetic. In this paper, we identify another attractive aspect of the HAWK design that is not affected by the AI attack and has been overlooked so far: its surprising friendliness to multiparty computation (MPC). Indeed, HAWK signing can be achieved in a generic way from a small collection of basic composable MPC functionalities (like integer multiplication, uniform random generation, etc.) in such a way that instantiating those functionalities using MPC protocols with given security properties (semi-honest vs. malicious, honest vs. dishonest majority, etc.) yields a secure protocol for MPC signing with those same properties. As a result, we obtain Kettle, a UC-secure threshold signature protocol that outputs specification-compliant HAWK signatures and scales to an arbitrary number of parties. It offers essentially the shortest signature size so far for a lattice-based threshold signature, while achieving significantly lower round complexity and online communication cost than other threshold protocols built from pre-existing, non-threshold lattice-based signatures (like ML-DSA and Falcon): as low as 2 online rounds (a dozen rounds total) and 2 kB online communication per party, depending on the specific setting and optimization choices. We also provide a proof-of-concept implementation of our approach in the MP-SPDZ framework, which can be instantiated with any number of parties, any threshold, and a variety of security properties.
-
Scalable Secure Biometric Authentication without Auxiliary Identifiers
- Authors: Alexander Bienstock, Daniel Escudero, Antigoni Polychroniadou, Zhen Zeng, Pranav Bhat, Ashok Singal, Prashant Sharma and Manuela Veloso
- Contribution order
- ePrint
Abstract
The prevalence of biometric authentication has been on the rise due to its ease of use and elimination of weak passwords. To date, most biometric authentication systems have been designed for on-device authentication of the device owner (e.g., smartphones and laptops). Recently, biometric authentication systems have started to emerge that are designed to authenticate users against cloud databases storing representations of biometrics for large numbers of users (potentially millions), such as those facilitating biometric payments. However, the use of a large cloud database introduces a significant attack vector, as a breach of the database could lead to the compromise of all enrolled users’ sensitive biometric data. Indeed, all such existing systems either do not adequately protect against such a breach, or are impractical to deploy and use due to their high computational overhead. In this work, we present a new biometric authentication system that provides provable security guarantees against data breaches, while remaining scalable and performant. To do so, we marry artificial intelligence with advanced cryptographic techniques in a novel fashion, providing several optimizations along the way. Our work is the first to show that real-world scalable privacy-preserving biometric authentication without auxiliary identifiers is feasible, and we believe that it will spur widespread industrial adoption and further research in this area.
Peer-Reviewed Publications
2026
7 papers
-
Merces: Confidential Token Transfers via MPC and CoSNARKs
- Authors: Daniel Escudero, Florian Lugstein, Christian Rechberger, Verena Schröppel and Roman Walch
- CANS 2026
- ePrint
Abstract
Fungible tokens on public blockchains expose all balances and transfer amounts in the clear, which is incompatible with the financial privacy required by many real-world applications. We present Merces a confidential token contract that hides user balances and transaction amounts while preserving on-chain verifiability. The core idea is to store secret shares of balances within a decentralized MPC network, while only commitments are published to a smart contract. Thereby, Merces is capable of translating any existing token (e.g., any ERC20 token) into a confidential version. Deposits, withdrawals, and transfers are computed privately within the MPC network, which generates a collaborative SNARK (CoSNARK) to prove the validity of each state transition. In particular, the proof ensures that on-chain commitments are updated consistently and that the sender has sufficient funds. In this paper we give a full formalization of our construction in the Universal Composability (UC) framework, provide rigorous security proofs, and describe a concrete instantiation using Groth16 over BN254 with Poseidon2-based commitments. We further provide a complete end-to-end implementation, accompanied by extensive benchmarks and discussion of a working demo: our system achieves over 300 transactions per second, including proof generation, while requiring only minimal client-side computation.
-
Covert Attacks on Machine Learning Training in Passively Secure MPC
- Authors: Daniel Escudero, Matthew Jagielski, Rahul Rachuri and Peter Scholl
- EuroS&P 2026
- ePrint
Abstract
Secure multiparty computation (MPC) allows data owners to train machine learning models on combined data while keeping the underlying training data private. The MPC threat model either considers an adversary who passively corrupts some parties without affecting their overall behavior, or an adversary who actively modifies the behavior of corrupt parties. It has been argued that in some settings, active security is not a major concern, partly because of the potential risk of reputation loss if a party is detected cheating.
In this work we show explicit, simple, and effective attacks that an active adversary can run on existing passively secure MPC training protocols, while keeping essentially zero risk of the attack being detected. The attacks we show can compromise both the integrity and privacy of the model, including attacks reconstructing exact training data. Our results challenge the belief that a threat model that does not include malicious behavior by the involved parties may be reasonable in the context of PPML, motivating the use of actively secure protocols for training.
-
Quorus: Efficient, Scalable Threshold ML-DSA Signatures from MPC
- Authors: Alexander Bienstock, Leo de Castro, Daniel Escudero, Antigoni Polychroniadou and Akira Takahashi
- USENIX 2026
- ePrint
Abstract
A threshold signature protocol divides a secret signing key among multiple parties, enabling any subset above a threshold to jointly create a signature. While post-quantum (PQ) threshold signatures are being studied, especially following NIST’s call for threshold schemes, most solutions focus on specially designed, threshold-friendly signature schemes. However, real-world applications like distributed certificate authorities and digital currencies require signatures verifiable under existing standardized procedures. With NIST’s standardization of PQ signatures and ongoing industry deployment, designing an efficient threshold scheme compatible with NIST-standardized verification remains a critical challenge.
In this work, we present the first efficient and scalable solution for multi-party generation of the module-lattice digital signature algorithm (ML-DSA), one of NIST’s PQ signature standards. Our contributions are two-fold. First, we present a variant of the ML-DSA signing algorithm that is amenable to efficient multi-party computation (MPC) and prove that this variant achieves the same security as the original ML-DSA scheme. Second, we present several efficient & scalable MPC protocols to instantiate the threshold signing functionality. Our protocols can produce threshold signatures with as little as 100 KB (per party) of online communication per rejection-sampling round. In addition, we instantiate our protocols in the honest-majority setting, which allows us to avoid any additional public key assumptions.
Our signatures verify under the same ML-DSA implementation for all security levels, with signature and verification key sizes matching ML-DSA; previous lattice-based threshold schemes could not match both of these sizes. Our solution provides the first method for producing threshold post-quantum signatures compatible with NIST-standardized verification, scalable to any number of parties, without new assumptions.
-
for the Price of One: On the Benefits of Using more than Parties in Threshold Signing
- Authors: Daniel Escudero, Yashvanth Kondi, Yifan Song and Hernán Vanegas
- Financial Cryptography 2026
- ePrint
Abstract
In threshold ECDSA a committee of parties holds—say, Shamir—shares of degree of a secret key, where typically for operational purposes (e.g. redundancy to prevent losing the key). At signing time, parties can execute a protocol to produce a signature on a given message without leaking anything about the secret key. In this work we show that if we use parties for signing instead, we can compute signatures without increasing at all the communication costs per party, essentially getting more signatures almost for free in a dishonest majority.
Our result is achieved by making use of packed secret-sharing to distribute multiple secrets with no communication penalty. This introduces several challenges not present in the non-packed domain, which leads us to introduce two primitives that may be of independent interest: we show how to prove that a sharing contains small elements efficiently, and its use in distributing consistent sharings of the same secret modulo two different integers. We also show how to generate degree- preprocessing material with constant communication via an adaptation of the virtual parties idea by Bracha from 1987.
We compare the communication of our protocol to sign messages with respect to the state-of-the-art in -party ECDSA signing by (Doerner et al, S&P'24), which needs to be repeated times. Our results show that, for appropriate regimes of , our protocol can achieve 5x less communication (and even a larger factor) than theirs while adding only a few extra parties for the computation.
-
Thresholdizing Standardized FALCON Signatures
- Authors: Radhika Garg, Daniel Escudero, Antigoni Polychroniadou, Akira Takahahi and Xiao Wang
- CCS 2026
- First author lead
- ePrint
Abstract
Threshold signatures allow a quorum of parties to jointly produce a signature while preventing any smaller subset from doing so. Following NIST’s post-quantum standardization, designing threshold schemes compatible with the newly selected primitives is a pressing task. In particular, no prior threshold signature scheme produces signatures verifiable under the unmodified FALCON verification algorithm - the NIST-selected post-quantum scheme with the smallest signatures and keys.
In this work, we present the first such threshold FALCON signing protocol, establishing its feasibility. Our technical contributions are threefold. First, we adapt the MPC-based discrete Gaussian sampling protocol of Wei et al. [CCS:WYFCW23] to support private centers and standard deviations, as required by FALCON’s signing process. Second, we carry out a Rényi divergence analysis of the Klein sampler under fixed-point arithmetic, showing that bits of precision suffice to achieve the same security as the FALCON specification. Third, we design an efficient MPC protocol for the Klein sampler that exploits the fixed trapdoor basis to construct a pseudorandom correlation generator for authenticated VOLE using only two-party DPFs, reducing per-signature communication significantly over standard authenticated triple generation. We implement and benchmark our protocol in two settings: -party signing with all-but-one corruption, and 3-party signing with honest majority, demonstrating that threshold FALCON signing is feasible for applications where compatibility with the FALCON standard is required.
-
Introduction to secret-sharing based secure multi-party computation in health data
- Authors: Steven Kerr and Daniel Escudero
- BMJ Open 2026
- Contribution order
Abstract
Background Joint analyses across multiple health datasets can increase statistical power and improve the generalisability of research findings. However, limitations on data sharing often prevent researchers from fully realising these benefits. Existing approaches such as federated analytics involve sharing information, which poses challenges due to data governance and security restrictions.
Secure multiparty computation (SMPC) is a set of cryptographic techniques that allows joint analyses across multiple private datasets with zero information sharing except for the agreed outputs. Despite its transformative potential in health research, SMPC has received relatively little attention within the health data landscape.
Objectives This article gives an introduction to secret sharing based SMPC that is accessible with no prior knowledge assumed. We explain how secret sharing techniques work, and the security guarantees they offer. We also discuss SMPC software, and offer our view on the most promising approaches to implementation.
Conclusion SMPC has significant potential for enabling privacy-preserving analyses, and could become a standard tool in the future for collaborative health data research. As efforts to improve data access and integration continue, it will be increasingly important for health data researchers to have an understanding of SMPC so they can use it effectively.
-
Actively Secure MPC with Computation and Communication via CRT
- Authors: Alexander Bienstock, Daniel Escudero and Antigoni Polychroniadou
- CRYPTO 2026
- ePrint
Abstract
Secure multiparty computation (MPC) allows parties to compute a function of their private inputs, so that nothing beyond the output of the function is revealed. In the sub-optimal honest majority setting in which the number of corrupted parties , the works of Goyal et al. (CRYPTO'21 and CRYPTO'22), achieved communication even against active adversaries, but with computation, where is the arithmetic circuit computed by the MPC. Recent work by Garg et al. (CRYPTO'24) showed that both communication and computation can be achieved in this regime, however, only against passive adversaries. In this work, we achieve the best-of-both-worlds by obtaining MPC with communication and computation against active corruption of parties. To do this, we introduce novel techniques for actively-secure MPC constructed from Chinese Remainder Theorem based secret sharing.
2025
6 papers
-
Degree-D Reverse Multiplication-Friendly Embeddings: Constructions and Applications
- Authors: Daniel Escudero, Hongqing Liu, Chaoping Xing and Chen Yuan
- IEEE Transactions on Information Theory 2025 (full version of Asiacrypt 2023)
- ePrint
Abstract
In the recent work of (Cheon & Lee, Eurocrypt'22), the concept of a degree- packing method was formally introduced, which captures the idea of embedding multiple elements of a smaller ring into a larger ring, so that element-wise multiplication in the former is somewhat “compatible” with the product in the latter. Then, several optimal bounds and results are presented, and furthermore, the concept is generalized from one multiplication to degrees larger than two. These packing methods encompass several constructions seen in the literature in contexts like secure multiparty computation and fully homomorphic encryption.
One such construction is the concept of reverse multiplication-friendly embeddings (RMFEs), which are essentially degree-2 packing methods. In this work we generalize the notion of RMFEs to degree- RMFEs which, in spite of being “more algebraic” than packing methods, turn out to be essentially equivalent. Then, we present a general construction of degree- RMFEs by generalizing the ideas on algebraic geometry used to construct traditional degree- RMFEs which, by the aforementioned equivalence, leads to explicit constructions of packing methods. Furthermore, our theory is given in an unified manner for general Galois rings, which include both rings of the form and fields like , which have been treated separately in prior works. We present multiple concrete sets of parameters for degree- RMFEs (including ), which can be useful for future works.
Finally, we apply our RMFEs to the task of non-interactively generating high degree correlations for secure multiparty computation protocols. This requires the use of Shamir secret sharing for a large number of parties, which is known to require large-degree Galois ring extensions. Our RMFE enables the generation of such preprocessing data over small rings, without paying for the multiplicative overhead incurred by using Galois ring extensions of large degree. For our application we also construct along the way, as a side contribution of potential independent interest, a pseudo-random secret-sharing solution for non-interactive generation of packed Shamir-sharings over Galois rings with structured secrets, inspired by the PRSS solutions from (Benhamouda et al, TCC 2021).
-
Towards Scalable YOSO MPC via Packed Secret-Sharing
- Authors: Daniel Escudero, Elisaweta Masserova and Antigoni Polychroniadou
- Asiacrypt 2025
- ePrint
Abstract
The YOSO (You Only Speak Once) model, introduced by Gentry et al. (CRYPTO 2021), helps to achieve strong security guarantees in cryptographic protocols for distributed settings, like blockchains, with large number of parties. YOSO protocols typically employ smaller anonymous committees to execute individual rounds of the protocol instead of having all parties execute the entire protocol. After completing their tasks, parties encrypt protocol messages for the next anonymous committee and erase their internal state before publishing ciphertexts, thereby enhancing security in dynamically changing environments.
In this work, we consider the problem of secure multi-party computation (MPC), a fundamental problem in cryptography and distributed computing. We assume honest majority among the committee members, and work in the online-offline, i.e., preprocessing, setting. In this context, we present the first YOSO MPC protocol where efficiency—measured as communication complexity—improves as the number of parties increases. Specifically, for and an adversary corrupting out of parties, our MPC protocol exhibits enhanced scalability as increases, where the online phase communication becomes independent of . Prior YOSO MPC protocols considered as large as , but a significant hurdle persisted in obtaining YOSO MPC with communication that does not scale linearly with the number of committee members, a challenge that is exagerbated when the committee size was large per YOSO’s requirements. We show that, by considering a small “gap” of , the sizes of the committees are only marginally increased, while online communication is significantly reduced.
Furthermore, we explicitly consider fail-stop adversaries, i.e., honest participants who may inadvertently fail due to reasons such as denial of service or software/hardware errors. In prior YOSO work, these adversaries were grouped with fully malicious parties. Adding explicit support for them allows us to achieve even better scalability.
-
Privacy-Preserving Training of Support Vector Machines via Secure Multiparty Computation
- Authors: Daniel Cabarcas Jaramillo, Hernan Dario Vanegas Madrigal, Daniel Escudero and Fernando Alberto Morales Jauregui
- Transactions on Privacy and Security 2025
- Contribution order
- ACM DL
Abstract
The power and ubiquity of machine learning demand security measures for protecting sensitive data. Secure multiparty computation (MPC) techniques enable a group of parties to jointly compute a given function while keeping the information private. In this work, we engineer a prototype for privately training support vector machines (SVMs) using MPC techniques. We conduct an extensive study on how different approaches for training SVMs interact with existing state-of-the-art MPC protocols. We identify the least squares (LS) approach as the best suited for privately training. We then optimize fixed-point precision, ensuring accuracy while keeping low running time and communication. The technical details of the optimization involve bounds on the step size of a gradient method to solve a linear system, which might be of independent interest. We further propose and analyse different alternatives to improve the LS approach on an MPC implementation, and we compare their performance. The best improvement yields up to 2× reduction of the running time and communication complexity, without affecting the accuracy of the trained model. In order to illustrate the feasibility of our solution, we securely train SVMs for two realistic tasks.
-
EncryptedLLM: Privacy-Preserving Large Language Model Inference via GPU-Accelerated Fully Homomorphic Encryption
- Authors: Leo de Castro, Daniel Escudero, Adya Agrawal, Antigoni Polychroniadou and Manuela Veloso
- ICML 2025
- Contribution order
- OpenReview
Abstract
As large language models (LLMs) become more powerful, the computation required to run these models is increasingly outsourced to a third-party cloud. While this saves clients’ computation, it risks leaking the clients’ LLM queries to the cloud provider. Fully homomorphic encryption (FHE) presents a natural solution to this problem: simply encrypt the query and evaluate the LLM homomorphically on the cloud machine. The result remains encrypted and can only be learned by the client who holds the secret key. In this work, we present a GPU-accelerated implementation of FHE and use this implementation to benchmark an encrypted GPT-2 forward pass, with runtimes over faster than the CPU baseline. We also present novel and extensive experimental analysis of approximations of LLM activation functions to maintain accuracy while achieving this performance.
-
Share the MAYO: thresholdizing MAYO
- Authors: Sofia Celi, Daniel Escudero and Guilhem Niot
- PQ Crypto 2025
- ePrint
Abstract
We present the first comprehensive study on thresholdizing practical OV-based signature schemes, specifically focusing on MAYO and UOV. Our approach begins by addressing the challenges associated with thresholdizing algorithms that sample solutions to linear equation systems of the form , which are fundamental to OV-based signature schemes. Previous attempts have introduced levels of leakage that we deem insecure. We propose a novel minimum-leakage solution and assess its practicality. Furthermore, we explore the thresholdization of the entire functionality of these signature schemes, demonstrating their unique applications in networks and cryptographic protocols.
-
Perfectly Secure Fluid MPC with Abort and Linear Communication Complexity
- Authors: Alexander Bienstock, Daniel Escudero and Antigoni Polychroniadou
- Communications in Cryptology
- ePrint
Abstract
The Fluid multiparty computation (MPC) model, introduced in (Choudhuri et al. CRYPTO 2021), addresses dynamic scenarios where participants can join or leave computations between rounds. Communication complexity initially stood at elements per gate, where is the number of parties in a committee online at a time. This held for both statistical security (honest majority) and computational security (dishonest majority) in (Choudhuri et al. CRYPTO'21) and (Rachuri and Scholl, CRYPTO'22), respectively. The work of Bienstock et al. CRYPTO'23) improved communication to elements per gate. However, it’s important to note that the perfectly secure setting with one-third corruptions per committee has only recently been addressed in the work of (David et al. CRYPTO'23). Notably, their contribution marked a significant advancement in the Fluid MPC literature by introducing guaranteed output delivery. However, this achievement comes at the cost of prohibitively expensive communication, which scales to elements per gate.
In this work, we study the realm of perfectly secure Fluid MPC under one-third active corruptions. Our primary focus lies in proposing efficient protocols that embrace the concept of security with abort. Towards this, we design a protocol for perfectly secure Fluid MPC that requires only linear communication of elements per gate, matching the communication of the non-Fluid setting. Our results show that, as in the case of computational and statistical security, perfect security with abort for Fluid MPC comes “for free (asymptotically linear in ) with respect to traditional non-Fluid MPC, marking a substantial leap forward in large scale dynamic computations, such as Fluid MPC.
2024
7 papers
-
Privacy-Preserving Large Language Model Inference via GPU-Accelerated Fully Homomorphic Encryption
- Authors: Leo de Castro, Antigoni Polychroniadou and Daniel Escudero
- Neurips Safe Generative AI Workshop 2024
- Contribution order
- NeurIPS
Abstract
As large language models (LLMs) become more ubiquitous, security concerns regarding sensitive queries grow. Due to the complexities of deploying these models, LLM evaluation is often outsourced to a third-party cloud, which leaks the clients’ queries to this external provider. These queries could contain sensitive information such as intellectual property, medical information, and proprietary data. Protecting this data while maintaining the LLM’s functionality is a major privacy challenge.
Fully homomorphic encryption (FHE) presents a natural solution to this problem: simply encrypt the query and evaluate the LLM homomorphically on the cloud machine. The result remains encrypted and can only be learned by the client who holds the secret key. There are two barriers to this solution: (1) FHE operations do not easily support the LLM activation functions and (2) FHE implementations remain too slow to evaluate an LLM in a reasonable time. In this work, we address both of these barriers to present a fully encrypted version of GPT-2 with forward pass times over 150× faster than the CPU baseline.
This result builds on two main technical contributions. First, we present the first open-sourced implementation of GPU-accelerated FHE as an extension to the popular OpenFHE library, achieving roughly 200× performance improvement for many critical functions including bootstrapping. Second, we present novel and extensive experimental analysis of approximations of LLM activation functions to maintain accuracy while achieving this performance. We run extensive benchmarks using the HellaSwag, LAMBADA and ARC datasets, and our results show that the accuracy/perplexity degradation with respect to “out-of-the-box” GPT-2 is minimal.
-
Honest Majority GOD MPC with Rounds and Low Online Communication
- Authors: Amit Agarwal, Alexander Bienstock, Ivan Damgård and Daniel Escudero
- Asiacrypt 2024
- ePrint
Abstract
In the context of secure multiparty computation (MPC) protocols with guaranteed output delivery (GOD) for the honest majority setting, the state-of-the-art in terms of communication is the work of (Goyal et al. CRYPTO'20), which communicates O(n|C|) field elements, where |C| is the size of the circuit being computed and n is the number of parties. Their round complexity, as usual in secret-sharing based MPC, is proportional to O(depth(C)), but only in the optimistic case where there is no cheating. Under attack, the number of rounds can increase to Ω(n^2) before honest parties receive output, which is undesired for shallow circuits with depth(C) << n^2. In contrast, other protocols that only require O(depth(C) rounds even in the worst case exist, but the state-of-the-art from (Choudhury and Patra, Transactions on Information Theory, 2017) still requires Ω(n^4|C|) communication in the offline phase, and Ω(n^3|C|) in the online (for both point-to-point and broadcast channels). We see there exists a tension between efficient communication and number of rounds. For reference, the recent work of (Abraham et al., EUROCRYPT'23) shows that for perfect security and t<n/3, protocols with both linear communication and O(depth(C)) rounds exist.
We address this state of affairs by presenting a novel honest majority GOD protocol that maintains O(depth(C)) rounds, even under attack, while improving over the communication of the most efficient protocol in this setting by Choudhury and Patra. More precisely, our protocol has point-to-point (P2P) online communication of O(n|C|), accompanied by O(n|C|) broadcasted (BC) elements, while the offline has O(n^3|C|) P2P communication with O(n^3|C|) BC. This improves over the previous best result, and reduces the tension between communication and round complexity. Our protocol is achieved via a careful use of packed secret-sharing in order to improve the communication of existing verifiable secret-sharing approaches, although at the expense of weakening their robust guarantees: reconstruction of shared values may fail, but only if the adversary gives away the identities of many corrupt parties. We show that this less powerful notion is still useful for MPC, and we use this as a core building block in our construction. Using this weaker VSS, we adapt the recent secure-with-abort Turbopack protocol (Escudero et al. CCS'22) to the GOD setting without significantly sacrificing in efficiency.
-
Perfectly-Secure Multiparty Computation with Linear Communication Complexity over Any Modulus
- Authors: Daniel Escudero, Yifan Song and Wenhao Wang
- Asiacrypt 2024
- ePrint
Abstract
Consider the task of secure multiparty computation (MPC) among parties with perfect security and guaranteed output delivery, supporting active corruptions. Suppose the arithmetic circuit to be computed is defined over a finite ring , for an arbitrary . It is known that this type of MPC over such ring is possible, with communication that scales as , assuming that scales as . However, for constant-size rings where , the communication is actually due to the need of the so-called ring extensions. In most natural settings, the number of parties is variable but the “datatypes” used for the computation are fixed (e.g. 64-bit integers). In this regime, no protocol with linear communication exists. In this work we provide an MPC protocol in this setting: perfect security, G.O.D. and active corruptions, that enjoys linear communication , even for constant-size rings . This includes as important particular cases small fields such as , and also the ring . The main difficulty in achieving this result is that widely used techniques such as linear secret-sharing cannot work over constant-size rings, and instead, one must make use of ring extensions that add overhead, while packing ring elements in each extension element in order to amortize this cost. We make use of reverse multiplication-friendly embeddings (RMFEs) for this packing, and adapt recent techniques in network routing (Goyal et al. CRYPTO'22) to ensure this can be efficiently used for non-SIMD circuits. Unfortunately, doing this naively results in a restriction on the minimum width of the circuit, which leads to an extra additive term in communication of . One of our biggest technical contributions lies in designing novel techniques to overcome this limitation by packing elements that are distributed across different layers. To the best of our knowledge, all works that have a notion of packing (e.g. RMFE or packed secret-sharing) group gates across the same layer, and not doing so, as in our work, leads to a unique set of challenges and complications.
-
On Information-Theoretic Secure Multiparty Computation with Local Repairability
- Authors: Daniel Escudero, Ivan Tjuawinata and Chaoping Xing
- PKC 2024
- ePrint
Abstract
In this work we consider the task of designing information-theoretic MPC protocols for which the state of a given party can be recovered from a small amount of parties, a property we refer to as local repairability. This is useful when considering MPC over dynamic settings where parties leave and join a computation, a scenario that has gained notable attention in recent literature. Thanks to the results of (Cramer et al. EUROCRYPT'00), designing such protocols boils down to constructing a linear secret-sharing scheme (LSSS) with good locality, that is, each share is determined by only a small amount of other shares, that also satisfies the so-called multiplicativity property. Previous constructions that achieve locality (e.g. using locally recoverable codes—LRCs) do not enjoy multiplicativity, and LSSS that are multiplicative (e.g. Shamir’s secret-sharing) do not satisfy locality. Our construction bridges this literature gap by showing the existence of an LSSS that achieves both properties simultaneously.
Our results are obtained by making use of well known connection between error correcting codes and LSSS, in order to adapt the LRC construction by (Tamo & Barg, IEEE Transactions on Information Theory 2014) to turn it into a LSSS. With enough care, such coding-theoretic construction yields our desired locality property, but it falls short at satisfying multiplicativity. In order to address this, we perform an extensive analysis of the privacy properties of our scheme in order to identify parameter regimes where our construction satisfies multiplicativity.
Finally, since our LSSS satisfies locality, every share is determined by a small amount of shares. However, in an MPC context it is not enough to let the (small set of) parties to send their shares to the repaired party, since this may leak more information than the regenerated share. To obtain our final result regarding MPC with local repairability, we construct a lightweight MPC protocol that performs such repairing process without any leakage. We provide both a passively secure construction (for the plain multiplicative regime) and an actively secure one (for strong multiplicativity).
-
Fully Secure MPC and zk-FLIOP Over Rings: New Constructions, Improvements and Extensions
- Authors: Anders Dalskov, Daniel Escudero and Ariel Nof
- CRYPTO 2024
- ePrint
Abstract
We revisit the question of the overhead to achieve full security (i.e., guaranteed output delivery) in secure multiparty computation (MPC). Recent works have closed the gap between full security and semi-honest security, by introducing protocols where the parties first compute the circuit using a semi-honest protocol and then run a verification step with sublinear communication in the circuit size. However, in these works the number of interaction rounds in the verification step is also sublinear in the circuit’s size. Unlike communication, the round complexity of the semi-honest execution typically grows with the circuit’s depth and not its size. Hence, for large but shallow circuits, this additional number of rounds incurs a significant overhead. Motivated by this gap, we make the following contributions:
-
We present a new MPC framework to obtain full security, compatible with effectively any ring, that has an additive communication overhead of only , where is the number of multiplication gates in the circuit, and a constant number of additional rounds beyond the underlying semi-honest protocol. Our framework works with any linear secret sharing scheme and relies on a new to utilize the machinery of zero-knowledge fully linear interactive oracle proofs (zk-FLIOP) in a black-box way. We present several instantiations to the building blocks of our compiler, from which we derive concretely efficient protocols in different settings.
-
We present extensions to the zk-FLIOP primitive for very general settings. The first one is for proving statements over potentially non-commutative rings, where the only requirement is that the ring has a large enough set where (1) every element in the set commutes with every element in the ring, and (2) the difference between any two distinct elements is invertible. Our second zk-FLIOP extension is for proving statements over Galois Rings. For these rings, we present concrete improvements on the current state-of-the-art for the case of constant-round proofs, by making use of Reverse Multiplication Friendly Embeddings (RMFEs).
-
-
Dishonest Majority Multi-Verifier Zero-Knowledge Proofs for Any Constant Fraction of Corrupted Verifiers
- Authors: Daniel Escudero, Antigoni Polychroniadou, Yifan Song and Chenkai Weng
- CCS 2024
- ePrint
Abstract
In this work we study the efficiency of Zero-Knowledge (ZK) arguments of knowledge, particularly exploring Multi-Verifier ZK (MVZK) protocols as a midway point between Non-Interactive ZK and Designated-Verifier ZK, offering versatile applications across various domains. We introduce a new MVZK protocol designed for the preprocessing model, allowing any constant fraction of verifiers to be corrupted, potentially colluding with the prover. Our contributions include the first MVZK over rings. Unlike recent prior works on fields in the dishonest majority case, our protocol demonstrates communication complexity independent of the number of verifiers, contrasting the linear complexity of previous approaches. This key advancement ensures improved scalability and efficiency. We provide an end-to-end implementation of our protocol. The benchmark shows that it achieves a throughput of 1.47 million gates per second for 64 verifiers with corruption, and 0.88 million gates per second with corruption.
-
Sublinear Distributed Product Checks on Replicated Secret-Shared Data over without Ring Extensions
- Authors: Yun Li, Daniel Escudero, Yufei Duan, Zhicong Huang, Cheng Hong, Chao Zhang and Yifan Song
- CCS 2024
- Contribution order, last is lead
- ePrint
Abstract
Multiple works have designed or used maliciously secure honest majority MPC protocols over using replicated secret sharing (e.g. Koti et al. USENIX'21). A recent trend in the design of such MPC protocols is to first execute a semi-honest protocol, and then use a check that verifies the correctness of the computation requiring only sublinear amount of communication in terms of the circuit size. The so-called Galois ring extensions are needed in order to execute such checks over , but these rings incur incredibly high computation overheads, which completely undermine any potential benefits the ring had to begin with.
In this work we revisit the task of designing sublinear distributed product checks on replicated secret-shared data over among three parties with an honest majority. We present a novel technique for verifying the correctness of a set of multiplication (in fact, inner product) triples, involving a sublinear cost in terms of the number of multiplications. Most importantly, unlike previous works, our tools do not rely on Galois ring extensions, which are computationally expensive, and only require computation over rings of the form . In terms of communication, our checks are lighter than existing checks using ring extensions, which is already quite remarkable. However, our most noticeable improvement is in terms of computation: our checks are better than previous approaches, for many parameter regimes of interest. Our experimental results show that checking a 10 million gate circuit with the 3PC protocol from Boyle et al. (CCS'19) takes about two minutes, while our approach takes only 2.82 seconds.
Finally, our techniques are not restricted to the three-party case, and we generalize them to replicated secret-sharing with an arbitrary number of parties . Even though the share size in this scheme grows exponentially with , prior works have used it for or — or even general for feasibility results — and our distributed checks also represent improvements in these contexts.
2023
5 papers
-
Degree-D Reverse Multiplication-Friendly Embeddings: Constructions and Applications
- Authors: Daniel Escudero, Hongqing Liu, Chaoping Xing and Chen Yuan
- Asiacrypt 2023
- ePrint
Abstract
In the recent work of (Cheon & Lee, Eurocrypt'22), the concept of a degree- packing method was formally introduced, which captures the idea of embedding multiple elements of a smaller ring into a larger ring, so that element-wise multiplication in the former is somewhat “compatible” with the product in the latter. Then, several optimal bounds and results are presented, and furthermore, the concept is generalized from one multiplication to degrees larger than two. These packing methods encompass several constructions seen in the literature in contexts like secure multiparty computation and fully homomorphic encryption.
One such construction is the concept of reverse multiplication-friendly embeddings (RMFEs), which are essentially degree-2 packing methods. In this work we generalize the notion of RMFEs to degree- RMFEs which, in spite of being “more algebraic” than packing methods, turn out to be essentially equivalent. Then, we present a general construction of degree- RMFEs by generalizing the ideas on algebraic geometry used to construct traditional degree- RMFEs which, by the aforementioned equivalence, leads to explicit constructions of packing methods. Furthermore, our theory is given in an unified manner for general Galois rings, which include both rings of the form and fields like , which have been treated separately in prior works. We present multiple concrete sets of parameters for degree- RMFEs (including ), which can be useful for future works.
Finally, we apply our RMFEs to the task of non-interactively generating high degree correlations for secure multiparty computation protocols. This requires the use of Shamir secret sharing for a large number of parties, which is known to require large-degree Galois ring extensions. Our RMFE enables the generation of such preprocessing data over small rings, without paying for the multiplicative overhead incurred by using Galois ring extensions of large degree. For our application we also construct along the way, as a side contribution of potential independent interest, a pseudo-random secret-sharing solution for non-interactive generation of packed Shamir-sharings over Galois rings with structured secrets, inspired by the PRSS solutions from (Benhamouda et al, TCC 2021).
-
On Fully-Secure Honest Majority MPC without Round Overhead
- Authors: Daniel Escudero and Serge Fehr
- Latincrypt 2023
- ePrint
Abstract
Fully secure multiparty computation (or guaranteed output delivery) among parties can be achieved with perfect security if the number of corruptions is less than , or with statistical security with the help of a broadcast channel if . In the case of , it is known that it is possible to achieve linear communication complexity, but at a cost of having a round count of in the worst case. The number of rounds can be reduced to by either increasing communication, or assuming some correlated randomness (a setting also known as the preprocesing model). For it is also known that linear communication complexity is achievable, but at the cost of rounds, due to the use of a technique called dispute control. However, in contrast to the setting, it is not known how to reduce this round count for to , neither allowing for larger communication, or by using correlated randomness.
In this work we make progress in this direction by taking the second route above: we present a fully secure protocol for in the preprocessing model, that achieves linear communication complexity, and whose round complexity is only , without the additive term that appears from the use of dispute control. While on the such result requires circuits of width , in our case circuits must be of width , leaving it as an interesting future problem to reduce this gap. Our round count is achieved by avoiding the use of dispute control entirely, relying on a different tool for guaranteeing output. In the setting when correlated randomness is available, this is done by using error correction to reconstruct secret-shared values, but in the case the equivalent is robust secret-sharing, which guarantees the reconstruction of a secret in spite of errors. However, we note that a direct use of such tool would lead to quadratic communication, stemming from the fact that each party needs to authenticate their share towards each other party. At the crux of our techniques lies a novel method for reconstructing a batch of robustly secret-shared values while involving only a linear amount of communication per secret, which may also be of independent interest.
-
SuperPack: Dishonest Majority MPC with Constant Online Communication
- Authors: Daniel Escudero, Vipul Goyal, Antigoni Polychroniadou, Yifan Song and Chenkai Weng
- Eurocrypt 2023
- ePrint
Abstract
In this work we present a novel actively secure dishonest majority MPC protocol, SuperPack, whose efficiency improves as the number of honest parties increases. Concretely, let and consider an adversary that corrupts out of parties. SuperPack requires field elements of online communication per multiplication gate across all parties, assuming circuit-dependent preprocessing, and assuming circuit-independent preprocessing. In contrast, most of the previous works such as SPDZ (Damgård et al, ESORICS 2013) and its derivatives perform the same regardless of whether there is only one honest party or a constant (non-majority) fraction of honest parties. A notable exception is due to Goyal et al (CRYPTO 2022), which achieves field elements assuming circuit-independent preprocessing. Our work improves this result substantially by a factor of at least in the circuit-independent preprocessing model.
Practically, we also compare our work with the best concretely efficient online protocol Turbospeedz (Ben-Efraim et al, ACNS 2019), which achieves field elements per multiplication gate among all parties. Our online protocol improves over Turbospeedz as grows, and as approaches . For example, if there are corruptions (), with our online protocol is better than Turbospeedz and with this factor is , but for corruptions () with our online protocol is better, and for this factor is .
Our circuit-dependent preprocessing can be instantiated from OLE/VOLE. The amount of OLE/VOLE correlations required in our work is a factor of smaller than these required by Le Mans (Rachuri and Scholl, CRYPTO 2022) leveraged to instantiate the preprocessing of Turbospeedz.
Our dishonest majority protocol relies on packed secret-sharing and leverages ideas from the honest majority TurboPack (Escudero et al, CCS 2022) protocol to achieve concrete efficiency for any circuit topology, not only SIMD. We implement both SuperPack and Turbospeedz and verify with experimental results that our approach indeed leads to more competitive runtimes in distributed environments with a moderately large number of parties.
-
Phoenix: Secure Computation in an Unstable Network with Dropouts and Comebacks
- Authors: Ivan Damgård, Daniel Escudero and Antigoni Polychroniadou
- Information-Theoretic Cryptography Conference (ITC) 2023
- ePrint
Abstract
We consider the task of designing secure computation protocols in an unstable network where honest parties can drop out at any time, according to a schedule provided by the adversary. This type of setting, where even honest parties are prone to failures, is more realistic than traditional models, and has therefore gained a lot of attention recently. Our model, Phoenix, enables a new approach to secure multiparty computation with dropouts, allowing parties to drop out and re-enter the computation on an adversarially-chosen schedule and without assuming that these parties receive the messages that were sent to them while being offline - features that are not available in the existing models of Sleepy MPC (Guo et al., CRYPTO ‘19), Fluid MPC (Choudhuri et al., CRYPTO ‘21 ) and YOSO (Gentry et al. CRYPTO ‘21). Phoenix does assume an upper bound on the number of rounds that an honest party can be off-line—otherwise protocols in this setting cannot guarantee termination within a bounded number of rounds; however, if one settles for a weaker notion, namely guaranteed output delivery only for honest parties who stay on-line long enough, this requirement is not necessary.
In this work, we study the settings of perfect, statistical and computational security and design MPC protocols in each of these scenarios. We assume that the intersection of online-and-honest parties from one round to the next is at least , and respectively, where is the number of (actively) corrupt parties. We show the intersection requirements to be optimal. Our (positive) results are obtained in a way that may be of independent interest: we implement a traditional stable network on top of the unstable one, which allows us to plug in any MPC protocol on top. This approach adds a necessary overhead to the round count of the protocols, which is related to the maximal number of rounds an honest party can be offline. We also present a novel, perfectly secure MPC protocol in the preprocessing model that avoids this overhead by following a more “direct” approach rather than first building a stable network and then using existing protocols. We introduce our network model in the UC-framework, show that the composition theorem still holds, and prove the security of our protocols within this setting.
-
On Linear Communication Complexity for (Maximally) Fluid MPC
- Authors: Alexander Bienstock, Daniel Escudero and Antigoni Polychroniadou
- CRYPTO 2023
- ePrint
Abstract
Secure multiparty computation protocols with dynamic parties, which assume that honest parties do not need to be online throughout the whole execution of the protocol, have recently gained a lot of traction for computations of large scale distributed protocols, such as blockchains. More specifically, in Fluid MPC, introduced in (Choudhuri et al. CRYPTO 2021), parties can dynamically join and leave the computation from round to round. The best known Fluid MPC protocol in the honest majority setting communicates elements per gate where is the number of parties online at a time. While Le Mans (Rachuri and Scholl, CRYPTO 2022) extends Fluid MPC to the dishonest majority setting with preprocessing, it still communicates elements per gate.
In this work we present alternative Fluid MPC solutions that require communication per gate for both the information-theoretic honest majority setting and the information-theoretic dishonest majority setting with preprocessing. Our solutions also achieve maximal fluidity where parties only need to be online for a single communication round. Additionally, we show that a protocol in the information-theoretic dishonest majority setting with sub-quadratic overhead per gate requires for each of the parties who may ever participate in the (later) execution phase, preprocessed data per gate.
2022
4 papers
-
Vector Commitments over Rings and Compressed Sigma-Protocols
- Authors: Thomas Attema, Ignacio Cascudo, Ronald Cramer, Ivan Damgård and Daniel Escudero
- TCC 2022
- ePrint
Abstract
Compressed -Protocol Theory (CRYPTO 2020) presents an “alternative” to Bulletproofs that achieves the same communication complexity while adhering more elegantly to existing -protocol theory, which enables their techniques to be directly applicable to other widely used settings in the context of “plug & play” algorithmics. Unfortunately, their techniques are restricted to arithmetic circuits over prime fields, which rules out the possibility of using more machine-friendly moduli such as powers of , which have proven to improve efficiency in applications. In this work we show that such techniques can be generalized to the case of arithmetic circuits modulo any number. This enables the use of powers of , which can prove to be beneficial for efficiency, but it also facilitates the use of other moduli that might prove useful in different applications.
In order to achieve this, we first present an instantiation of the main building block of the theory of compressed -protocols, namely compact vector commitments. Our construction, which may be of independent interest, is homomorphic modulo any positive integer , a result that was not known in the literature before. Second, we generalize the Compressed -Protocol Theory from finite fields to . The main challenge here is ensuring that there are large enough challenge sets as to fulfill the necessary soundness requirements, which is achieved by considering certain ring extensions. Our techniques have application as publicly verifiable zero knowledge proofs of correct computation on homomorphically encrypted data, where for a more flexible parameter instantiation it is useful that the ciphertext space is allowed to be a modular or Galois ring rather than a field: concretely, our protocols can be plugged as a commit-and-proof argument into a recent result on efficient verifiable computation schemes on encrypted data with context-hiding (PKC 21) which exploited this advantage.
-
Fast Fully Secure Multi-Party Computation over Any Ring with Two-Thirds Honest Majority
- Authors: Anders Dalskov, Daniel Escudero and Ariel Nof
- CCS 2022
- ePrint
Abstract
We introduce a new MPC protocol to securely compute any functionality over an arbitrary black-box finite ring (which may not be commutative), tolerating active corruptions while guaranteeing output delivery (G.O.D.). Our protocol is based on replicated secret-sharing, whose share size is known to grow exponentially with the number of parties . However, even though the internal storage and computation in our protocol remains exponential, the communication complexity of our protocol is constant, except for a light constant-round check that is performed at the end before revealing the output.
Furthermore, the amortized communication complexity of our protocol is not only constant, but very small: only ring elements per party, per multiplication gate over two rounds of interaction. This improves over the state-of-the art protocol in the same setting by Furukawa and Lindell (CCS 2019), which has a communication complexity of field elements per party, per multiplication gate and while achieving fairness only. As an alternative, we also describe a variant of our protocol which has only one round of interaction per multiplication gate on average, and amortized communication cost of ring elements per party on average for any natural circuit.
Motivated by the fact that efficiency of distributed protocols are much more penalized by high communication complexity than local computation/storage, we perform a detailed analysis together with experiments in order to explore how large the number of parties can be, before the storage and computation overhead becomes prohibitive. Our results show that our techniques are viable even for a moderate number of parties (e.g., ).
-
TurboPack: Honest Majority MPC with Constant Online Communication
- Authors: Daniel Escudero, Vipul Goyal, Antigoni Polychroniadou and Yifan Song
- CCS 2022
- ePrint
Abstract
We present a novel approach to honest majority secure multiparty computation in the preprocessing model with information theoretic security that achieves the best online communication complexity. The online phase of our protocol requires elements in total per multiplication gate with circuit-dependent preprocessing, or elements in total with circuit-independent preprocessing. Prior works achieved linear online communication complexity in , the number of parties, with the best prior existing solution involving elements per multiplication gate. Only one recent work (Goyal et al, CRYPTO'22) achieves constant online communication complexity, but the constants are large ( elements for passive security, and twice that for active security). That said, our protocol offers a very efficient information theoretic online phase for any number of parties.
The total end-to-end communication cost with the preprocessing phase is linear in , i.e., , which is larger than the complexity of the state-of-the-art protocols. The gap is not significant when the online phase must be optimized as a priority and a reasonably large number of parties is involved. Unlike previous works based on packed secret-sharing to reduce communication complexity, we further reduce the communication by avoiding the use of complex and expensive network routing or permutations tools. Furthermore, we also allow for a maximal honest majority adversary, while most previous works require the set of honest parties to be strictly larger than a majority.
Our protocol is simple and offers concrete efficiency. To illustrate this we present a full-fledged implementation together with experimental results that show improvements in online phase runtimes that go up to in certain settings (e.g. parties, LAN network, circuit of depth with M gates).
-
More Efficient Dishonest Majority Secure Computation over via Galois Rings
- Authors: Daniel Escudero, Chaoping Xing, Chen Yuan
- CRYPTO 2022
- ePrint
Abstract
In this work we present a novel actively secure multiparty computation protocol in the dishonest majority setting, where the computation domain is a ring of the type . Instead of considering an “extension ring” of the form as in SPD (Cramer et al, CRYPTO 2018) and its derivatives, we make use of an actual ring extension, or more precisely, a Galois ring extension of large enough degree, in order to ensure that the adversary cannot cheat except with negligible probability. These techniques have been used already in the context of honest majority MPC over , and to the best of our knowledge, our work constitutes the first study of the benefits of these tools in the dishonest majority setting.
Making use of Galois ring extensions requires great care in order to avoid paying an extra overhead due to the use of larger rings. To address this, reverse multiplication-friendly embeddings (RMFEs) have been used in the honest majority setting (e.g. Cascudo et al, CRYPTO 2018), and more recently in the dishonest majority setting for computation over (Cascudo and Gundersen, TCC 2020). We make use of the recent RMFEs over from (Cramer et al, CRYPTO 2021), together with adaptations of some RMFE optimizations introduced in (Abspoel et al, ASIACRYPT 2021) in the honest majority setting, to achieve an efficient protocol that only requires in its online phase bits of amortized communication complexity and one round of communication for each multiplication gate. We also instantiate the necessary offline phase using Oblivious Linear Evaluation (OLE) by generalizing the approach based on Oblivious Transfer (OT) proposed in MASCOT (Keller et al, CCS 2016). To this end, and as an additional contribution of potential independent interest, we present a novel technique using Multiplication-Friendly Embeddings (MFEs) to achieve OLE over Galois ring extensions using black-box access to an OLE protocol over the base ring without paying a quadratic cost in terms of the extension degree. This generalizes the approach in MASCOT based on Correlated OT Extension. Finally, along the way we also identify a bug in a central proof in MASCOT, and we implicitly present a fix in our generalized proof.
2021
8 papers
- Improved Single-Round Secure Multiplication Using Regenerating Codes
- Authors: Mark Abspoel, Ronald Cramer, Daniel Escudero, Ivan Damgård and Chaoping Xing
- Asiacrypt 2021
- ePrint
Abstract
In 2016, Guruswami and Wootters showed Shamir’s secret-sharing scheme defined over an extension field has a regenerating property. Namely, we can compress each share to an element of the base field by applying a linear form, such that the secret is determined by a linear combination of the compressed shares. Immediately it seemed like an application to improve the complexity of unconditionally secure multiparty computation must be imminent; however, thus far, no result has been published.
We present the first application of regenerating codes to MPC, and show that its utility lies in reducing the number of rounds. Concretely, we present a protocol that obliviously evaluates a depth- arithmetic circuit in rounds, in the amortized setting of parallel evaluations, with ring elements communicated per multiplication. Our protocol is secure against the maximal adversary corrupting parties. All existing approaches in this setting have complexity .
Moreover, we extend some of the theory on regenerating codes to Galois rings. It was already known that the repair property of MDS codes over fields can be fully characterized in terms of its dual code. We show this characterization extends to linear codes over Galois rings, and use it to show the result of Guruswami and Wootters also holds true for Shamir’s scheme over Galois rings.
- Information-Theoretically Secure MPC against Mixed Dynamic Adversaries
- Authors: Ivan Damgård, Daniel Escudero, Divya Ravi
- TCC 2021
- ePrint
Abstract
In this work we consider information-theoretically secure MPC against a mixed adversary who can corrupt parties passively, parties actively, and can make parties fail-stop. With perfect security, it is known that every function can be computed securely if and only if , and for statistical security the bound is .
These results say that for each given set of parameters respecting the inequality, there exists a protocol secure against this particular choice of corruption thresholds. In this work we consider a dynamic adversary. Here, the goal is a single protocol that is secure, no matter which set of corruption thresholds from a certain class is chosen by the adversary. A dynamic adversary can choose a corruption strategy after seeing the protocol and so is much stronger than a standard adversary.
Dynamically secure protocols have been considered before for computational security. Also the information theoretic case has been studied, but only considering non-threshold general adversaries, leading to inefficient protocols.
We consider threshold dynamic adversaries and information theoretic security. For statistical security we show that efficient dynamic secure function evaluation (SFE) is possible if and only if , but any dynamically secure protocol must use rounds, even if only fairness is required. Further, general reactive MPC is possible if we assume in addition that , but fair reactive MPC only requires .
For perfect security we show that both dynamic SFE and verifiable secret sharing (VSS) are impossible if we only assume and remain impossible even if we also assume . On the other hand, perfect dynamic SFE with guaranteed output delivery (G.O.D.) is possible when either or i.e. if instead we assume or . Further, perfect dynamic VSS with G.O.D. is possible under the additional conditions or . These conditions are also sufficient for dynamic perfect reactive MPC.
- Improved Threshold Signatures, Proactive Secret Sharing, and Input Certification from LSS Isomorphisms
- Authors: Diego F. Aranha, Anders Dalskov, Daniel Escudero and Claudio Orlandi
- Latincrypt 2021
- ePrint
Abstract
In this paper we present a series of applications steming from a formal treatment of linear secret-sharing isomorphisms, which are linear transformations between different secret-sharing schemes defined over vector spaces over a field and allow for efficient multiparty conversion from one secret-sharing scheme to the other. This concept generalizes the folklore idea that moving from a secret-sharing scheme over to a secret sharing “in the exponent” can be done non-interactively by multiplying the share unto a generator of e.g., an elliptic curve group. We generalize this idea and show that it can also be used to compute arbitrary bilinear maps and in particular pairings over elliptic curves.
We include the following practical applications originating from our framework: First we show how to securely realize the Pointcheval-Sanders signature scheme (CT-RSA 2016) in MPC. Second we present a construction for dynamic proactive secret-sharing which outperforms the current state of the art from CCS 2019. Third we present a construction for MPC input certification using digital signatures that we show experimentally to outperform the previous best solution in this area.
- Honest Majority MPC with Abort with Minimal Online Communication
- Authors: Anders Dalskov and Daniel Escudero
- Latincrypt 2021
- ePrint
Abstract
In this work we focus on improving the communication complexity of the online phase of honest majority MPC protocols. To this end, we present a general and simple method to compile arbitrary secret-sharing-based passively secure protocols defined over an arbitrary ring that are secure up to additive attacks in a malicious setting, to actively secure protocols with abort. The resulting protocol has a total communication complexity in the online phase of shares, which amounts to shares per party asymptotically. An important aspect of our techniques is that they can be seen as generalization of ideas that have been used in other works in a rather ad-hoc manner for different secret-sharing protocols. Thus, our work serves as a way of unifying key ideas in recent honest majority protocols, to understand better the core techniques and similarities among these works. Furthermore, for , when instantiated with replicated secret-sharing-based protocols (Araki et al. CCS 2016), the communication complexity in the online phase amounts to only ring element per party, matching the communication complexity of the BLAZE protocol (Patra & Suresh, NDSS 2020), while having a much simpler design.
- Efficient Information-Theoretic Multi-Party Computation over Non-Commutative Rings
- Authors: Daniel Escudero and Eduardo Soria-Vazquez
- CRYPTO 2021
- ePrint
Abstract
We construct the first efficient MPC protocol that only requires black-box access to a non-commutative ring . Previous results in the same setting were efficient only either for a constant number of corruptions or when computing branching programs and formulas. Our techniques are based on a generalization of Shamir’s secret sharing to non-commutative rings, which we derive from the work on Reed Solomon codes by Quintin, Barbier and Chabot (IEEE Transactions on Information Theory, 2013). When the center of the ring contains a set such that , the resulting secret sharing scheme is strongly multiplicative and we can generalize existing constructions over finite fields without much trouble.
Most of our work is devoted to the case where the elements of do not commute with all of , but they just commute with each other. For such rings, the secret sharing scheme cannot be linear “on both sides” and furthermore it is not multiplicative. Nevertheless, we are still able to build MPC protocols with a concretely efficient online phase and black-box access to . As an example we consider the ring , for which when , we obtain protocols that require around less communication and less computation than the state of the art protocol based on Circuit Amortization Friendly Encodings (Dalskov, Lee and Soria-Vazquez, ASIACRYPT 2020).
In this setting with a “less commutative” , our black-box preprocessing phase has a less practical complexity of . Due to this, we additionally provide specialized, concretely efficient preprocessing protocols for that exploit the structure of the matrix ring.
- Fantastic Four: Honest-Majority Four-Party Secure Computation With Malicious Security
- Authors: Anders Dalskov, Daniel Escudero and Marcel Keller
- USENIX 2021
- ePrint
Abstract
In this work we introduce a novel four-party honest-majority MPC protocol with active security that achieves comparable efficiency to equivalent protocols in the same setting, while having a much simpler design and not relying on function-dependent preprocessing. Our initial protocol satisfies security with abort, but we present some extensions to achieve guaranteed output delivery. Unlike previous works, we do not achieve this by delegating the computation to one single party that is identified to be honest, which is likely to hinder the adoption of these technologies as it centralizes sensitive data. Instead, our novel approach guarantees termination of the protocol while ensuring that no single party (honest or corrupt) learns anything beyond the output.
We implement our four-party protocol with abort in the MP-SPDZ framework for multiparty computation and benchmark multiple applications like MNIST classification training and ImageNet inference. Our results show that our four-party protocol performs similarly to an efficient honest-majority three-party protocol that only provides semi-honest/passive security, which suggest that adding a fourth party can be an effective method to achieve active security without harming performance.
- Secure Training of Decision Trees with Continuous Attributes
- Authors: Mark Abspoel, Daniel Escudero, Nikolaj Volgushev
- PoPETs 2021
- ePrint
Abstract
We apply multiparty computation (MPC) techniques to show, given a database that is secret-shared among multiple mutually distrustful parties, how the parties may obliviously construct a decision tree based on the secret data. We consider data with continuous attributes (i.e., coming from a large domain), and develop a secure version of a learning algorithm similar to the C4.5 or CART algorithms. Previous MPC-based work only focused on decision tree learning with discrete attributes (De Hoogh et al. 2014).
Our starting point is to apply an existing generic MPC protocol to a standard decision tree learning algorithm, which we then optimize in several ways. We exploit the fact that even if we allow the data to have continuous values, which a priori might require fixed or floating point representations, the output of the tree learning algorithm only depends on the relative ordering of the data. By obliviously sorting the data we reduce the number of comparisons needed per node to from the naive , where is the number of training records in the dataset, thus making the algorithm feasible for larger datasets. This does however introduce a problem when duplicate values occur in the dataset, but we manage to overcome this problem with a relatively cheap subprotocol. We show a procedure to convert a sorting network into a permutation network of smaller complexity, resulting in a round complexity of per layer in the tree.
We implement our algorithm in the MP-SPDZ framework and benchmark our implementation for both passive and active three-party computation using arithmetic modulo . We apply our implementation to a large scale medical dataset of rows using random forests, and thus demonstrate practical feasibility of using MPC for privacy-preserving machine learning based on decision trees for large datasets.
- An Efficient Passive-to-Active Compiler for Honest-Majority MPC over Rings
- Authors: Mark Abspoel, Anders Dalskov, Daniel Escudero and Ariel Nof
- ACNS 2021
- ePrint
Abstract
Multiparty computation (MPC) over rings such as or has received a great deal of attention recently due to its ease of implementation and attractive performance. Several actively secure protocols over these rings have been implemented, for both the dishonest majority setting and the setting of three parties with one corruption. However, in the honest majority setting, no concretely efficient protocol for arithmetic computation over rings has yet been proposed that allows for an arbitrary number of parties.
We present a novel compiler for MPC over the ring in the honest majority setting that turns a semi-honest protocol into an actively secure protocol with very little overhead. The communication cost per multiplication is only twice that of the semi-honest protocol, making the resultant actively secure protocol almost as fast.
To demonstrate the efficiency of our compiler, we implement both an optimized 3-party variant (based on replicated secret-sharing), as well as a protocol for parties (based on a recent protocol from TCC 2019). For the 3-party variant, we obtain a protocol which outperforms the previous state of the art that we can experimentally compare against. Our -party variant is the first implementation for this particular setting, and we show that it performs comparably to the current state of the art over fields.
2020
4 papers
-
Secure Evaluation of Quantized Neural Networks
- Authors: Anders Dalskov, Daniel Escudero and Marcel Keller.
- PoPETs 2020
- ePrint
Abstract
We investigate two questions in this paper: First, we ask to what extent “MPC friendly” models are already supported by major Machine Learning frameworks such as TensorFlow or PyTorch. Prior works provide protocols that only work on fixed-point integers and specialized activation functions, two aspects that are not supported by popular Machine Learning frameworks, and the need for these specialized model representations means that it is hard, and often impossible, to use e.g., TensorFlow to design, train and test models that later have to be evaluated securely. Second, we ask to what extent the functionality for evaluating Neural Networks already exists in general-purpose MPC frameworks. These frameworks have received more scrutiny, are better documented and supported on more platforms. Furthermore, they are typically flexible in terms of the threat model they support. In contrast, most secure evaluation protocols in the literature are targeted to a specific threat model and their implementations are only a “proof-of-concept”, making it very hard for their adoption in practice. We answer both of the above questions in a positive way: We observe that the quantization techniques supported by both TensorFlow, PyTorch and MXNet can provide models in a representation that can be evaluated securely; and moreover, that this evaluation can be performed by a general purpose MPC framework. We perform extensive benchmarks to understand the exact trade-offs between different corruption models, network sizes and efficiency. These experiments provide an interesting insight into cost between active and passive security, as well as honest and dishonest majority. Our work shows then that the separating line between existing ML frameworks and existing MPC protocols may be narrower than implicitly suggested by previous works.
-
Improved Primitives for MPC over Mixed Arithmetic-Binary Circuits
- Authors: Daniel Escudero, Satrajit Ghosh, Marcel Keller, Rahul Rachuri, Peter Scholl
- CRYPTO 2020
- ePrint
Abstract
This work introduces novel techniques to improve the translation between arithmetic and binary data types in secure multi-party computation. We introduce a new approach to performing these conversions using what we call extended doubly-authenticated bits (edaBits), which correspond to shared integers in the arithmetic domain whose bit decomposition is shared in the binary domain. These can be used to considerably increase the efficiency of non-linear operations such as truncation, secure comparison and bit-decomposition.
Our edaBits are similar to the daBits technique introduced by Rotaru et al. (Indocrypt 2019). However, we show that edaBits can be directly produced much more efficiently than daBits, with active security, while enabling the same benefits in higher-level applications. Our method for generating edaBits involves a novel cut-and-choose technique that may be of independent interest, and improves efficiency by exploiting natural, tamper-resilient properties of binary circuits that occur in our construction. We also show how edaBits can be applied to efficiently implement various non-linear protocols of interest, and we thoroughly analyze their correctness for both signed and unsigned integers.
The results of this work can be applied to any corruption threshold, although they seem best suited to dishonest majority protocols such as SPDZ. We implement and benchmark our constructions, and experimentally verify that our technique yield a substantial increase in efficiency. EdaBits save in communication by a factor that lies between and for secure comparisons with respect to a purely arithmetic approach, and between 2 and 25 with respect to using daBits. Improvements in throughput per second are slightly lower but still as high as a factor of 47. We also apply our novel machinery to the tasks of biometric matching and convolutional neural networks, obtaining a noticeable improvement as well.
-
Efficient Protocols for Oblivious Linear Function Evaluation from Ring-LWE
- Authors: Carsten Baum, Daniel Escudero, Alberto Pedrouzo-Ulloa, Peter Scholl, Juan Ramón Troncoso-Pastoriza
- SCN 2020
- ePrint
Abstract
An oblivious linear function evaluation protocol, or OLE, is a two-party protocol for the function , where a sender inputs the field elements , and a receiver inputs and learns . OLE can be used to build secret-shared multiplication, and is an essential component of many secure computation applications including general-purpose multi-party computation, private set intersection and more.
In this work, we present several efficient OLE protocols from the ring learning with errors (RLWE) assumption. Technically, we build two new passively secure protocols, which build upon recent advances in homomorphic secret sharing from (R)LWE (Boyle et al., Eurocrypt 2019), with optimizations tailored to the setting of OLE. We upgrade these to active security using efficient amortized zero-knowledge techniques for lattice relations (Baum et al., Crypto 2018), and design new variants of zero-knowledge arguments that are necessary for some of our constructions.
Our protocols offer several advantages over existing constructions. Firstly, they have the lowest communication complexity amongst previous, practical protocols from RLWE and other assumptions; secondly, they are conceptually very simple, and have just one round of interaction for the case of OLE where is randomly chosen. We demonstrate this with an implementation of one of our passively secure protocols, which can perform more than 1 million OLEs per second over the ring , for a 120-bit modulus , on standard hardware.
-
Asymptotically Good Multiplicative LSSS over Galois Rings and Applications to MPC over
- Authors: Mark Abspoel, Ronald Cramer, Ivan Damgård, Daniel Escudero, Matthieu Rambaud, Chaoping Xing and Chen Yuan
- Asiacrypt 2020
- ePrint
Abstract
We study information-theoretic multiparty computation (MPC) protocols over rings that have good asymptotic communication complexity for a large number of players. An important ingredient for such protocols is arithmetic secret sharing, i.e., linear secret-sharing schemes with multiplicative properties. The standard way to obtain these over fields is with a family of linear codes , such that , and are asymptotically good (strongly multiplicative). For our purposes here it suffices if the square code is not the whole space, i.e., has codimension at least 1 (multiplicative).
Our approach is to lift such a family of codes defined over a finite field to a Galois ring, which is a local ring that has as its residue field and that contains as a subring, and thus enables arithmetic that is compatible with both structures. Although arbitrary lifts preserve the distance and dual distance of a code, as we demonstrate with a counterexample, the multiplicative property is not preserved. We work around this issue by showing a dedicated lift that preserves self-orthogonality (as well as distance and dual distance), for . Self-orthogonal codes are multiplicative, therefore we can use existing results of asymptotically good self-dual codes over fields to obtain arithmetic secret sharing over Galois rings. For we obtain multiplicativity by using existing techniques of secret-sharing using both and , incurring a constant overhead. As a result, we obtain asymptotically good arithmetic secret-sharing schemes over Galois rings.
With these schemes in hand, we extend existing field-based MPC protocols to obtain MPC over , in the setting of a submaximal adversary corrupting less than a fraction of the players, where is arbitrarily small. We consider 3 different corruption models. For passive and active security with abort, our protocols communicate bits per multiplication. For full security with guaranteed output delivery we use a preprocessing model and get bits per multiplication in the online phase and bits per multiplication in the offline phase. Thus, we obtain true linear bit complexities, without the common assumption that the ring size depends on the number of players.
2019
2 papers
-
New Primitives for Actively-Secure MPC over Rings with Applications to Private Machine Learning
- Authors: Ivan Damgård, Daniel Escudero, Tore Kasper Frederiksen, Marcel Keller, Peter Scholl, Nikolaj Volgushev.
- S&P 2019
- ePrint
Abstract
At CRYPTO 2018 Cramer et al. presented SPDZ2k, a new secret-sharing based protocol for actively secure multi-party computation against a dishonest majority, that works over rings instead of fields. Their protocol uses slightly more communication than competitive schemes working over fields. However, their approach allows for arithmetic to be carried out using native 32 or 64-bit CPU operations rather than modulo a large prime. The authors thus conjectured that the increased communication would be more than made up for by the increased efficiency of implementations.
In this work we answer their conjecture in the affirmative. We do so by implementing their scheme, and designing and implementing new efficient protocols for equality test, comparison, and truncation over rings. We further show that these operations find application in the machine learning domain, and indeed significantly outperform their field-based competitors. In particular, we implement and benchmark oblivious algorithms for decision tree and support vector machine (SVM) evaluation.
-
Efficient Information-Theoretic Secure Multiparty Computation over via Galois Rings
- Authors: Mark Abspoel, Ronald Cramer, Ivan Damgård, Daniel Escudero, Chen Yuan:
- TCC 2019
- ePrint
Abstract
At CRYPTO 2018, Cramer et al. introduced a secret-sharing based protocol called SPD that allows for secure multiparty computation (MPC) in the dishonest majority setting over the ring of integers modulo , thus solving a long-standing open question in MPC about secure computation over rings in this setting. In this paper we study this problem in the information-theoretic scenario. More specifically, we ask the following question: Can we obtain information-theoretic MPC protocols that work over rings with comparable efficiency to corresponding protocols over fields? We answer this question in the affirmative by presenting an efficient protocol for robust Secure Multiparty Computation over (for any prime and positive integer ) that is perfectly secure against active adversaries corrupting a fraction of at most players, and a robust protocol that is statistically secure against an active adversary corrupting a fraction of at most players.
2018
2 papers
-
SPDZ: Efficient MPC mod for Dishonest Majority
- Authors: Ronald Cramer, Ivan Damgård, Daniel Escudero, Peter Scholl, Chaoping Xing.
- CRYPTO 2018
- ePrint
Abstract
Most multi-party computation protocols allow secure computation of arithmetic circuits over a finite field, such as the integers modulo a prime. In the more natural setting of integer computations modulo , which are useful for simplifying implementations and applications, no solutions with active security are known unless the majority of the participants are honest.
We present a new scheme for information-theoretic MACs that are homomorphic modulo , and are as efficient as the well-known standard solutions that are homomorphic over fields. We apply this to construct an MPC protocol for dishonest majority in the preprocessing model that has efficiency comparable to the well-known SPDZ protocol (Damgård et al., CRYPTO 2012), with operations modulo instead of over a field. We also construct a matching preprocessing protocol based on oblivious transfer, which is in the style of the MASCOT protocol (Keller et al., CCS 2016) and almost as efficient.
-
Rank Analysis of Cubic Multivariate Cryptosystems
- Authors: John B. Baena, Daniel Cabarcas, Daniel E. Escudero, Karan Khathuria, and Javier A. Verbel.
- PQCrypto 2018
- ePrint
Abstract
In this work we analyze the security of cubic cryptographic constructions with respect to rank weakness. We detail how to extend the big field idea from quadratic to cubic, and show that the same rank defect occurs. We extend the min-rank problem and propose an algorithm to solve it in this setting. We show that for fixed small rank, the complexity is even lower than for the quadratic case. However, the rank of a cubic polynomial in variables can be larger than , and in this case the algorithm is very inefficient. We show that the rank of the differential is not necessarily smaller, rendering this line of attack useless if the rank is large enough. Similarly, the algebraic attack is exponential in the rank, thus useless for high rank.
2016
1 paper
- Efficient ZHFE Key Generation
- Authors: John B. Baena, Daniel Cabarcas, Daniel E. Escudero, Jaiberth Porras- Barrera, and Javier A. Verbel.
- PQCrypto 2016
- Springer
Abstract
In this paper we present a new algorithm to construct the keys of the multivariate public key encryption scheme ZHFE. Constructing ZHFE’s trapdoor involves finding a low degree polynomial of q-Hamming-weight-three, as an aid to invert a pair of q-Hamming-weight-two polynomials of high degree and high rank. This is done by solving a large sparse linear system of equations. We unveil the combinatorial structure of the system in order to reveal the hidden structure of the matrix associated with it. When the system’s variables and equations are organized accordingly, an almost block diagonal shape emerges. We then exploit this shape to solve the system much faster than when ZHFE was first proposed. The paper presents the theoretical details explaining the structure of the matrix. We also present experimental data that confirms the notable improvement of the key generation complexity, which makes ZHFE more suitable for practical implementations.
Theses
PhD (2021)
- Multiparty Computation over
- PhD thesis, supervised by Prof. Ivan Damgård
- PDF (source code)
Master (2018)
- Cubic Multivariate Cryptosystems based on Big Field Constructions and their Vulnerability to a Min-Rank Attack
- Master thesis, supervised by Prof. Daniel Cabarcas Jaramillo.
- PDF (source code)
Undergraduate (2016)
- Groebner Bases and Applications to the Security of Multivariate Public Key Cryptosystems
- Bachelor’s thesis, supervised by Prof. Daniel Cabarcas Jaramillo.
- PDF (source code)