International Association
for Cryptologic Research

Secure computation often benefits from the use of correlated randomness to achieve fast, non-cryptographic online protocols. A recent paradigm put forth by Boyle $\textit{et al.}$ (CCS 2018, Crypto 2019) showed how pseudorandom correlation generators (PCG) can be used to generate large amounts of useful forms of correlated (pseudo)randomness, using minimal interactions followed solely by local computations, yielding silent secure two-party computation protocols (protocols where the preprocessing phase requires almost no communication). Furthermore, programmable PCG's can be used similarly to generate multiparty correlated randomness to be used in silent secure N-party protocols. Previous works constructed very efficient (non-programmable) PCG's for correlations such as random oblivious transfers. However, the situation is less satisfying for the case of random oblivious linear evaluation (OLE), which generalises oblivious transfers over large fields, and are a core resource for secure computation of arithmetic circuits. The state-of-the-art work of Boyle $\textit{et al.}$ (Crypto 2020) constructed programmable PCG's for OLE, but their work suffers from two important downsides: (1) it only generates OLE's over large fields, and (2) it relies on relatively new "splittable" ring-LPN assumption, which lacks strong security foundations.

In this work, we construct new programmable PCG's for the OLE correlation, that overcome both limitations. To this end, we introduce the quasi-abelian syndrome decoding problem (QA-SD), a family of assumptions which generalises the well-established quasi-cyclic syndrome decoding assumption. Building upon QA-SD, we construct new programmable PCG's for OLE's over any field $\mathbb{F}_q$ with $q>2$. Our analysis also sheds light on the security of the ring-LPN assumption used in Boyle $\textit{et al.}$ (Crypto 2020). Using our new PCG's, we obtain the first efficient N-party silent secure computation protocols for computing general arithmetic circuit over $\mathbb{F}_q$ for any $q>2$.

Inspired by the advancements in (fully) homomorphic encryption during the last decades and its practical applications, we conduct a preliminary study on the underlying mathematical structure of the corresponding schemes. Hence, this paper focuses on investigating the challenge of deducing bivariate polynomials constructed using homomorphic operations, namely repetitive additions and multiplications.

To begin with, we introduce an approach for solving the previously mentioned problem using Lagrange interpolation for the evaluation of univariate polynomials. This method is well-established for determining univariate polynomials that satisfy a specific set of points. Moreover, we propose a second approach based on modular knapsack resolution algorithms. These algorithms are designed to address optimization problems where a set of objects with specific weights and values is involved. Finally, we give recommendations on how to run our algorithms in order to obtain better results in terms of precision.

WhatsApp is an end-to-end encrypted (E2EE) messaging service used by billions of people. In late 2021, WhatsApp rolled out a new protocol for backing up chat histories. The E2EE WhatsApp backup protocol (WBP) allows users to recover their chat history from passwords, leaving WhatsApp oblivious of the actual encryption keys. The WBP builds upon the OPAQUE framework for password-based key exchange, which is currently undergoing standardization. While considerable efforts have gone into the design and auditing of the WBP, the complexity of the protocol’s design and shortcomings in the existing security analyses of its building blocks make it hard to understand the actual security guarantees that the WBP provides. In this work, we provide the first formal security analysis of the WBP. Our analysis in the universal composability (UC) framework confirms that the WBP provides strong protection of users’ chat history and passwords. It also shows that a corrupted server can under certain conditions make more password guesses than what previous analysis suggests.

Differential obliviousness (DO) is a privacy notion which mandates that the access patterns of a program satisfy differential privacy. Earlier works have shown that in numerous applications, differential obliviousness allows us to circumvent fundamental barriers pertaining to fully oblivious algorithms, resulting in asymptotical (and sometimes even polynomial) performance improvements. Although DO has been applied to various contexts, including the design of algorithms, data structures, and protocols, its compositional properties are not explored until the recent work of Zhou et al. (Eurocrypt'23). Specifically, Zhou et al. showed that the original DO notion is not composable. They then proposed a refinement of DO called neighbor-preserving differential obliviousness (NPDO), and proved a basic composition for NPDO.

In Zhou et al.'s basic composition theorem for NPDO, the privacy loss is linear in $k$ for $k$-fold composition. In comparison, for standard differential privacy, we can enjoy roughly $\sqrt{k}$ loss for $k$-fold composition by applying the well-known advanced composition theorem. Therefore, a natural question left open by their work is whether we can also prove an analogous advanced composition for NPDO.

In this paper, we answer this question affirmatively. As a key step in proving an advanced composition theorem for NPDO, we define a more operational notion called symmetric NPDO which we prove to be equivalent to NPDO. Using symmetric NPDO as a stepping stone, we also show how to generalize NPDO to more general notions of divergence, resulting in Rényi-NPDO, zero-concentrated NPDO, Gassian-NPDO, and $g$-NPDO notions. We also prove composition theorems for these generalized notions of NPDO.

We report on a new class of ECDSA signature vulnerability observed in the wild on the Bitcoin blockchain that results from a signature nonce generated by concatenating half of the bits of the message hash together with half of the bits of the secret signing key. We give a lattice-based attack for efficiently recovering the secret key from a single signature of this form. We then search the entire Bitcoin blockchain for such signatures, and identify and track the activities of an apparently custom ECDSA/Bitcoin implementation that has been used to empty hundreds of compromised Bitcoin addresses for many years.

The sum of two $n$-bit pseudorandom permutations is known to behave like a pseudorandom function with $n$ bits of security. A recent line of research has investigated the security of two public $n$-bit permutations and its degree of indifferentiability. Mandal et al. (INDOCRYPT 2010) proved $2n/3$-bit security, Mennink and Preneel (ACNS 2015) pointed out a non-trivial flaw in their analysis and re-proved $(2n/3-\log_2(n))$-bit security. Bhattacharya and Nandi (EUROCRYPT 2018) eventually improved the result to $n$-bit security. Recently, Gunsing at CRYPTO 2022 already observed that a proof technique used in this line of research only holds for sequential indifferentiability. We revisit the line of research in detail, and observe that the strongest bound of $n$-bit security has two other serious issues in the reasoning, the first one is actually the same non-trivial flaw that was present in the work of Mandal et al., while the second one discards biases in the randomness influenced by the distinguisher. More concretely, we introduce two attacks that show limited potential of different approaches. We (i) show that the latter issue that discards biases only holds up to $2^{3n/4}$ queries, and (ii) perform a differentiability attack against their simulator in $2^{5n/6}$ queries. On the upside, we revive the result of Mennink and Preneel and show $(2n/3-\log_2(n))$-bit regular indifferentiability security of the sum of public permutations.

Secure multiparty computation protocols with dynamic parties, which assume that honest parties do not need to be online throughout the whole execution of the protocol, have recently gained a lot of traction for computations of large scale distributed protocols, such as blockchains. More specifically, in Fluid MPC, introduced in (Choudhuri et al. CRYPTO 2021), parties can dynamically join and leave the computation from round to round. The best known Fluid MPC protocol in the honest majority setting communicates $O(n^2)$ elements per gate where $n$ is the number of parties online at a time. While Le Mans (Rachuri and Scholl, CRYPTO 2022) extends Fluid MPC to the dishonest majority setting with preprocessing, it still communicates $O(n^2)$ elements per gate.

In this work we present alternative Fluid MPC solutions that require $O(n)$ communication per gate for both the information-theoretic honest majority setting and the information-theoretic dishonest majority setting with preprocessing. Our solutions also achieve maximal fluidity where parties only need to be online for a single communication round. Additionally, we show that a protocol in the information-theoretic dishonest majority setting with sub-quadratic $o(n^2)$ overhead per gate requires for each of the $N$ parties who may ever participate in the (later) execution phase, $\Omega(N)$ preprocessed data per gate.

Motivated by applications in threshold cryptography, we initiate the study of secret-sharing schemes that distribute a secret from a large field $F_p$ among $n$ parties such that the recovery algorithm makes a minimal number of \emph{additions}. Existing schemes achieve either $O(n\log p)$ additions (e.g., Shamir, Comm. of ACM, 1979) or at least $\Omega(n^2)$ operations independently of the field size (e.g., Cramer-Xing, EUROCRYPT, 2020). This leaves open the existence of a secret sharing whose recovery algorithm can be computed by performing only $O(n)$ additions.

We resolve the question in the affirmative and present such a near-threshold secret sharing scheme that provides privacy against unauthorized sets of density at most $\tau_p$, and correctness for authorized sets of density at least $\tau_c$, for any given arbitrarily close constants $\tau_p<\tau_c$. Reconstruction can be computed by making at most $O(n)$ additions and, in addition, (1) the share size is constant, (2) the sharing procedure also makes $O(n)$ additions, and (3) the scheme is a blackbox secret-sharing scheme, i.e., the sharing and reconstruction algorithms work universally for all finite abelian groups $\mathbb{G}$. Prior to our work, no such scheme was known even without features (1)--(3) and even for the ramp setting where $\tau_p$ and $\tau_c$ are far apart. As a by-product, we derive the first blackbox near-threshold secret-sharing scheme with linear-time sharing. We also present several concrete instantiations of our approach that seems practically efficient (e.g., for threshold discrete-log-based signatures).

Our constructions are combinatorial in nature. We combine graph-based erasure codes that support ``peeling-based'' decoding with a new randomness extraction for low dimensional sub-space that is based on inner-product with a small-integer vector. By combining these tools with the blueprint of Cramer et al. (EUROCRYPT 2015), we derive efficient secret-sharing scheme with far-apart thresholds. We then introduce a general concatenation-like transform for secret-sharing schemes that allows us to arbitrarily shrink the privacy-correctness gap with a minor overhead. Our techniques enrich the secret-sharing toolbox and, in the context of blackbox secret sharing, provide a new alternative to existing number-theoretic approaches.

Coercion-resistance is one of the most challenging security properties to achieve when designing an e-voting protocol. The JCJ voting scheme, proposed in 2005 by Juels, Catalano and Jakobsson, is one of the first voting systems where coercion-resistance was rigorously defined and achieved, making JCJ the benchmark for coercion-resistant protocols. Recently, the coercion-resistance definition proposed in JCJ has been disputed and improved by Cortier, Gaudry, and Yang. They identified a major problem, related to leakage of the number of discarded votes by revoting; and proposed CHide, a new protocol that solves the issue and satisfies a stronger security notion. In this work we present an improved version of CHide, with complexity $O(n\log n)$ instead of $O(n^2)$ in the number $n$ of received ballots, that relies on sorting encrypted ballots to make the tallying phase faster. The asymptotic complexity of our protocol is competitive with other state-of-the-art coercion-resistant voting protocols satisfying the stronger notion for coercion resistance.

Attribute-Based Encryption (ABE) is a very attractive primitive to limit access according to specific rights. While very powerful instantiations have been offered, under various computational assumptions, they rely on either classical or post-quantum problems, and are quite intricate to implement, generally resulting in poor efficiency; the construction we offer results in a powerful efficiency gap with respect to existing solutions.

With the threat of quantum computers, post-quantum solutions are important, but not yet tested enough to rely on such problems only. We thus first study an hybrid approach to rely on the best of the two worlds: the scheme is secure if at least one of the two underlying assumptions is still valid (i.e. the DDH and LWE).

Then, we address the ABE problem, with a practical solution delivering encrypted contents such that only authorized users can decrypt, without revealing the target sets, while also granting tracing capabilities. Our scheme is inspired by the Subset Cover framework where the users' rights are organized as subsets and a content is encrypted with respect to a subset covering of the target set.

Quite conveniently, we offer black-box modularity: one can easily use any public-key encryption of their choice, such as Kyber, with their favorite library, to combine it with a simple ElGamal variant of key encapsulation mechanisms, providing strong security guarantees.

The masking countermeasure is often analyzed in the probing model. Proving the probing security of large circuits at high masking orders is achieved by composing gadgets that satisfy security definitions such as non-interference (NI), strong non-interference (SNI) or free SNI. The region probing model is a variant of the probing model, where the probing capabilities of the adversary scale with the number of regions in a masked circuit. This model is of interest as it allows better reductions to the more realistic noisy leakage model. The efficiency of composable region probing secure masking has been recently improved with the introduction of the input-output separation (IOS) definition.

In this paper, we first establish equivalences between the non-interference framework and the IOS formalism. We also generalize the security definitions to multiple-input gadgets and systematically show implications and separations between these notions. Then, we study which gadgets from the literature satisfy these. We give new security proofs for some well-known arbitrary-order gadgets, and also some automated proofs for fixed-order, special-case gadgets. To this end, we introduce a new automated formal verification algorithm that solves the open problem of verifying free SNI, which is not a purely simulation-based definition. Using the relationships between the security notions, we adapt this algorithm to further verify IOS. Finally, we look at composition theorems. In the probing model, we use the link between free SNI and the IOS formalism to generalize and improve the efficiency of the tight private circuit (Asiacrypt 2018) construction, also fixing a flaw in the original proof. In the region probing model, we relax the assumptions for IOS composition (TCHES 2021), which allows to save many refresh gadgets, hence improving the efficiency.

The Number Field Sieve and its variants are the best algorithms to solve the discrete logarithm problem in finite fields. The Factory variant accelerates the computation when several prime fields are targeted. This article adapts the Factory variant to non-prime finite fields of medium and large characteristic. We combine this idea with two other variants of NFS, namely the tower and special variant. This combination leads to improvements in the asymptotic complexity. Besides, we lay out estimates of the practicality of this method for 1024-bit targets and extension degree $6$.

A proxy signature enables a party to delegate her signing power to another. This is useful in practice to achieve goals related to robustness, crowd-sourcing, and workload sharing. Such applications usually require delegation to satisfy several properties, including time bounds, anonymity, revocability, and policy enforcement. Despite the large amount of work on proxy signatures in the literature, none of the existing schemes satisfy all these properties; even there is no unified formal notion that captures them.

In this work, we close this gap and propose an anonymous, timed, and revocable proxy signature scheme. We achieve this in two steps: First, we introduce a tokenizable digital signature based on Schnorr signature allowing for secure distribution of signing tokens (which could be of independent interest). Second, we utilize a public bulletin board and timelock encryption to support: (1) one-time usage of the signing tokens by tracking tokens used so far based on unique values associated to them, (2) timed delegation so that a proxy signer cannot sign outside a given period, and (3) delegation revocation allowing the original signer to end a delegation earlier than provisioned. All of these are done in a decentralized and anonymous way; no trusted party is involved, and no one can tell that someone else signed on behalf of the original signer or even that a delegation took place. We define a formal notion for proxy signatures capturing all these properties, and prove that our construction realizes this notion. We also introduce several design considerations addressing issues related to deployment in practice.

The security and usability of cryptocurrencies and other blockchain-based applications depend on the secure management of cryptographic keys. However, current approaches for managing these keys often rely on third parties, trusted to be available at a minimum, and even serve as custodians in some solutions, creating single points of failure and limiting the ability of users to fully control their own assets. In this work, we introduce the concept of unstoppable wallets, which are programmable threshold ECDSA wallets that allow users to co-sign transactions with a confidential smart contract, rather than a singular third-party. We propose a new model that encapsulates the use of a confidential smart contract as both a party and the sole (broadcast) communication channel in secure Multi-Party Computation (MPC) protocols. We construct highly efficient threshold ECDSA protocols that form the basis of unstoppable wallets and prove their security under this model, achieving the standard notion of fairness and robustness even in case of a dishonest majority of signers. Our protocols minimize the write-complexity for threshold ECDSA key-generation and signing, while reducing communication and computation overhead. We implement these protocols as smart contracts, deploy them on Secret Network, and showcase their applicability for two interesting applications, policy checking and wallet exchange, as well as their efficiency by demonstrating low gas costs and fees.

Masking is considered to be an essential defense mechanism against side-channel attacks, but it is challenging to be adopted for hardware cryptographic implementations, especially for high-security orders. Recently, Knichel et al. proposed an automated tool called AGEMA that enables the generation of masked implementations in hardware for arbitrary security orders using composable gadgets. This accelerates the construction and practical application of masking schemes. This article proposes a new automated tool named AGEMA$^+$ that can generate masked implementations with much better performance. The effectiveness of AGEMA$^+$ is evaluated in several case studies. The evaluation results show a significant performance improvement, particularly for the first-order secure SKINNY S-box: saving 41$ \% $ area, 25$ \% $ latency, and 49$ \% $ dynamic power. We achieve such a good result by integrating three key techniques: a new composable AND-XOR gadget, an optimization strategy based on the latency asymmetry feature of the AND-XOR gadget, and an implementation optimization for synchronization. Besides, we use the formal verification tool SILVER and FPGA-based practical experiments to confirm the security of the masked implementations generated by AGEMA$^+$.

The article introduces HPPC a new Digital Signature scheme that intends to resist known previous attacks applied to HFE-based schemes like QUARTZ and GeMMS. The idea is to use maximal degree for the central HFE polynomial whereas the trapdoor polynomial has low degree in order to sign messages by finding polynomial roots in an extension field via Berlekamp's algorithm. This work has been submitted to NIST's Post-Quantum Cryptography challenge (PQC) and code is available at https://github.com/kub0x/MPKC-HPPC

Trusted Execution Environments (TEEs) suffer from performance issues when executing certain management instructions, such as creating an enclave, context switching in and out of protected mode, and swapping cached pages. This is especially problematic for short-running, interactive functions in Function-as-a-Service (FaaS) platforms, where existing techniques to address enclave overheads are insufficient. We find FaaS functions can spend more time managing the enclave than executing application instructions. In this work, we propose a TEE/GC hybrid (TGh) protocol to enable confidential FaaS platforms. TGh moves computation out of the enclave onto the untrusted host using garbled circuits (GC), a cryptographic construction for secure function evaluation. Our approach retains the security guarantees of enclaves while avoiding the performance issues associated with enclave management instructions.

For computing square roots in a finite field $GF(q)$ where $q - 1 = 2^n m$ for an odd integer $m$ and some integer $n$, the classic Tonelli-Shanks algorithm starts with an exponentiation (the exponent has size about $\log_2 q - n$ bits), followed by a discrete logarithm computation in the subgroup of $2^n$-th roots of unity in $GF(q)$; the latter operation has cost $O(n^2)$ multiplications in the field, which is prohibitive when $n$ is large. Bernstein proposed an optimized variant with lookup tables, leading to a runtime cost of $O((n/w)^2)$, using $w$-bit tables of cumulative size $O(2^w n/w)$. Sarkar recently improved on the runtime cost, down to $O((n/w)^{1.5})$, with the same overall storage cost. In this short note, we explore the use of a straightforward divide-and-conquer variant of the Pohlig-Hellman algorithm, bringing the asymptotic cost down to $O(n\log n)$, and further study some additional optimizations. The result appears to be competitive, at least in terms of number of multiplications, for some well-known fields such that the 224-bit field used in NIST standard elliptic curve P-224 (for which $n = 96$).

Recently, significant progress has been made toward quantumly secure multi-party computation (MPC) in the stand-alone setting. In sharp contrast, the picture of concurrently secure MPC (or even 2PC), for both classical and quantum functionalities, still remains unclear. Quantum information behaves in a fundamentally different way, making the job of adversary harder and easier at the same time. Thus, it is unclear if the positive or negative results from the classical setting still apply. This work initiates a systematic study of concurrent secure computation in the quantum setting. We obtain a mix of positive and negative results.

We first show that assuming the existence of post-quantum one-way functions (PQ-OWFs), concurrently secure 2PC (and thus MPC) for quantum functionalities is impossible. Next, we focus on the bounded-concurrent setting, where we obtain simulation-sound zero-knowledge arguments for both NP and QMA, assuming PQ-OWFs. This is obtained by a new design of simulation-sound gadget, relying on the recent post-quantum non-malleable commitments by Liang, Pandey, and Yamakawa [arXiv:2207.05861], and the quantum rewinding strategy recently developed by Ananth, Chung, and La Placa [CRYPTO'21] for bounded-concurrent post-quantum ZK.

Moreover, we show that our technique is general enough---It also leads to quantum-secure bounded-concurrent coin-flipping protocols, and eventually general-purpose 2PC and MPC, for both classical and quantum functionalities. All these constructions can be based on the quantum hardness of Learning with Errors.

This paper studies the hardness of decision Module Learning with Errors (\MLWE) under linear leakage, which has been used as a foundation to derive more efficient lattice-based zero-knowledge proofs in a recent paradigm of Lyubashevsky, Nguyen, and Seiler (PKC 21). Unlike in the plain \LWE~setting, it was unknown whether this problem remains provably hard in the module/ring setting.

This work shows a reduction from the search \MLWE~to decision \MLWE~with linear leakage. Thus, the main problem remains hard asymptotically as long as the non-leakage version of \MLWE~is hard. Additionally, we also refine the paradigm of Lyubashevsky, Nguyen, and Seiler (PKC 21) by showing a more fine-grained tradeoff between efficiency and leakage. This can lead to further optimizations of lattice proofs under the paradigm.