International Association
for Cryptologic Research

We propose a novel variant of functional encryption which supports ciphertext updates, dubbed ciphertext-updatable functional encryption. Such a feature further broadens the practical applicability of the functional encryption paradigm and allows for fine-grained access control even after a ciphertext is generated. Updating ciphertexts is carried out via so-called update tokens which a dedicated party can use to convert ciphertexts. However, allowing update tokens requires some care for the security definition. Our contribution is threefold: (a) We define our new primitive with a security notion in the indistinguishability setting. Within CUFE, functional decryption keys and ciphertexts are labeled with tags such that only if the tags of the decryption key and the ciphertext match, then decryption succeeds. Furthermore, we allow ciphertexts to switch their tags to any other tag via update tokens. Such tokens are generated by the holder of the main secret key and can only be used in the desired direction. (b) We present a generic construction of CUFE for any functionality as well as predicates different from equality testing on tags which relies on the existence of indistinguishability obfuscation (iO). (c) We present a practical construction of CUFE for the inner-product functionality from standard assumptions (i.e., LWE) in the random-oracle model. On the technical level, we build on the recent functional encryption schemes with fine-grained access control and linear operations on encrypted data (Abdalla et al., AC’20) and introduce an additional ciphertext updatability feature. Proving security for such a construction turned out to be non-trivial, particularly when revealing keys for the updated challenge ciphertext is allowed. Overall, such construction enriches the set of known inner-product functional encryption schemes with the additional updatability feature of ciphertexts.

Analysis of advanced physical unclonable function (PUF) applications and protocols relies on assuming that a PUF behaves like a random oracle; that is, upon receiving a challenge, a uniform random response with replacement is selected, measurement noise is added, and the resulting response is returned. In order to justify such an assumption, we need to rely on digital interface computation that to some extent remains confidential—otherwise, information about PUF challenge–response pairs leak with which the adversary can train a prediction model for the PUF. We introduce a theoretical framework that allows the adversary to have a prediction model (with a typical accuracy of 75% for predicting response bits for state-of-the-art silicon PUF designs). We do not require any confidential digital computing or digital secrets, while we can still prove rigorous statements about the bit security of a system that interfaces with the PUF. In particular, we prove the bit security of a PUF-based random oracle construction; this merges the PUF framework with fuzzy extractors.

We consider the problem of constant-round secure two-party computation in the presence of active (malicious) adversaries. We present the first protocol that has only a constant multiplicative communication overhead compared to Yao’s protocol for passive adversaries, and can be implemented in the plain model by only making a black-box use of (parallel) oblivious transfer and a pseudo-random generator. This improves over the polylogarithmic overhead of the previous best protocol. A similar result could previously be obtained only in an amortized setting, using preprocessing, or by assuming bit-oblivious-transfer as an ideal primitive that has a constant cost. We present two variants of this result, one which is aimed at minimizing the number of oblivious transfers and another which is aimed at optimizing concrete efficiency. Our protocols are based on a novel combination of previous techniques together with a new efficient protocol to certify that pairs of strings transmitted via oblivious transfer satisfy a global relation. Settling for “security with correlated abort”, the concrete communication complexity of the second variant of our protocol can beat the best previous protocols with the same kind of security even for realistic values of the circuit size and the security parameter. This variant is particularly attractive in the offline–online setting, where the online cost is dominated by a single evaluation of an authenticated garbled circuit, and can also be made non-interactive using the Fiat–Shamir heuristic.

A central challenge in the study of MPC is to balance between security guarantees, hardness assumptions, and resources required for the protocol. In this work, we study the cost of tolerating adaptive corruptions in MPC protocols under various corruption thresholds. In the strongest setting, we consider adaptive corruptions of an arbitrary number of parties (potentially all) and achieve the following results: (1) A two-round secure function evaluation (SFE) protocol in the CRS model, assuming LWE and indistinguishability obfuscation (iO). The communication, the CRS size, and the online computation are sublinear in the size of the function. The iO assumption can be replaced by secure erasures. Previous results required either the communication or the CRS size to be polynomial in the function size. (2) Under the same assumptions, we construct a “Bob-optimized” 2PC (where Alice talks first, Bob second, and Alice learns the output). That is, the communication complexity and total computation of Bob are sublinear in the function size and in Alice’s input size. We prove impossibility of “Alice-optimized” protocols. (3) Assuming LWE, we bootstrap adaptively secure NIZK arguments to achieve proof size sublinear in the circuit size of the NP relation. On a technical level, our results are based on laconic function evaluation (LFE) (Quach, Wee, and Wichs, FOCS’18) and shed light on an interesting duality between LFE and FHE. Next, we analyze adaptive corruptions of all-but-one of the parties and show a two-round SFE protocol in the threshold-PKI model (where keys of a threshold FHE scheme are pre-shared among the parties) with communication complexity sublinear in the circuit size, assuming LWE and NIZK. Finally, we consider the honest-majority setting and show a two-round SFE protocol with guaranteed output delivery under the same constraints. Our results highlight that the asymptotic cost of adaptive security can be reduced to be comparable to, and in many settings almost match, that of static security, with only a little sacrifice to the concrete round complexity and asymptotic communication complexity.

An $$\alpha $$ α -fair coin-tossing protocol allows a set of mutually distrustful parties to generate a uniform bit, such that no efficient adversary can bias the output bit by more than $$\alpha $$ α . Cleve (in: Proceedings of the 18th annual ACM symposium on theory of computing (STOC), 1986) has shown that if half of the parties can be corrupted, then no $$r$$ r -round coin-tossing protocol is $$o(1/r)$$ o ( 1 / r ) -fair. For over two decades, the best-known m -party protocols, tolerating up to $${t}\ge m/2$$ t ≥ m / 2 corrupted parties, were only $$O\left( {t}/\sqrt{r} \right) $$ O t / r -fair. In a surprising result, Moran et al. (in: Theory of cryptography, sixth theory of cryptography conference, TCC, 2009) constructed an $$r$$ r -round two-party $$O(1/r)$$ O ( 1 / r ) -fair coin-tossing protocol, i.e., an optimally fair protocol. Beimel et al. (in: Rabin (ed) Advances in cryptology—CRYPTO 2010, volume 6223 of lecture notes in computer science, Springer, 2010) extended the result of Moran et al. to the multiparty setting where strictly fewer than 2/3 of the parties are corrupted. They constructed a $$2^{2^k}/r$$ 2 2 k / r -fair r -round m -party protocol, tolerating up to $$t=\frac{m+k}{2}$$ t = m + k 2 corrupted parties. In a breakthrough result, Haitner and Tsfadia (in: Symposium on theory of computing, STOC, 2014) constructed an $$O\left( \log ^3(r)/r \right) $$ O log 3 ( r ) / r -fair (almost optimal) three-party coin-tossing protocol. Their work brought forth a combination of novel techniques for coping with the difficulties of constructing fair coin-tossing protocols. Still, the best coin-tossing protocols for the case where more than 2/3 of the parties may be corrupted (and even when $$t=2m/3$$ t = 2 m / 3 , where $$m>3$$ m > 3 ) were $$\theta \left( 1/\sqrt{r} \right) $$ θ 1 / r -fair. We construct an $$O\left( \log ^3(r)/r \right) $$ O log 3 ( r ) / r -fair m -party coin-tossing protocol, tolerating up to t corrupted parties, whenever m is constant and $$t<3m/4$$ t < 3 m / 4 .

We propose and implement a multiparty homomorphic encryption (MHE) scheme with a $$t$$ t -out-of- $$N$$ N -threshold access-structure that is efficient and does not require a trusted dealer in the common random string model. We construct this scheme from the ring-learning-with-error assumptions and as an extension of the MHE scheme of Mouchet et al. (PETS 21). By means of a specially adapted share re-sharing procedure, this extension can be used to relax the $$N$$ N -out-of- $$N$$ N -threshold access-structure of the original scheme into a $$t$$ t -out-of- $$N$$ N -threshold one. This procedure introduces only a single round of communication during the setup phase, after which any set of at least t parties can compute a t -out-of- t additive sharing of the secret-key with no interaction; this new sharing can be used directly in the scheme of Mouchet et al. We show that, by performing Shamir re-sharing over the MHE ciphertext-space ring with a carefully chosen exceptional set, this reconstruction procedure can be made secure and has negligible overhead. Moreover, it only requires the parties to store a constant-size state after its setup phase. Hence, in addition to fault tolerance, lowering the corruption threshold also yields considerable efficiency benefits, by enabling the distribution of batched secret-key operations among the online parties. We implemented and open-sourced our scheme in the Lattigo library.

Two of the most sought-after properties of multi-party computation (MPC) protocols are fairness and guaranteed output delivery (GOD), the latter also referred to as robustness. Achieving both, however, brings in the necessary requirement of malicious-minority. In a generalized adversarial setting where the adversary is allowed to corrupt both actively and passively, the necessary bound for a n -party fair or robust protocol turns out to be $$t_a + t_p < n$$ t a + t p < n , where $$t_a,t_p$$ t a , t p denote the threshold for active and passive corruption with the latter subsuming the former. Subsuming the malicious-minority as a boundary special case, this setting, denoted as dynamic corruption, opens up a range of possible corruption scenarios for the adversary. While dynamic corruption includes the entire range of thresholds for $$(t_a,t_p)$$ ( t a , t p ) starting from $$(\lceil \frac{n}{2} \rceil - 1, \lfloor \frac{n}{2} \rfloor )$$ ( ⌈ n 2 ⌉ - 1 , ⌊ n 2 ⌋ ) to $$(0,n-1)$$ ( 0 , n - 1 ) , the boundary corruption restricts the adversary only to the boundary cases of $$(\lceil \frac{n}{2} \rceil - 1, \lfloor \frac{n}{2} \rfloor )$$ ( ⌈ n 2 ⌉ - 1 , ⌊ n 2 ⌋ ) and $$(0,n-1)$$ ( 0 , n - 1 ) . Notably, both corruption settings empower an adversary to control majority of the parties, yet ensuring the count on active corruption never goes beyond $$\lceil \frac{n}{2} \rceil - 1$$ ⌈ n 2 ⌉ - 1 . We target the round complexity of fair and robust MPC tolerating dynamic and boundary adversaries. As it turns out, $$\lceil \frac{n}{2} \rceil + 1$$ ⌈ n 2 ⌉ + 1 rounds are necessary and sufficient for fair as well as robust MPC tolerating dynamic corruption. The non-constant barrier raised by dynamic corruption can be sailed through for a boundary adversary. The round complexity of 3 and 4 is necessary and sufficient for fair and GOD protocols, respectively, with the latter having an exception of allowing 3-round protocols in the presence of a single active corruption. While all our lower bounds assume pairwise-private and broadcast channels and hold in the presence of correlated randomness setup (which subsumes both public (CRS) and private (PKI) setup), our upper bounds are broadcast-only and assume only public setup. The traditional and popular setting of malicious-minority, being restricted compared to both dynamic and boundary setting, requires 3 and 2 rounds in the presence of public and private setup, respectively, for both fair and GOD protocols.

A wiretap coding scheme (Wyner in Bell Syst Tech J 54(8):1355–1387, 1975) enables Alice to reliably communicate a message m to an honest Bob by sending an encoding c over a noisy channel $$\textsf{ChB}$$ ChB , while at the same time hiding m from Eve who receives c over another noisy channel $$\textsf{ChE}$$ ChE . Wiretap coding is clearly impossible when $$\textsf{ChB}$$ ChB is a degraded version of $$\textsf{ChE}$$ ChE , in the sense that the output of $$\textsf{ChB}$$ ChB can be simulated using only the output of $$\textsf{ChE}$$ ChE . A classic work of Csiszár and Korner (IEEE Trans Inf Theory 24(3):339–348, 1978) shows that the converse does not hold. This follows from their full characterization of the channel pairs $$(\textsf{ChB},\textsf{ChE})$$ ( ChB , ChE ) that enable information-theoretic wiretap coding. In this work, we show that in fact the converse does hold when considering computational security ; that is, wiretap coding against a computationally bounded Eve is possible if and only if $$\textsf{ChB}$$ ChB is not a degraded version of $$\textsf{ChE}$$ ChE . Our construction assumes the existence of virtual black-box obfuscation of specific classes of “evasive” functions that generalize fuzzy point functions and can be heuristically instantiated using indistinguishability obfuscation. Finally, our solution has the appealing feature of being universal in the sense that Alice’s algorithm depends only on $$\textsf{ChB}$$ ChB and not on $$\textsf{ChE}$$ ChE .

Approximated homomorphic encryption (HE) schemes such as CKKS are commonly used to perform computations over encrypted real numbers. It is commonly assumed that these schemes are not “exact” and thus they cannot execute circuits with unbounded depth over discrete sets, such as binary or integer numbers, without error overflows. These circuits are usually executed using BGV and B/FV for integers and TFHE for binary numbers. This artificial separation can cause users to favor one scheme over another for a given computation, without even exploring other, perhaps better, options. We show that by treating step functions as “clean-up” utilities and by leveraging the SIMD capabilities of CKKS, we can extend the homomorphic encryption toolbox with efficient tools. These tools use CKKS to run unbounded circuits that operate over binary and small-integer elements and even combine these circuits with fixed-point real numbers circuits. We demonstrate the results using the Turing-complete Conway’s Game of Life. In our evaluation, for boards of size 256 $$\times $$ × 256, these tools achieved orders of magnitude faster latency than previous implementations using other HE schemes. We argue and demonstrate that for large enough real-world inputs, performing binary circuits over CKKS, while considering it as an “exact” scheme, results in comparable or even better performance than using other schemes tailored for similar inputs.

We unify the state-of-the-art bootstrapping algorithms for BGV and BFV in a single framework and show that both schemes can be bootstrapped with identical complexity. This result corrects a claim by Chen and Han (Eurocrypt 2018) that BFV is more efficient to bootstrap than BGV. We also fix an error in their optimized procedure for power-of-two cyclotomics, which occurs for some parameter sets. Our analysis is simpler, yet more general than earlier work, in that it simultaneously covers both BGV and BFV. Furthermore, we also design and implement a high-level open source software library for bootstrapping in the Magma Computer Algebra System. It is the first library to support both BGV and BFV bootstrapping in full generality, with all recent techniques (including the above fixes) and trade-offs.

Garbled circuits are a fundamental cryptographic primitive that allows two or more parties to securely evaluate an arbitrary Boolean circuit without revealing any information beyond the output using a constant number of communication rounds. Garbled circuits have been introduced by Yao (FOCS’86) and generalized to the multi-party setting by Beaver, Micali and Rogaway (STOC’90). Since then, several works have improved their efficiency by providing different garbling schemes and several implementations exist. Starting with the seminal Fairplay compiler (USENIX Security’04), several implementation frameworks decoupled the task of compiling the function to be evaluated into a Boolean circuit from the engine that securely evaluates that circuit, e.g., using a secure two-party computation protocol based on garbled circuits. In this paper, we show that this decoupling of circuit generation and evaluation allows a subtle attack on several prominent garbling schemes. It occurs when violating the implicit assumption on the circuit that gates have different input wires which is most often not explicitly specified in the respective papers. The affected garbling schemes use separate calls to a deterministic encryption function for the left and right input wire of a gate to derive pseudo-random encryption pads that are XORed together. When a circuit contains a gate where the left and right input wire are the same, these two per-wire encryption pads cancel out and we demonstrate that this can result in a complete break of privacy. We show how the vulnerable garbling schemes can be fixed easily.

Byzantine agreement (BA), the task of n parties to agree on one of their input bits in the face of malicious agents, is a powerful primitive that lies at the core of a vast range of distributed protocols. Interestingly, in BA protocols with the best overall communication, the demands of the parties are highly unbalanced : the amortized cost is $${\tilde{O}}(1)$$ O ~ ( 1 ) bits per party, but some parties must send $$\Omega (n)$$ Ω ( n ) bits. In best known balanced protocols, the overall communication is sub-optimal, with each party communicating $${\tilde{O}}(\sqrt{n})$$ O ~ ( n ) . In this work, we ask whether asymmetry is inherent for optimizing total communication. In particular, is BA possible where each party communicates only $${\tilde{O}}(1)$$ O ~ ( 1 ) bits? Our contributions in this line are as follows: We define a cryptographic primitive— succinctly reconstructed distributed signatures (SRDS)—that suffices for constructing $${\tilde{O}}(1)$$ O ~ ( 1 ) balanced BA. We provide two constructions of SRDS from different cryptographic and public-key infrastructure (PKI) assumptions. The SRDS-based BA follows a paradigm of boosting from “almost-everywhere” agreement to full agreement, and does so in a single round. Complementarily, we prove that PKI setup and cryptographic assumptions are necessary for such protocols in which every party sends o ( n ) messages. We further explore connections between a natural approach toward attaining SRDS and average-case succinct non-interactive argument systems (SNARGs) for a particular type of NP-Complete problems (generalizing Subset-Sum and Subset-Product). Our results provide new approaches forward, as well as limitations and barriers, toward minimizing per-party communication of BA. In particular, we construct the first two BA protocols with $${\tilde{O}}(1)$$ O ~ ( 1 ) balanced communication, offering a trade-off between setup and cryptographic assumptions and answering an open question presented by King and Saia (DISC’09).

We propose a new approach to construct general-purpose indistinguishability obfuscation (iO). Our construction is obtained via a new intermediate primitive that we call split fully homomorphic encryption (split FHE), which we show to be sufficient for constructing iO. Specifically, split FHE is FHE where decryption takes the following two-step syntactic form: (i) a secret decryption step that uses the secret key and produces a hint which is (asymptotically) shorter than the length of the encrypted message, and (ii) a public decryption step that only requires the ciphertext and the previously generated hint (and not the entire secret key) and recovers the encrypted message. In terms of security, the hints for a set of ciphertexts should not allow one to violate semantic security for any other ciphertexts. Next, we show a generic candidate construction of split FHE based on three building blocks: (i) A standard FHE scheme with linear decrypt-and-multiply (which can be instantiated with essentially all LWE-based constructions), (ii) a linearly homomorphic encryption scheme with short decryption hints (such as the Damgård-Jurik encryption scheme, based on the DCR problem), and (iii) a cryptographic hash function (which can be based on a variety of standard assumptions). Our approach is heuristic in the sense that our construction is not provably secure and makes implicit assumptions about the interplay between these underlying primitives. We show evidence that this construction is secure by providing an argument in an appropriately defined oracle model. We view our construction as a big departure from the state-of-the-art constructions, and it is in fact quite simple.

In structure-preserving cryptography, every building block shares the same bilinear groups. These groups must be generated for a specific, a priori fixed security level, and thus, it is vital that the security reduction in all involved building blocks is as tight as possible. In this work, we present the first generic construction of structure-preserving signature schemes whose reduction cost is independent of the number of signing queries. Its chosen-message security is almost tightly reduced to the chosen-plaintext security of a structure-preserving public-key encryption scheme and the security of Groth–Sahai proof system. Technically, we adapt the adaptive partitioning technique by Hofheinz (Eurocrypt 2017) to the setting of structure-preserving signature schemes. To achieve a structure-preserving scheme, our new variant of the adaptive partitioning technique relies only on generic group operations in the scheme itself. Interestingly, however, we will use non-generic operations during our security analysis. Instantiated over asymmetric bilinear groups, the security of our concrete scheme is reduced to the external Diffie–Hellman assumption with linear reduction cost in the security parameter, independently of the number of signing queries. The signatures in our schemes consist of a larger number of group elements than those in other non-tight schemes, but can be verified faster, assuming their security reduction loss is compensated by increasing the security parameter to the next standard level.

We give a new approach to the elliptic curve discrete logarithm problem over cubic extension fields $${\mathbb {F}}_{q^3}$$ F q 3 . It is based on a transfer: First an $${\mathbb {F}}_q$$ F q -rational $$(\ell ,\ell ,\ell )$$ ( ℓ , ℓ , ℓ ) -isogeny from the Weil restriction of the elliptic curve under consideration with respect to $${\mathbb {F}}_{q^3}/{\mathbb {F}}_q$$ F q 3 / F q to the Jacobian variety of a genus three curve over $${\mathbb {F}}_q$$ F q is applied and then the problem is solved in the Jacobian via index-calculus attacks. Although it uses no covering maps in the construction of the desired homomorphism, this method is, in a sense, a kind of cover attack. As a result, it is possible to solve the discrete logarithm problem in some elliptic curve groups of prime order over $${\mathbb {F}}_{q^3}$$ F q 3 in a time of $${\tilde{O}}(q)$$ O ~ ( q ) .

Competitions are widely viewed as the safest way to select cryptographic algorithms. This paper surveys procedures that have been used in cryptographic competitions, and analyzes the extent to which those procedures reduce security risks.

Decentralized multi-authority attribute-based encryption ( $$\textsf{MA}$$ MA - $$\textsf{ABE}$$ ABE ) is a strengthening of standard ciphertext-policy attribute-based encryption so that there is no trusted central authority: Any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. Essentially, any party can act as an authority for some attribute by creating a public key of its own and issuing private keys to different users that reflect their attributes. This paper presents the first $$\textsf{MA}$$ MA - $$\textsf{ABE}$$ ABE proven secure under the standard search variant of bilinear Diffie–Hellman ( CBDH ) and in the random oracle model. Our scheme supports all access policies captured by $$\textsf{NC}^1$$ NC 1 circuits. All previous constructions were proven secure in the random oracle model and additionally were based on decision assumptions such as the DLIN assumption, non-standard q -type assumptions, or subspace decision assumptions over composite-order bilinear groups.

Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. The two classic adversary models considered are semi-honest (where the adversary follows the protocol specification but tries to learn more than allowed by examining the protocol transcript) and malicious (where the adversary may follow any arbitrary attack strategy). Protocols for semi-honest adversaries are often far more efficient, but in many cases the security guarantees are not strong enough. In this paper, we present new protocols for securely computing any functionality represented by an arithmetic circuit, assuming an honest majority exists . We utilize a new method for verifying that the adversary does not cheat, that yields a cost of just twice that of semi-honest protocols in some settings. Our protocols are information-theoretically secure in the presence of malicious adversaries. We present protocol variants for small and large fields, and show how to efficiently instantiate them based on replicated secret sharing and Shamir secret sharing. In particular, for large fields, our protocol requires each party to send just  2 field elements per multiplication gate in the three-party setting, and just  12 field elements per multiplication gate for any number of parties. As with previous works in this area aiming to achieve high efficiency, our protocol is secure with abort and does not achieve fairness, meaning that the adversary may receive output while the honest parties do not. We implemented our protocol and ran experiments for different numbers of parties, different network configurations and different circuit depths. Our protocol significantly outperforms the previous best for this setting (Lindell and Nof, CCS 2017); for a large number of parties (e.g., 100 parties), our implementation runs almost an order of magnitude faster than theirs.

The celebrated Fiat–Shamir transformation turns any public-coin interactive proof into a non-interactive one, which inherits the main security properties (in the random oracle model) of the interactive version. While originally considered in the context of 3-move public-coin interactive proofs, i.e., so-called $$\varSigma $$ Σ -protocols, it is now applied to multi-round protocols as well. Unfortunately, the security loss for a $$(2\mu + 1)$$ ( 2 μ + 1 ) -move protocol is, in general, approximately $$Q^\mu $$ Q μ , where Q is the number of oracle queries performed by the attacker. In general, this is the best one can hope for, as it is easy to see that this loss applies to the $$\mu $$ μ -fold sequential repetition of $$\varSigma $$ Σ -protocols, but it raises the question whether certain (natural) classes of interactive proofs feature a milder security loss. In this work, we give positive and negative results on this question. On the positive side, we show that for $$(k_1, \ldots , k_\mu )$$ ( k 1 , … , k μ ) -special-sound protocols (which cover a broad class of use cases), the knowledge error degrades linearly in Q , instead of $$Q^\mu $$ Q μ . On the negative side, we show that for t -fold parallel repetitions of typical $$(k_1, \ldots , k_\mu )$$ ( k 1 , … , k μ ) -special-sound protocols with $$t \ge \mu $$ t ≥ μ (and assuming for simplicity that t and Q are integer multiples of $$\mu $$ μ ), there is an attack that results in a security loss of approximately  $$\frac{1}{2} Q^\mu /\mu ^{\mu +t}$$ 1 2 Q μ / μ μ + t .

Fine-grained cryptography is constructing cryptosystems in a setting where an adversary’s resource is a-prior bounded and an honest party has less resource than an adversary. Currently, only simple form of encryption schemes, such as secret-key and public-key encryption, are constructed in this setting. In this paper, we enrich the available tools in fine-grained cryptography by proposing the first fine-grained secure attribute-based encryption (ABE) scheme. Our construction is adaptively secure under the widely accepted worst-case assumption, $$\mathsf {NC^1}\subsetneq \mathsf{\oplus L/poly}$$ NC 1 ⊊ ⊕ L / poly , and it is presented in a generic manner using the notion of predicate encodings (Wee, TCC’14). By properly instantiating the underlying encoding, we can obtain different types of ABE schemes, including identity-based encryption. Previously, all of these schemes were unknown in fine-grained cryptography. Our main technical contribution is constructing ABE schemes without using pairing or the Diffie-Hellman assumption. Hence, our results show that, even if one-way functions do not exist, we still have ABE schemes with meaningful security. For more application of our techniques, we construct an efficient (quasi-adaptive) non-interactive zero-knowledge proof system.

In the setting of secure multiparty computation, a set of parties wish to carry out a joint computation of their inputs while keeping them private. In this paper, we describe new information-theoretic protocols for secure three-party computation with an honest majority. Our protocols compute Boolean circuits with minimal computation and communication. We start with a protocol, based on replicated secret sharing, which is secure in the presence of semi-honest adversaries in which the parties communicate only a single bit per AND gate. Then, we show how to modify it to be secure in the presence of malicious adversaries. Our malicious protocol follows the paradigm of first constructing Beaver multiplication triples and then using them to verify that circuit gates are correctly computed. As in previous work (e.g., the so-called TinyOT and SPDZ protocols), we rely on the cut-and-choose paradigm to verify that triples are correctly constructed. We are able to utilize the fact that at most one of three parties is corrupted in order to construct an extremely simple and efficient method of constructing such triples. Then, we provide general techniques for improving efficiency of cut-and-choose protocols on multiplication triples and utilize them to further improve the protocol. The resulting protocol for malicious adversaries has bandwidth of only 7 bits per AND gate per party, when amortizing over 1 million gates and with statistical error $$2^{-40}$$ 2 - 40 . An implementation of our protocol achieves a throughput of over 7 billion AND gates per second with the semi-honest protocol, and over 1 billion AND gates per second with the malicious protocol (using the above parameters). Our results demonstrate that high-throughput secure computation is possible.

We introduce BICYCL  an open-source C++ library that implements arithmetic in the ideal class groups of imaginary quadratic fields, together with a set of cryptographic primitives based on class groups. It is available at https://gite.lirmm.fr/crypto/bicycl under GNU General Public License version 3 or any later version. BICYCL  provides significant speed-ups on the implementation of the arithmetic of class groups. Concerning cryptographic applications, BICYCL  is orders of magnitude faster than any previous pilot implementation of the $$\textsf{CL}$$ CL linearly encryption scheme, making it faster than Paillier’s encryption scheme at any security level. Linearly homomorphic encryption is the core of many multi-party computation protocols, sometimes involving a huge number of encryptions and homomorphic evaluations: class group-based protocols become the best solution in terms of bandwidth and computational efficiency to rely upon.

In this paper, we present 4 major contributions to ARX ciphers and in particular, to the Salsa/ChaCha family of stream ciphers: (a) We propose an improved differential-linear distinguisher against ChaCha. To do so, we propose a new way to approach the derivation of linear approximations by viewing the algorithm in terms of simpler subrounds. Using this idea, we show that it is possible to derive almost all linear approximations from previous works from just 3 simple rules. Furthermore, we show that with one extra rule, it is possible to improve the linear approximations proposed by Coutinho and Souza at Eurocrypt 2021 (Coutinho and Neto, in: Canteaut, Standaert (eds) Advances in cryptology—EUROCRYPT 2021—40th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, October 17–21, 2021, proceedings, Part I. Lecture notes in computer science, vol 12696, Springer, 2021). (b) We propose a technique called Bidirectional Linear Expansions (BLE) to improve attacks against Salsa. While previous works only considered linear expansions moving forward into the rounds, BLE explores the expansion of a single bit in both forward and backward directions. Applying BLE, we propose the first differential-linear distinguishers reaching 7 and 8 rounds of Salsa and we improve Probabilistic Neutral Bit (PNB) key-recovery attacks against 8 rounds of Salsa. (c) At Eurocrypt 2022 (Dey et al in Revamped differential-linear cryptanalysis on reduced round chacha, Springer, 2022), Dey et al. proposed a technique to combine two input–output positions in a PNB attack. In this paper, we generalize this technique for an arbitrary number of input–output positions. Combining this approach with BLE, we are able to improve key recovery attacks against 7 rounds of Salsa. (d) Using all the knowledge acquired studying the cryptanalysis of these ciphers, we propose some modifications in order to provide better diffusion per round and higher resistance to cryptanalysis, leading to a new stream cipher named Forró. We show that Forró has higher security margin; this allows us to reduce the total number of rounds while maintaining the security level, thus creating a faster cipher in many platforms, especially in constrained devices. (e) Finally, we developed CryptDances , a new tool for the cryptanalysis of Salsa, ChaCha, and Forró designed to be used in high performance environments with several GPUs. With CryptDances it is possible to compute differential correlations, to derive new linear approximations for ChaCha automatically, to automate the computation of the complexity of PNB attacks, among other features. We make CryptDances available for the community at https://github.com/murcoutinho/cryptDances .

The tower variant of the number field sieve (TNFS) is known to be asymptotically the most efficient algorithm to solve the discrete logarithm problem in finite fields of medium characteristics, when the extension degree is composite. A major obstacle to an efficient implementation of TNFS is the collection of algebraic relations, as it happens in dimension greater than 2. This requires the construction of new sieving algorithms which remain efficient as the dimension grows. In this article, we overcome this difficulty by considering a lattice enumeration algorithm which we adapt to this specific context. We also consider a new sieving area, a high-dimensional sphere, whereas previous sieving algorithms for the classical NFS considered an orthotope. Our new sieving technique leads to a much smaller running time, despite the larger dimension of the search space, and even when considering a larger target, as demonstrated by a record computation we performed in a 521-bit finite field  $${{{\mathbb {F}}}}_{p^6}$$ F p 6 . The target finite field is of the same form as finite fields used in recent zero-knowledge proofs in some blockchains. This is the first reported implementation of TNFS.

Driven by the open problem raised by Hofheinz and Kiltz (J Cryptol 25(3):484–527, 2012), we study the formalization of lattice-based programmable hash function (PHF) and give three types of concrete constructions by using several techniques such as a novel combination of cover-free sets and lattice trapdoors. Under the inhomogeneous small integer solution (ISIS) assumption, we show that any (non-trivial) lattice-based PHF is a collision-resistant hash function, which gives a direct application of this new primitive. We further demonstrate the power of lattice-based PHF by giving generic constructions of signature and identity-based encryption (IBE) in the standard model, which not only provide a way to unify several previous lattice-based schemes using the partitioning proof techniques, but also allow us to obtain new short signature schemes and IBE schemes from (ideal) lattices. Specifically, by instantiating the generic constructions with our Type-II and Type-III PHF constructions, we immediately obtain two short signatures and two IBE schemes with asymptotically much shorter keys. A major downside which inherits from our Type-II and Type-III PHF constructions is that we can only prove the security of the new signatures and IBEs in the bounded security model that the number Q of the adversary’s queries is required to be known in advance. Another downside is that the computational time of our new signatures and IBEs is a linear function of Q , which is large for typical parameters. To overcome the above limitations, we also give a refined way of using Type-II and Type-III PHFs to construct lattice-based short signatures with short verification keys in the full security model. In particular, our methods depart from the confined guessing technique of Böhl et al. (Eurocrypt’13) that was used to construct previous standard model short signature schemes with short verification keys by Ducas and Micciancio (Crypto’14) and by Alperin-Sheriff (PKC’15) and allow us to achieve much tighter security from weaker hardness assumptions.

Generic vulnerability assessment of cipher implementations against Fault Attacks (FA) is a largely unexplored research area. Security assessment against FA is critical for FA countermeasures. On several occasions, countermeasures fail to fulfil their sole purpose of preventing FA due to flawed design or implementation. This paper proposes a generic, simulation-based, statistical yes/no experiment for evaluating fault-assisted information leakage based on the principle of non-interference . It builds on an initial idea called ALAFA that utilizes t -test and its higher-order variants for detecting leakage at different moments of ciphertext distributions. In this paper, we improve this idea with a Deep Learning (DL)-based leakage detection test. The DL-based detection test is not specific to only moment-based leakages. It thus can expose leakages in several cases where t -test-based technique demands a prohibitively large number of ciphertexts. Further, we present two generalizations of the leakage assessment experiment—one for evaluating against the statistical ineffective fault model and another for assessing fault-induced leakages originating from “non-cryptographic” peripheral components of a security module. Finally, we explore techniques for efficiently covering the fault space of a block cipher by exploiting logic-level and cipher-level fault equivalences. The efficacy of our proposals has been evaluated on a rich test suite of hardened implementations, including an open-source Statistical Ineffective Fault Attack countermeasure and a hardware security module called Secured-Hardware-Extension.

We propose a novel framework, $$\texttt{Manticore}$$ Manticore , for multiparty computations, with full threshold and semi-honest security model, supporting a combination of real number arithmetic (arithmetic shares), Boolean arithmetic (Boolean shares) and garbled circuits (Yao shares). In contrast to prior work (Mohassel and Zhang, in 2017 IEEE symposium on security and privacy (SP), 2017; Mohassel and Rindal, in Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, 2018), $$\texttt{Manticore}$$ Manticore mitigates overflows, which is of paramount importance for machine learning applications, without compromising efficiency or security. Compared to other overflow-free recent techniques such as MP-SPDZ (Escudero et al., in 40th annual international cryptology conference, CRYPTO. Lecture notes in computer science, 2020) that convert arithmetic to Boolean shares, $$\texttt{Manticore}$$ Manticore uses an efficient modular lifting/truncation method that allows for scalable high numerical precision computations with optimal numerical windows and hence, highly efficient online phases. We adapt basic MPC operations such as real-valued polynomial evaluation, division, logarithms, exponentials, Fourier series evaluations and oblivious comparisons to $$\texttt{Manticore}$$ Manticore by employing our modular lift in combination with existing efficient conversions between arithmetic, Boolean and Yao shares. We also describe a highly scalable computations of logistic regression models with real-world training data sizes and high numerical precision through PCA and blockwise variants (for memory and runtime optimizations) based on second-order optimization techniques. On a dataset of 50 M samples and 50 features distributed among two players, the online phase completes in 14.5 h with at least 10 decimal digits of precision compared to plaintext training. The setup phase of $$\texttt{Manticore}$$ Manticore is supported in both the trusted dealer and the interactive models allowing for tradeoffs between efficiency and stronger security. The highly efficient online phase makes the framework particularly suitable for MPC applications where the output of the setup phase is part of the input of the protocol (such as MPC-in-the-head or Prio ).

Recently, numerous physical attacks have been demonstrated against lattice-based schemes, often exploiting their unique properties such as the reliance on Gaussian distributions, rejection sampling and FFT-based polynomial multiplication. As the call for concrete implementations and deployment of postquantum cryptography becomes more pressing, protecting against those attacks is an important problem. However, few countermeasures have been proposed so far. In particular, masking has been applied to the decryption procedure of some lattice-based encryption schemes, but the much more difficult case of signatures (which are highly nonlinear and typically involve randomness) has not been considered until now. In this paper, we describe the first masked implementation of a lattice-based signature scheme. Since masking Gaussian sampling and other procedures involving contrived probability distributions would be prohibitively inefficient, we focus on the GLP scheme of Güneysu, Lyubashevsky and Pöppelmann (CHES 2012). We show how to provably mask it in the Ishai–Sahai–Wagner model (CRYPTO 2003) at any order in a relatively efficient manner, using extensions of the techniques of Coron et al. for converting between arithmetic and Boolean masking. Our proof relies on a mild generalization of probing security that supports the notion of public outputs. We also provide a proof-of-concept implementation to assess the efficiency of the proposed countermeasure.

The growing volumes of data being collected and its analysis to provide better services are creating worries about digital privacy. To address privacy concerns and give practical solutions, the literature has relied on secure multiparty computation techniques. However, recent research over rings has mostly focused on the small-party honest-majority setting of up to four parties tolerating single corruption, noting efficiency concerns. In this work, we extend the strategies to support higher resiliency in an honest-majority setting with efficiency of the online phase at the centre stage. Our semi-honest protocol improves the online communication of the protocol of Damgård and Nielsen (CRYPTO’07) without inflating the overall communication. It also allows shutting down almost half of the parties in the online phase, thereby saving up to 50% in the system’s operational costs. Our maliciously secure protocol also enjoys similar benefits and requires only half of the parties, except for one-time verification towards the end, and provides security with fairness. To showcase the practicality of the designed protocols, we benchmark popular applications such as deep neural networks, graph neural networks, genome sequence matching, and biometric matching using prototype implementations. Our protocols, in addition to improved communication, aid in bringing up to 60–80% savings in monetary cost over prior work.

Secure multiparty computation (MPC) on incomplete communication networks has been studied within two primary models: (1) where a partial network is fixed a priori, and thus corruptions can occur dependent on its structure, and (2) where edges in the communication graph are determined dynamically as part of the protocol. Whereas a rich literature has succeeded in mapping out the feasibility and limitations of graph structures supporting secure computation in the fixed-graph model (including strong classical lower bounds), these bounds do not apply in the latter dynamic-graph setting, which has recently seen exciting new results, but remains relatively unexplored. In this work, we initiate a similar foundational study of MPC within the dynamic-graph model. As a first step, we investigate the property of graph expansion . All existing protocols (implicitly or explicitly) yield communication graphs which are expanders, but it is not clear whether this is inherent. Our results consist of two types (for constant fraction of corruptions): Upper bounds: We demonstrate secure protocols whose induced communication graphs are not expander graphs, within a wide range of settings (computational, information theoretic, with low locality, even with low locality and adaptive security), each assuming some form of input-independent setup. Lower bounds: In the plain model (no setup) with adaptive corruptions, we demonstrate that for certain functionalities, no protocol can maintain a non-expanding communication graph against all adversarial strategies. Our lower bound relies only on protocol correctness (not privacy) and requires a surprisingly delicate argument. More generally, we provide a formal framework for analyzing the evolving communication graph of MPC protocols, giving a starting point for studying the relation between secure computation and further, more general graph properties.

We give a construction of a non-interactive zero-knowledge (NIZK) argument for all $${\textsf{NP}}$$ NP languages based on a succinct non-interactive argument (SNARG) for all $${\textsf{NP}}$$ NP languages and a one-way function. The succinctness requirement for the SNARG is rather mild: We only require that the proof size be $$|\pi |={\textsf{poly}}(\lambda )(|x|+|w|)^\delta $$ | π | = poly ( λ ) ( | x | + | w | ) δ for some constant $$\delta <1$$ δ < 1 , where | x | is the statement length, | w | is the witness length, and $$\lambda $$ λ is the security parameter. Especially, we do not require the efficiency of the verification to be sublinear in | x | or | w |. As a corollary, we give a generic conversion from a SNARK to a zero-knowledge SNARG assuming the existence of one-way functions where SNARK is a SNARG with knowledge-extractability. For this conversion, we require the SNARK to be fully succinct, i.e., the proof size is $${\textsf{poly}}(\lambda )(|x|+|w|)^{o(1)}$$ poly ( λ ) ( | x | + | w | ) o ( 1 ) . Before this work, such a conversion was only known if we additionally assume the existence of a NIZK. Along the way of obtaining our result, we give a generic compiler to upgrade a NIZK for all $${\textsf{NP}}$$ NP languages with non-adaptive zero-knowledge to one with adaptive zero-knowledge. Though this can be shown by carefully combining known results, to the best of our knowledge, no explicit proof of this generic conversion has been presented.

In this paper, we give a no-signaling linear probabilistically checkable proof (PCP) system for polynomial-time deterministic computation, i.e., a PCP system for $$\mathcal {P}$$ P such that (1) the honest PCP oracle is a linear function and (2) the soundness holds against any (computational) no-signaling cheating prover, who is allowed to answer each query according to a distribution that depends on the entire query set in a certain way. To the best of our knowledge, our construction is the first PCP system that satisfies these two properties simultaneously. As an application of our PCP system, we obtain a 2-message delegating computation scheme by using a known transformation. Compared with the existing 2-message delegating computation schemes that are based on standard cryptographic assumptions, our scheme requires preprocessing but has a simpler structure and makes use of different (possibly cheaper) standard cryptographic primitives, namely additive/multiplicative homomorphic encryption schemes.

Vector commitments (VCs), enabling to commit to a vector and locally reveal any of its entries, play a key role in a variety of both classic and recently evolving applications. However, security notions for VCs have so far focused on passive attacks, and non-malleability notions considering active attacks have not been explored. Moreover, existing frameworks that may enable to capture the non-malleability of VCs seem either too weak (non-malleable non-interactive commitments that do not account for the security implications of local openings) or too strong (non-malleable zero-knowledge sets that support both membership and non-membership proofs). We put forward a rigorous framework capturing the non-malleability of VCs, striking a careful balance between the existing weaker and stronger frameworks: We strengthen the framework of non-malleable non-interactive commitments by considering attackers that may be exposed to local openings, and we relax the framework of non-malleable zero-knowledge sets by focusing on membership proofs. In addition, we strengthen both frameworks by supporting (inherently private) updates to entries of committed vectors, and discuss the benefits of non-malleable VCs in the context of both UTXO-based and account-based stateless blockchains, and in the context of simultaneous multi-round auctions (that have been adopted by the US Federal Communications Commission as the standard auction format for selling spectrum ranges). Within our framework, we present a direct approach for constructing non-malleable VCs whose efficiency essentially matches that of the existing standard VCs. Specifically, we show that any VC can be transformed into a non-malleable one, relying on a new primitive that we put forth. Our new primitive, locally equivocable commitments with all-but-one binding , is evidently both conceptually and technically simpler compared to multi-trapdoor mercurial trapdoor commitments (the main building block underlying existing non-malleable zero-knowledge sets), and admits more efficient instantiations based on the same number-theoretic assumptions.

We present the first Oblivious RAM (ORAM) construction that for N memory blocks supports accesses with worst-case $$O(\log N)$$ O ( log N ) overhead for any block size $$\Omega (\log N)$$ Ω ( log N ) while requiring a client memory of only a constant number of memory blocks. We rely on the existence of one-way functions and guarantee computational security. Our result closes a long line of research on fundamental feasibility results for ORAM constructions as logarithmic overhead is necessary. The previous best logarithmic overhead construction only guarantees it in an amortized sense, i.e., logarithmic overhead is achieved only for long enough access sequences, where some of the individual accesses incur $$\Theta (N)$$ Θ ( N ) overhead. The previously best ORAM in terms of worst-case overhead achieves $$O(\log ^2 N/\log \log N)$$ O ( log 2 N / log log N ) overhead. Technically, we design a novel de-amortization framework for modern ORAM constructions that use the “shuffled inputs” assumption. Our framework significantly departs from all previous de-amortization frameworks, originating from Ostrovsky and Shoup (STOC’97), that seem to be fundamentally too weak to be applied on modern ORAM constructions.

Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of n mutually distrusting parties with private inputs to securely compute any publicly known function of their inputs, by keeping their respective inputs as private as possible. While several works in the past have addressed the problem of designing communication-efficient MPC protocols in the synchronous communication setting, not much attention has been paid to the design of efficient MPC protocols in the asynchronous communication setting. In this work, we focus on the design of efficient asynchronous MPC (AMPC) protocol with statistical security, tolerating a computationally unbounded adversary, capable of corrupting up to t parties out of the n parties. The seminal work of Ben-Or, Kelmer and Rabin (PODC 1994) and later Abraham, Dolev and Stern (PODC 2020) showed that the optimal resilience for statistically secure AMPC is $$t < n/3$$ t < n / 3 . Unfortunately, the communication complexity of the protocol presented by Ben-Or et al. is significantly high, where the communication complexity per multiplication is $$\Omega (n^{13} \kappa ^2 \log n)$$ Ω ( n 13 κ 2 log n ) bits (where $$\kappa $$ κ is the statistical-security parameter). To the best of our knowledge, no work has addressed the problem of improving the communication complexity of the protocol of Ben-Or et al. In this work, our main contributions are the following. We present a new statistically secure AMPC protocol with the optimal resilience $$t < n/3$$ t < n / 3 , where the communication complexity is $$\mathcal {O}(n^4 \kappa )$$ O ( n 4 κ ) bits per multiplication. Apart from improving upon the communication complexity of the protocol of Ben-Or et al., our protocol is relatively simpler and based on very few sub-protocols, unlike the protocol of Ben-Or et al. which involves several layers of sub-protocols. A central component of our AMPC protocol is a new and simple protocol for verifiable asynchronous complete secret-sharing (ACSS), which is of independent interest. As a side result, we give the security proof for our AMPC protocol in the standard universal composability (UC) framework of Canetti (FOCS 2001, JACM 2020), which is now the de facto standard for proving the security of cryptographic protocols. This is unlike the protocol of Ben-Or et al., which was missing the formal security proofs.

Fully secure multiparty computation (MPC) allows a set of parties to compute some function of their inputs, while guaranteeing correctness, privacy, fairness, and output delivery. Understanding the necessary and sufficient assumptions that allow for fully secure MPC is an important goal. Cleve (STOC’86) showed that full security cannot be obtained in general without an honest majority. Conversely, by Rabin and Ben-Or (STOC’89), assuming a broadcast channel and an honest majority enables a fully secure computation of any function. Our goal is to characterize the set of functionalities that can be computed with full security, assuming an honest majority, but no broadcast. This question was fully answered by Cohen et al. (TCC’16)—for the restricted class of symmetric functionalities (where all parties receive the same output). Instructively, their results crucially rely on agreement and do not carry over to general asymmetric functionalities. In this work, we focus on the case of three-party asymmetric functionalities, providing a variety of necessary and sufficient conditions to enable fully secure computation. An interesting use-case of our results is server-aided computation, where an untrusted server helps two parties to carry out their computation. We show that without a broadcast assumption, the resource of an external non-colluding server provides no additional power. Namely, a functionality can be computed with the help of the server if and only if it can be computed without it. For fair coin tossing, we further show that the optimal bias for three-party (server-aided) r -round protocol remains $$\Theta \left( 1/r\right) $$ Θ 1 / r (as in the two-party setting).

In theory, fully homomorphic encryption schemes allow users to compute any operation over encrypted data. However in practice, one of the major difficulties lies into determining secure cryptographic parameters that minimize the computational cost of evaluating a circuit. In this paper, we propose a solution to solve this open problem. Even though it mainly focuses on TFHE, the method is generic enough to be adapted to all the current FHE schemes. TFHE is particularly suited, for small precision messages, from Boolean to 5-bit integers. It is possible to instantiate bigger integers with this scheme; however, the computational cost quickly becomes unpractical. By studying the parameter optimization problem for TFHE, we observed that if one wants to evaluate operations on larger integers, the best way to do it is by encrypting the message into several ciphertexts, instead of considering bigger parameters for a single ciphertext. In the literature, one can find some constructions going in that direction, which are mainly based on radix and CRT representations of the message. However, they still present some limitations, such as inefficient algorithms to evaluate generic homomorphic lookup tables and no solution to work with arbitrary modulus for the message space. We overcome these limitations by proposing two new ways to evaluate homomorphic modular reductions for any modulo in the radix approach, by introducing on the one hand a new hybrid representation, and on the other hand by exploiting a new efficient algorithm to evaluate generic lookup tables on several ciphertexts. The latter is not only a programmable bootstrapping but does not require any padding bit, as needed in the original TFHE bootstrapping. We additionally provide benchmarks to support our results in practice. Finally, we formalize the parameter selection as an optimization problem, and we introduce a framework based on it enabling easy and efficient translation of an arithmetic circuit into an FHE graph of operation along with its optimal set of cryptographic parameters. This framework offers a plethora of features: fair comparisons between FHE operators, study of contexts that are favorable to a given FHE strategy/algorithm, failure probability selection for the entire use-case and so on.

Recent works showed how Mutual Information Neural Estimation (MINE) could be applied to side-channel analysis in order to evaluate the amount of leakage of an electronic device. One of the main advantages of MINE over classical estimation techniques is to enable the computation between high dimensional traces and a secret, which is relevant for leakage assessment. However, optimally exploiting this information in an attack context in order to retrieve a secret remains a non-trivial task especially when a profiling phase of the target is not allowed. Within this context, the purpose of this paper is to address this problem based on a simple idea: there are multiple leakage sources in side-channel traces and optimal attacks should necessarily exploit most/all of them. To this aim, a new mathematical framework, designed to bridge classical Mutual Information Analysis (MIA) and the multidimensional aspect of neural-based estimators, is proposed. One of the goals is to provide rigorous proofs consolidating the mathematical basis behind MIA, thus alleviating inconsistencies found in the state of the art. This framework allows to derive a new attack called Neural Estimated Mutual Information Analysis (NEMIA). To the best of our knowledge, it is the first unsupervised attack able to benefit from both the power of deep learning techniques and the valuable theoretical properties of MI. From simulations and experiments conducted in this paper, it seems that NEMIA performs better than classical and more recent deep learning based unsupervised side-channel attacks, especially in low-information contexts.

In this paper, we design unconditionally secure multi-party computation (MPC) protocols in the asynchronous communication setting with optimal resilience. Our protocols are secure against a computationally unbounded malicious adversary characterized by an adversary structure $$\mathcal {Z}$$ Z , which enumerates all possible subsets of potentially corrupt parties. We present protocols with both perfect-security , as well as with statistical-security . While the protocols in the former class achieve all the security properties in an error-free fashion, the protocols belonging to the latter category achieve all the security properties except with a negligible error. Our perfectly secure protocol incurs an amortized communication of $$\mathcal {O}(|\mathcal {Z}|^2)$$ O ( | Z | 2 ) bits per multiplication. This improves upon the protocol of Choudhury and Pappu (INDOCRYPT 2020) with the least known amortized communication complexity of $$\mathcal {O}(|\mathcal {Z}|^3)$$ O ( | Z | 3 ) bits per multiplication. On the other hand, our statistically secure protocol incurs an amortized communication of $$\mathcal {O}(|\mathcal {Z}|)$$ O ( | Z | ) bits per multiplication. This is the first statistically secure asynchronous MPC protocol against general adversaries. Previously, perfectly secure and statistically secure MPC with an amortized communication cost of $$\mathcal {O}(|\mathcal {Z}|^2)$$ O ( | Z | 2 ) and $$\mathcal {O}(|\mathcal {Z}|)$$ O ( | Z | ) bits, respectively, per multiplication was known only in the relatively simpler synchronous communication setting (Hirt and Tschudi in ASIACRYPT, Springer, 2013).

Succinct non-interactive arguments of knowledge (SNARKs) enable non-interactive efficient verification of NP computations and admit short proofs. However, all current SNARK constructions assume that the statements to be proven can be efficiently represented as either Boolean or arithmetic circuits over finite fields. For most constructions, the choice of the prime field $${\mathbb {F}}_{p}$$ F p is limited by the existence of groups of matching order for which secure bilinear maps exist. In this work, we overcome such restrictions and enable verifying computations over rings. We construct the first designated-verifier SNARK for statements which are represented as circuits over a broader kind of commutative rings. Our contribution is threefold: 1. We first introduce Quadratic Ring Programs (QRPs) as a characterization of NP where the arithmetic is over a ring. 2. Second, inspired by the framework in Gennaro et al. (in: Johansson and Nguyen (eds) EUROCRYPT 2013, volume 7881 of LNCS, pp 626–645. Springer, Heidelberg, 2013), we design SNARKs over rings in a modular way. We generalize preexistent assumptions employed in field-restricted SNARKs to encoding schemes over rings. As our encoding notion is generic in the choice of the ring, it is amenable to different settings. 3. Finally, we propose two applications for our SNARKs. Our first application is verifiable computation over encrypted data, specifically for evaluations of Ring-LWE-based homomorphic encryption schemes. In the second one, we use Rinocchio to naturally prove statements about circuits over, e.g., $${\mathbb {Z}}_{2^{64}}$$ Z 2 64 , which closely matches real-life computer architectures such as standard CPUs.

Private Stream Aggregation (PSA) protocols perform secure aggregation of time-series data without leaking information about users’ inputs to the aggregator. Previous work in post-quantum PSA used the Ring Learning with Errors (RLWE) problem indirectly via homomorphic encryption (HE), leading to a needlessly complex and intensive construction. In this work, we present SLAP, the first PSA protocol that is directly constructed from the RLWE problem to gain post-quantum security. By nature of our white-box approach, SLAP is simpler and more efficient than previous PSA that uses RLWE indirectly through the black box of HE. We also show how to apply state-of-the-art optimizations for lattice-based cryptography to greatly improve the practical performance of SLAP. The communication overhead of SLAP is much less than in previous work, with decreases of up to 99.96% in ciphertext sizes as compared to previous work in RLWE-based PSA. We demonstrate a speedup of 20.76x over the previous state-of-the-art RLWE-based PSA work’s aggregation and show that SLAP achieves a throughput of 390,691 aggregations per second for 1000 users. We also compare SLAP to other state-of-the-art post-quantum PSA and show that SLAP is comparable in latency and shows improvement in throughput when compared to these works, and we compare the qualitative features of these schemes with regards to practical usability.

Topology-hiding broadcast ( THB ) enables parties communicating over an incomplete network to broadcast messages while hiding the topology from within a given class of graphs. THB is a central tool underlying general topology-hiding secure computation ( THC ) (Moran et al. TCC’15). Although broadcast is a privacy-free task, it was recently shown that THB for certain graph classes necessitates computational assumptions, even in the semi-honest setting, and even given a single corrupted party. In this work, we investigate the minimal assumptions required for topology-hiding communication: both Broadcast or Anonymous Broadcast (where the broadcaster’s identity is hidden). We develop new techniques that yield a variety of necessary and sufficient conditions for the feasibility of THB / THAB in different cryptographic settings: information theoretic, given existence of key agreement, and given existence of oblivious transfer. Our results show that feasibility can depend on various properties of the graph class, such as connectivity , and highlight the role of different properties of topology when kept hidden, including direction , distance , and/or distance-of-neighbors to the broadcaster. An interesting corollary of our results is a dichotomy for THC with a public number of at least three parties, secure against one corruption: information-theoretic feasibility if all graphs are 2-connected; necessity and sufficiency of key agreement otherwise.

Predicate inner product functional encryption (P-IPFE) is essentially attribute-based IPFE (AB-IPFE) which additionally hides attributes associated to ciphertexts. In a P-IPFE, a message $${\textbf {x}}$$ x is encrypted under an attribute $${\textbf {w}}$$ w and a secret key is generated for a pair $$({\textbf {y}}, {\textbf {v}})$$ ( y , v ) such that recovery of $$\langle {{\textbf {x}}}, {{\textbf {y}}}\rangle $$ ⟨ x , y ⟩ requires the vectors $${\textbf {w}}, {\textbf {v}}$$ w , v to satisfy a linear relation. We call a P-IPFE unbounded if it can encrypt unbounded length attributes and message vectors. $$\bullet $$ ∙ zero predicate IPFE . We construct the first unbounded zero predicate IPFE (UZP-IPFE) which recovers $$\langle {{\textbf {x}}}, {{\textbf {y}}}\rangle $$ ⟨ x , y ⟩ if $$\langle {{\textbf {w}}}, {{\textbf {v}}}\rangle =0$$ ⟨ w , v ⟩ = 0 . This construction is inspired by the unbounded IPFE of Tomida and Takashima (ASIACRYPT 2018) and the unbounded zero inner product encryption of Okamoto and Takashima (ASIACRYPT 2012). The UZP-IPFE stands secure against general attackers capable of decrypting the challenge ciphertext. Concretely, it provides full attribute-hiding security in the indistinguishability-based semi-adaptive model under the standard symmetric external Diffie–Hellman assumption. $$\bullet $$ ∙ non-zero predicate IPFE . We present the first unbounded non-zero predicate IPFE (UNP-IPFE) that successfully recovers $$\langle {{\textbf {x}}}, {{\textbf {y}}}\rangle $$ ⟨ x , y ⟩ if $$\langle {{\textbf {w}}}, {{\textbf {v}}}\rangle \ne 0$$ ⟨ w , v ⟩ ≠ 0 . We generically transform an unbounded quadratic FE (UQFE) scheme to weak attribute-hiding UNP-IPFE in both public and secret key setting. Interestingly, our secret key simulation secure UNP-IPFE has succinct secret keys and is constructed from a novel succinct UQFE that we build in the random oracle model. We leave the problem of constructing a succinct public key UNP-IPFE or UQFE in the standard model as an important open problem.

An accumulator is a function that hashes a set of inputs into a short, constant-size string while preserving the ability to efficiently prove the inclusion of a specific input element in the hashed set. It has proved useful in the design of numerous privacy-enhancing protocols, in order to handle revocation or simply prove set membership. In the lattice setting, currently known instantiations of the primitive are based on Merkle trees, which do not interact well with zero-knowledge proofs. In order to efficiently prove the membership of some element in a zero-knowledge manner, the prover has to demonstrate knowledge of a hash chain without revealing it, which is not known to be efficiently possible under well-studied hardness assumptions. In this paper, we provide an efficient method of proving such statements using involved extensions of Stern’s protocol. Under the Small Integer Solution assumption, we provide zero-knowledge arguments showing possession of a hash chain. As an application, we describe new lattice-based group and ring signatures in the random oracle model. In particular, we obtain: (i) the first lattice-based ring signatures with logarithmic size in the cardinality of the ring and (ii) the first lattice-based group signature that does not require any GPV trapdoor and thus allows for a much more efficient choice of parameters.