Motivated by applications to efficient secure computation, we consider the following problem of encrypted matrix-vector product (EMVP). Let ⅇ be a finite field. In an offline phase, a client uploads an encryption of a matrix M∈ ⅇmxℓ to a server, keeping only a short secret key. The server stores the encrypted matrix M. In the online phase, the client may repeatedly send encryptions qi of query vectors qi∈ ⅇℓ, which enables the client and the server to locally compute compact shares of the matrix-vector product M qi. The server learns nothing about M or qi. The shared output can either be revealed to the client or processed by another protocol.

We propose plausible post-quantum (PQ) oblivious pseudorandom functions (OPRFs) based on the Power-Residue PRF (Damgård CRYPTO'88), a generalization of the Legendre PRF. For security parameter$\lambda$, we consider the PRF Gold$k(x)$that maps an integer$x$modulo a public prime$p=2^{\lambda}\cdot g+1$to the element$(k+x)^{g}\text{mod}\ p$, where$g$is public and$\log g\approx 2\lambda$. At the core of our constructions are efficient novel methods for evaluating Gold within two-party computation (2PC-Gold), achieving different security requirements. Here, the server$\mathcal{P}_{s}$holds the PRF key$k$whereas the client$\mathcal{P}_{c}$holds the PRF input$x$, and they jointly evaluate Gold in$2\mathbf{PC}$. 2 PC-Gold uses standard Vector Oblivious Linear Evaluation (VOLE) correlations and is information-theoretic and constant-round in the (V)OLE-hybrid model. We show: •For a semi-honest$\mathcal{P}_{s}$and a malicious$\mathcal{P}_{c}$: a 2PC-Gold that just uses a single (V)OLE correlation, and has a communication complexity of 3 field elements (2 field elements if we only require a uniformly sampled key) and a computational complexity of$\mathcal{O}(\lambda)$field operations. We refer to this as half-malicious security. •For malicious$\mathcal{P}_{s}$and$\mathcal{P}_{c}$: a 2PC-Gold that just uses$\frac{\lambda}{4}+\mathcal{O}(1)$VOLE correlations, and has a communication complexity of$\frac{\lambda}{4}+\mathcal{O}(1)$field elements and a computational complexity of$\mathcal{O}(\lambda)$field operations. These constructions support additional features and extensions, e.g., batched evaluations with better amortized costs where$\mathcal{P}_{c}$repeatedly evaluates the PRF under the same key. Furthermore, we extend 2PC-Gold to Verifiable OPRFs and use the methodology from Beullens et al. (Eurocrypt'25) to get strong OPRF security in the universally composable setting. All the protocols are efficient in practice. We implemented 2PC-Gold-with (PQ) VOLEs-and benchmarked them. For example, our half-malicious (resp. malicious) n-batched PQ OPRFs incur about 100B (resp. 1.9KB) of amortized communication for$\lambda=128$.

The Algorand consensus protocol is interesting both in theory and in practice. On the theoretical side, to achieve adaptive security, it introduces the novel idea of player replaceability, where each step of the protocol is executed by a different randomly selected committee whose members remain secret until they send their first and only message. The protocol provides consistency under arbitrary network conditions and liveness under intermittent network partitions. On the practical side, the protocol is used to secure the Algorand cryptocurrency, whose total value is approximately 850M at the time of writing.

This paper introduces Flamingo, a system for secure aggregation of data across a large set of clients. In secure aggregation, a server sums up the private inputs of clients and obtains the result without learning anything about the individual inputs beyond what is implied by the final sum. Flamingo focuses on the multi-round setting found in federated learning in which many consecutive summations (averages) of model weights are performed to derive a good model. Previous protocols, such as Bell et al. (CCS ’20), have been designed for a single round and are adapted to the federated learning setting by repeating the protocol multiple times. Flamingo eliminates the need for the per-round setup of previous protocols, and has a new lightweight dropout resilience protocol to ensure that if clients leave in the middle of a sum the server can still obtain a meaningful result. Furthermore, Flamingo introduces a new way to locally choose the so-called client neighborhood introduced by Bell et al. These techniques help Flamingo reduce the number of interactions between clients and the server, resulting in a significant reduction in the end-to-end runtime for a full training session over prior work.We implement and evaluate Flamingo and show that it can securely train a neural network on the (Extended) MNIST and CIFAR-100 datasets, and the model converges without a loss in accuracy, compared to a non-private federated learning system.

Nakamoto introduced a mechanism for leader election via proof of work, and allowed this dealer to speak once. In this setting parties do not have inputs and they output a value which they calculated. Jing and Micali took this idea a step further and showed that Byzantine agreement, a function where parties have inputs but no private information, can be reached in a setting where each party speaks only once. This was achieved by introducing the notion of player replaceability. In our recent works we have shown that any function, including those where parties have secret inputs, can be computed in the YOSO (you only speak once) model.

We consider large deployments of threshold cryptographic services that can run in traditional multi-server settings and, at a much larger scale, in blockchain environments. We present a set of techniques that improve performance and meet the requirements of settings with large number of servers and high rate of threshold operations. More fundamentally, our techniques enable threshold cryptographic applications to run in more challenging decentralized permissionless systems, such as contemporary blockchains. In particular, we design and implement a novel threshold solution for the recently introduced YOSO (You Only Speak Once) model. The model builds on ever changing, unpredictable committees that perform ephemeral roles in a way that evades targeting by attackers and enables virtually unlimited scalability in very large networks. Our solution allows for the maintenance of system-wide keys that can be generated, used and proactivized as needed. The specific techniques build on optimized protocols for multi-secret multi-dealer verifiable secret sharing and their adaptation to the YOSO model.

Existing models for non-interactive MPC cannot provide full privacy for inputs, because they inherently leak the residual function (i.e., the output of the function on the honest parties’ input together with all possible values of the adversarial inputs). For example, in any non-interactive sealed-bid auction, the last bidder can figure out what was the highest previous bid. We present a new MPC model which avoids this privacy leak. To achieve this, we utilize a blockchain in a novel way, incorporating smart contracts and arbitrary parties that can be incentivized to perform computation (“bounty hunters,” akin to miners). Security is maintained under a monetary assumption about the parties: an honest party can temporarily supply a recoverable collateral of value higher than the computational cost an adversary can expend. We thus construct non-interactive MPC protocols with strong security guarantees (full security, no residual leakage) in the short term. Over time, as the adversary can invest more and more computational resources, the security guarantee decays. Thus, our model, which we call Gage MPC, is suitable for secure computation with limited-time secrecy, such as auctions. A key ingredient in our protocols is a primitive we call “Gage Time Capsules” (GaTC): a time capsule that allows a party to commit to a value that others are able to reveal but only at a designated computational cost. A GaTC allows a party to commit to a value together with a monetary collateral. If the original party properly opens the GaTC, it can recover the collateral. Otherwise, the collateral is used to incentivize bounty hunters to open the GaTC. This primitive is used to ensure completion of Gage MPC protocols on the desired inputs. As a requisite tool (of independent interest), we present a generalization of garbled circuit that are more robust: they can tolerate exposure of extra input labels. This is in contrast to Yao’s garbled circuits, whose secrecy breaks down if even a single extra label is exposed. Finally, we present a proof-of-concept implementation of a special case of our construction, yielding an auction functionality over an Ethereum-like blockchain.

Abstract We propose F alcon , an end-to-end 3-party protocol for efficient private training and inference of large machine learning models. F alcon presents four main advantages – (i) It is highly expressive with support for high capacity networks such as VGG16 (ii) it supports batch normalization which is important for training complex networks such as AlexNet (iii) F alcon guarantees security with abort against malicious adversaries, assuming an honest majority (iv) Lastly, F alcon presents new theoretical insights for protocol design that make it highly efficient and allow it to outperform existing secure deep learning solutions. Compared to prior art for private inference, we are about 8× faster than SecureNN (PETS’19) on average and comparable to ABY 3 (CCS’18). We are about 16 − 200× more communication efficient than either of these. For private training, we are about 6× faster than SecureNN, 4.4× faster than ABY 3 and about 2−60× more communication efficient. Our experiments in the WAN setting show that over large networks and datasets, compute operations dominate the overall latency of MPC, as opposed to the communication.

Reporting sexual assault and harassment is an important and difficult problem. Since late 2017, it has received increased attention as the viral #MeToo movement has brought about accusations against high-profile individuals and a wider discussion around the prevalence of sexual violence. Addressing occurrences of sexual assault requires a system to record and process accusations. It is natural to ask what security guarantees are necessary and achievable in such a system. In particular, we focus on detecting repeat offenders: only when a set number of accusations are lodged against the same party will the accusations be revealed to a legal counselor. Our solution ensures the confidentiality of the accuser and the accused as well as the traceability of false accusations using various cryptographic techniques. The protocol design emphasizes practicality, preferring fast operations that are implemented in existing software libraries.

The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is a complete Paillier (in: EUROCRYPT, pp 223–238, 1999 ) threshold encryption scheme in the two-party setting with security against malicious attacks. We further describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation protocol is comprised of the following subprotocols: ( i ) a distributed protocol for generation of an RSA composite and ( ii ) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite for the public key and is comprised of the following subprotocols: ( i ) a distributed generation of the corresponding secret key shares and ( ii ) a distributed decryption protocol for decrypting according to Paillier.

Abstract Reporting sexual assault and harassment is an important and difficult problem. Since late 2017, it has received increased attention as the viral #MeToo movement has brought about accusations against high-profile individuals and a wider discussion around the prevalence of sexual violence. Addressing occurrences of sexual assault requires a system to record and process accusations. It is natural to ask what security guarantees are necessary and achievable in such a system. In particular, we focus on detecting repeat offenders: only when a set number of accusations are lodged against the same party will the accusations be revealed to a legal counselor. Previous solutions to this privacy-preserving reporting problem, such as the Callisto Protocol of Rajan et al., have focused on the confidentiality of accusers. This paper proposes a stronger security model that ensures the confidentiality of the accuser and the accused as well as the traceability of false accusations. We propose the WhoToo protocol to achieve this notion of security using suitable cryptographic techniques. The protocol design emphasizes practicality, preferring fast operations that are implemented in existing software libraries. We estimate that an implementation would be suitably performant for real-world deployment.

Abstract The growing availability of genomic data holds great promise for advancing medicine and research, but unlocking its full potential requires adequate methods for protecting the privacy of individuals whose genome data we use. One example of this tension is running Similar Patient Query on remote genomic data: In this setting a doctor that holds the genome of his/her patient may try to find other individuals with “close” genomic data, and use the data of these individuals to help diagnose and find effective treatment for that patient’s conditions. This is clearly a desirable mode of operation. However, the privacy exposure implications are considerable, and so we would like to carry out the above “closeness” computation in a privacy preserving manner. In this work we put forward a new approach for highly efficient secure computation for computing an approximation of the Similar Patient Query problem. We present contributions on two fronts. First, an approximation method that is designed with the goal of achieving efficient private computation. Second, further optimizations of the two-party protocol. Our tests indicate that the approximation method works well, it returns the exact closest records in 98% of the queries and very good approximation otherwise. As for speed, our protocol implementation takes just a few seconds to run on databases with thousands of records, each of length thousands of alleles, and it scales almost linearly with both the database size and the length of the sequences in it. As an example, in the datasets of the recent iDASH competition, after a one-time preprocessing of around 12 seconds, it takes around a second to find the nearest five records to a query, in a size-500 dataset of length- 3500 sequences. This is 2-3 orders of magnitude faster than using state-of-the-art secure protocols with existing edit distance algorithms.

Attribute-based methods provide authorization to parties based on whether their set of attributes (e.g., age, organization, etc.) fulfills a policy. In attribute-based encryption (ABE), authorized parties can decrypt, and in attribute-based credentials (ABCs), authorized parties can authenticate themselves. In this paper, we combine elements of ABE and ABCs together with garbled circuits to construct attribute-based key exchange (ABKE). Our focus is on an interactive solution involving a client that holds a certificate (issued by an authority) vouching for that client's attributes and a server that holds a policy computable on such a set of attributes. The goal is for the server to establish a shared key with the client but only if the client's certified attributes satisfy the policy. Our solution enjoys strong privacy guarantees for both the client and the server, including attribute privacy and unlinkability of client sessions.

We present a unified framework for studying secure multiparty computation (MPC) with arbitrarily restricted interaction patterns such as a chain, a star, a directed tree, or a directed graph. Our study generalizes both standard MPC and recent models for MPC with specific restricted interaction patterns, such as those studied by Halevi et al. (Crypto 2011), Goldwasser et al. (Eurocrypt 2014), and Beimel et al. (Crypto 2014).

Physical computational devices leak side-channel information that may, and often does, reveal secret internal states. We present a general transformation that compiles any circuit into a circuit with the same functionality but resilience against well-defined classes of leakage. Our construction requires a small, stateless, and computation-independent leak-proof component that draws random elements from a fixed distribution. In essence, we reduce the problem of shielding arbitrarily complex circuits to the problem of shielding a single, simple component. Our approach is based on modeling the adversary as a powerful observer that inspects the device via a limited measurement apparatus. We allow the apparatus to access all the bits of the computation (except those inside the leak-proof component), and the amount of leaked information to grow unbounded over time. However, we assume that the apparatus is limited in the amount of output bits per iteration and the ability to decode certain linear encodings. While our results apply in general to such leakage classes, in particular, we obtain security against (a) constant-depth circuits leakage, where the leakage function is computed by an $\mathsf{AC}^0$ circuit (composed of NOT gates and unbounded fan-in AND and OR gates); (b) noisy leakage, where the leakage function reveals all the bits of the internal state of the circuit, but each bit is perturbed by independent binomial noise---i.e., flipped with some probability $p$. Namely, for some number $p\in(0,1/2]$, each bit of the computation is flipped with probability $p$, and remains unchanged with probability $1-p$.

This paper investigates compression of data encrypted with block ciphers, such as the Advanced Encryption Standard. It is shown that such data can be feasibly compressed without knowledge of the secret key. Block ciphers operating in various chaining modes are considered and it is shown how compression can be achieved without compromising security of the encryption scheme. Further, it is shown that there exists a fundamental limitation to the practical compressibility of block ciphers when no chaining is used between blocks. Some performance results for practical code constructions used to compress binary sources are presented.

We investigate the question of whether the security of protocols in the information-theoretic setting (where the adversary is computationally unbounded) implies the security of these protocols under concurrent composition. This question is motivated by the folklore that all known protocols that are secure in the information-theoretic setting are indeed secure under concurrent composition. We provide answers to this question for a number of different settings (i.e., considering perfect versus statistical security, and concurrent composition with adaptive versus fixed inputs). Our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security.

This paper investigates compression of encrypted data. It has been previously shown that data encrypted with Vernam's scheme, also known as the one-time pad, can be compressed without knowledge of the secret key, therefore this result can be applied to stream ciphers used in practice. However, it was not known how to compress data encrypted with non-stream ciphers. In this paper, we address the problem of compressing data encrypted with block ciphers, such as the advanced encryption standard (AES) used in conjunction with one of the commonly employed chaining modes. We show that such data can be feasibly compressed without knowledge of the key. We present performance results for practical code constructions used to compress binary sources.

We investigate the question of whether security of protocols in the information-theoretic setting (where the adversary is computationally unbounded) implies security under concurrent composition. This question is motivated by the folklore that all known protocols that are secure in the information-theoretic setting are indeed secure under concurrent composition. We provide answers to this question for a number of different settings (i.e., considering perfect versus statistical security, and concurrent composition with adaptive versus fixed inputs). Our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security.

A fundamental problem of distributed computing is that of simulating a secure broadcast channel, within the setting of a point-to-point network. This problem is known as Byzantine Agreement (or Generals) and has been the focus of much research. Lamport et al. [1982] showed that in order to achieve Byzantine Agreement in the plain model, more than two thirds of the participating parties must be honest. They further showed that by augmenting the network with a public-key infrastructure for digital signatures, it is possible to obtain protocols that are secure for any number of corrupted parties. The problem in this augmented model is called “authenticated Byzantine Agreement”.In this article, we consider the question of concurrent, parallel and sequential composition of authenticated Byzantine Agreement protocols with a single common setup. We present surprising impossibility results showing that:(1) Authenticated Byzantine Agreement protocols that remain secure under parallel or concurrent composition (even for just two executions) and tolerate a third or more corrupted parties, do not exist.(2) Deterministic authenticated Byzantine Agreement protocols that run for r rounds and tolerate a third or more corrupted parties, can remain secure for at most 2 r − 1 sequential executions.In contrast, we present randomized protocols for authenticated Byzantine Agreement that remain secure under sequential composition, for any polynomial number of executions. We exhibit two such protocols. In the first protocol, an honest majority is required. In the second protocol, any number of parties may be corrupted; however, the complexity of the protocol is in the order of 2 n · n ! for n parties. In order to have this polynomial in the security parameter k (used for the signature scheme in the protocol), this requires the overall number of parties to be limited to O (log k /log log k ). The above results are achieved due to a new protocol for authenticated Byzantine Generals for three parties that can tolerate any number of faulty parties and composes sequentially.Finally, we show that when the model is further augmented so that in each session, all the participating parties receive a common session identifier that is unique to that session, then any polynomial number of authenticated Byzantine agreement protocols can be concurrently executed, while tolerating any number of corrupted parties.

The question of the composition of protocols is an important and heavily researched one. In this paper we consider the problem of sequential composition of synchronous protocols that do not have simultaneous termination; i.e., the parties do not necessarily conclude a protocol execution in the same round. A problem arises becauses such protocols must begin in synchrony; therefore a second execution cannot follow from the first in a straightforward manner. An important example of a protocol with this property is that of randomized Byzantine Agreement with an expected constant number of rounds (such as the one due to Feldman and Micali). We note that expected constant-round Byzantine Agreement cannot have simultaneous termination and thus this (problematic) property is inherent.Given that the termination of the parties is not simultaneous, a natural question to consider is how to synchronize the parties so that such protocols can be sequentially composed. Furthermore, such a composition should preserve the original running-time of the protocol, i.e. running the protocol ℓ times sequentially should take in the order of ℓ times the running-time of the protocol. In this paper, we present a method for sequentially composing any protocol in which the players do not terminate in the same round, while preserving the original round complexity. An important application of this result is the sequential composition of parallel Byzantine Agreement. Such a composition can be used by parties connected in a point-to-point network to run protocols designed for the broadcast model, while maintaining the original round complexity.

A fundamental problem of distributed computing is that of simulating a (secure) broadcast channel, within the setting of a point-to-point network. This problem is known as Byzantine Agreement and has been the focus of much research. Lamport et al. showed that in order to achieve Byzantine Agreement in the standard model, more than 2/3 of the participating parties must be honest. They further showed that by augmenting the network with a public-key infrastructure, it is possible to obtain secure protocols for any number of faulty parties. This augmented problem is called "authenticated Byzantine Agreement".In this paper we consider the question of concurrent, parallel and sequential composition of authenticated Byzantine Agreement protocols. We present surprising impossibility results showing that:

The round complexity of interactive protocols is one of their most important complexity measures. In this work we study the exact round complexity of two basic secure computation tasks: Verifiable Secret Sharing (VSS) and Secure Multicast.

The goal of this paper is to introduce a simple verifiable secret sharing scheme, to improve the efficiency of known secure multiparty protocols and, by employing these techniques, to improve the efficiency of applications which use these protocols.First we present a very simple Verifiable Secret Sharing protocol which is based on fast cryptographic primitives and avoids altogether the need for expensive zero-knowledge proofs.This is followed by a highly simplified protocol to compute multiplications over shared secrets.This is a major component in secure multiparty computation protocols and accounts for much of the complexity of proposed solutions.Using our protocol as a plug-in unit in known protocols reduces their complexity.We show how to achieve efficient multiparty computations in the computational model, through the application of homomorphic commitments.Finally, we present fast-track multiparty computation protocols.In a model in which malicious faults are rare we show that it is possible to carry out a simpler and more efficient protocol which does not perform all the expensive checks needed to combat a malicious adversary from foiling the computation.Yet, the protocol still enables detection of faults and recovers the computation when faults occur without giving any information advantage to the adversary.This results in protocols which are much more efficient under normal operation of the system i.e. when there are no faults.As an example of the practical impact of our work we show how our techniques can be used to greatly improve the speed and the fault-tolerance of existing threshold cryptography protocols.

A shared coin is one which n players "simultaneously" hold and can later reveal, but no sufficiently small coalition can influence or `a priori predict the outcome. Such coins are expensive to produce, yet many distributed protocols (including broadcast and Byzantine agreement) need them in bulk. We introduce a new paradigm for obtaining shared coins. We suggest distributed, pseudorandom bit generators (D-PRBGs). Analogous to a pseudo-random bit generator, which is an efficient algorithm to expand a short random seed into a long random looking sequence, a DPRBG is a protocol which "expands" a "distributed seed," consisting of shared coins, into a longer "sequence" of shared coins, at low amortized cost per coin produced. Our main result is the construction of a D-PRBG in which this amortized cost (computation and communication) is significantly lower than the cost of any "from-scratch" shared coin generation protocol. Furthermore, for applications which are executed repeatedly, we sugg...

We investigate the problem of multiparty computations in a fully connected, asynchronous network of n players, in which up to t Byzantine faults may occur.

The problem of Verifiable Secret Sharing (VSS) is the following: A dealer, who may be honest or cheating, can share a secret s , among n ≥ 2 t + 1 players, where t players at most are cheaters. The sharing process will cause the dealer to commit himself to a secret s . If the dealer is honest, then, during the sharing process, the set of dishonest players will have no information about s . When the secret is reconstructed, at a later time, all honest players will reconstruct s . The solution that is given is a constant round protocol, with polynomial time local computations and polynomial message size. The protocol assumes private communication lines between every two participants, and a broadcast channel. The protocol achieves the desired properties with an exponentially small probability of error. A new tool, called Information Checking , which provides authentication and is not based on any unproven assumptions, is introduced, and may have wide application elsewhere. For the case in which it is known that the dealer is honest, a simple constant round protocol is proposed, without assuming broadcast. A weak version of secret sharing is defined: Weak Secret Sharing (WSS). WSS has the same properties as VSS for the sharing process. But, during reconstruction, if the dealer is dishonest, then he might obstruct the reconstruction of s . A protocol for WSS is also introduced. This protocol has an exponentially small probability of error. WSS is an essential building block for VSS. For certain applications, the much simpler WSS protocol suffice. All protocols introduced in this paper are secure in the Information Theoretic sense.

It is known that, in both asynchronous and synchronous networks, no Byzantine Agreement (BA) protocol for n players exists if d e of the players are faulty (in other words, no BA protocol is d e-resilient). The only known asynchronous (d e \\Gamma 1)-resilient BA protocol runs in expected exponential time, and the best resilience achieved by an asynchronous protocol with polynomial complexity is (d 4 e \\Gamma 1). The question whether there exists an asynchronous (d BA protocol with polynomial complexity remained open.

Under the assumption that each participant can broadcast a message to all other participants and that each pair of participants can communicate secretly, we present a verifiable secret sharing protocol, and show that any multiparty protocol, or game with incomplete information, can be achieved if a majority of the players are honest. The secrecy achieved is unconditional and does not rely on any assumption about computational intractability. Applications of these results to Byzantine Agreement are also presented.