Threshold ECDSA schemes distribute the capability of issuing signatures to multiple parties. They have been used in practical MPC wallets holding cryptocurrencies. However, most prior protocols are not robust, wherein even one misbehaving or non-responsive party would mandate an abort. Robust schemes have been proposed (Wong et al., NDSS ’23, ’24), but they do not match state-of-the-art number of rounds which is only three (Doerner et al., S&P ’24). In this work, we propose robust threshold ECDSA schemes RompSig-Q and RompSig-L that each take three rounds (where the first two are broadcasts, whereas the non-robust scheme of Doerner et al. uses no broadcasts). Building on the works of Wong et al. and further optimized towards saving bandwidth, they respectively take each signer (1.0t+ 1.6) KiB and 3.0 KiB outbound broadcast communication, and thus exhibit bandwidth efficiency that is competitive in practical scenarios where broadcasts are natively handled. RompSig-Q preprocesses multiplications and features fast online signing; RompSig-L leverages threshold CL encryption for scalability and dynamic participation.

Threshold signatures, especially ECDSA, enhance key protection by addressing the single-point-of-failure issue. Threshold signing can be divided into offline and online phases, based on whether the message is required. Schemes with low-cost online phases are referred to as “online-friendly”. Another critical aspect of threshold ECDSA for real-world applications is robustness, which guarantees the successful completion of each signing execution whenever a threshold number$t$of semi-honest participants is met, even in the presence of misbehaving signatories. The state-of-the-art online-friendly threshold ECDSA with-out robustness was developed by Doerner et al. in S&P'24, requiring only three rounds. Recent work by Wong et al. in NDSS'23 (WMY+23) and NDSS'24 (WMC24) achieves robustness but demands additional communication rounds (7 and 4, respectively) or incurs costly operations in the online phase, such as computations over a homomorphic encryption scheme. This paper presents the first three-round threshold ECDSA scheme with both robustness and an online-friendly design. The online phase of our scheme relies solely on several elliptic-curve group operations, which are 2 to 3 orders of magnitude less computationally intensive than those based on linearly homomorphic encryption schemes. We implement our protocol and conduct a comprehensive comparison with WMY+23 and WMC24. Benchmark results show that the online phase of our scheme is 2.5x faster than that of WMY+23 and hundreds of times faster than that of WMC24. Lastly, we demonstrate that our techniques can be extended to construct an online-friendly and robust three-round threshold BBS + scheme.

Secure and efficient data sharing is essential in cloud environments, where data owners must delegate decryption rights without re-encrypting data for each user. Proxy Re-Encryption (PRE) addresses this by allowing a proxy to transform ciphertexts for authorized recipients without accessing the plaintext. As a variant, Attribute-Based Conditional PRE (AB-CPRE) enhances traditional PRE by incorporating two key features: (1) attribute-based access control, and (2) conditional ciphertext transformation based on a specified policy. Despite significant advancements, existing AB-CPRE schemes face a trilemma in balancing functionality and security, hindering their use in cloud data-sharing: (1) support limited to single-hop re-encryption, restricting multi-hop scenarios; (2) a weak security model relying on selective security without allowing the adversary to choose the target attributes or policies adaptively; and (3) an insufficient security guarantee only targeting chosen plaintext attacks (CPA), offering no protection against honest re-encryption attacks (HRA).In this paper, we propose the first AB-CPRE scheme tailored to the cloud environment that simultaneously supports multi-hop transformation, adaptive-policy security, and resistance to HRA. Our construction is based on the learning with errors (LWE) assumption in the standard model, making it also quantum-resistant. We prove security through a novel re-encryption key simulatability technique, allowing the simulation of the re-encryption key without knowing the corresponding secret key, which is of independent interest. Through a comprehensive performance comparison, our scheme demonstrates a lower decryption overhead and a comparable re-encryption key size, showing its practicality compared to the state-of-the-art schemes while offering stronger security and functionality.

The Paillier cryptosystem is renowned for its applications in electronic voting, threshold ECDSA, multi-party computation, and more, largely due to its additive homomorphism. In these applications, range proofs for the Paillier cryptosystem are crucial for maintaining security, because of the mismatch between the message space in the Paillier system and the operation space in application scenarios.

We present an efficient zero-knowledge argument of knowledge system customized for the Paillier cryptosystem. Our system enjoys sublinear proof size, low verification cost, and acceptable proof generation effort, while also supporting batch proof generation/verification. Existing works specialized for Paillier cryptosystem feature linear proof size and verification time. Using existing sublinear argument systems for generic statements (e.g., zk-SNARK) results in unaffordable proof generation cost since it involves translating the relations to be proven into an inhibitive large Boolean or arithmetic circuit over a prime order field. Our system does not suffer from these limitations.The core of our argument systems is a constraint system defined over the ring of residue classes modulo a composite number, together with novel techniques tailored for arguing binary values in this setting. We then adapt the approach from Bootle et al. (EUROCRYPT 2016) to compile the constraint system into a sublinear argument system. Our constraint system is generic and can be used to express typical relations in Paillier cryptosystems including range proof, correctness proof, relationships between bits of plaintext, relationships of plaintexts among multiple ciphertexts, and more. Our argument supports batch proof generation and verification, with the amortized cost outperforming state-of-the-art protocol specialized for Paillier when the number of Paillier ciphertext is in the order of hundreds.We report an end-to-end prototype and conduct comprehensive experiments across multiple scenarios. Scenario 1 is Paillier with packing. When we pack 25.6K bits into 400 ciphertexts, a proof that all these ciphertexts are correctly computed is 17 times smaller and is 3 times faster to verify compared with the naive implementation: using 25.6K OR-proofs without packing. Furthermore, we can prove additional statements almost for free, e.g., one can prove that the sum of a subset of the witness bits is less than a threshold t. Another scenario is range proof. To prove that each plaintext in 200 Paillier ciphertexts is of size 256 bits, our proof size is 10 times smaller than the state-of-the-art. Our analysis suggests that our system is asymptotically more efficient than existing protocols, and is highly suitable for scenarios involving a large number (more than 100) of Paillier ciphertexts, which is often the case for data analytics applications.

Private Set Intersection (PSI) protocols can securely compute the intersection of the private sets on the server and the client without revealing additional data. This work introduces the concept of Privacy-Preserving Feature Retrieved Private Set Intersection ($\mathsf {P^{2}FRPSI}$). In$\mathsf {P^{2}FRPSI}$protocols, the client can obtain the intersection that satisfies a given predicate without revealing the predicate and additional data. We formally define the$\mathsf {P^{2}FRPSI}$protocol, including its inputs, outputs, functionality, and security. To achieve the privacy guarantee in$\mathsf {P^{2}FRPSI}$protocols, a new two-party protocol is designed, namely Secure Secret Shared Retrieval ($\mathsf {S^{3}R}$), which can be used to securely determine whether each item on the server satisfies the predicate. We construct an$\mathsf {S^{3}R}$protocol and prove its security in the semi-honest model. On the basis of this, we design an efficient OT-based$\mathsf {P^{2}FRPSI}$protocol and an easy-to-implement DH-based$\mathsf {P^{2}FRPSI}$protocol and prove that they are secure in the semi-honest model. Our implementation shows that the OT-based$\mathsf {P^{2}FRPSI}$protocol can perform the matching for about 1000K items in 3.8 seconds with a single thread. Moreover, the DH-based$\mathsf {P^{2}FRPSI}$can perform the matching for about 7000K items in one hour with four threads, with communication totaling 1456 MB, while the OT-based$\mathsf {P^{2}FRPSI}$protocol requires 1673 MB.

A Verifiably Encrypted Signature (VES) scheme encrypts a digital signature in a way that allows the public to verify the validity of the encrypted signature. Recently, several practical VES schemes for ECDSA have been proposed to enable escrowed transactions with cryptocurrencies. However, these schemes are inefficient in terms of both communication and computation, or require a large lookup table. In this paper, we present two efficient VES schemes for ECDSA that improve upon previous work. The first scheme is based on Castagnos-Laguillaumie (CL) encryption, while the second is based on modified Joye-Libert (JL) encryption. Our benchmark shows that our schemes outperform existing constructions by a factor of at least 2 in both computation and communication. Additionally, our solution does not rely on any lookup table. We demonstrate that these schemes can also be generalized to design VES for Schnorr signature scheme and EdDSA. The main technical contribution of this paper, which is of independent interest, is a zero-knowledge proof for the equality of the discrete log of an elliptic-curve point and that of a JL ciphertext. Importantly, the security of our proof does not rely on any non-standard assumptions.

Threshold ECDSA receives interest lately due to its widespread adoption in blockchain applications. A common building block of all leading constructions involves a secure conversion of multiplicative shares into additive ones, which is called the multiplicative-to-additive (MtA) function. MtA dominates the overall complexity of all existing threshold ECDSA constructions. Specifically, O(n2) invocations of MtA are required in the case of n active signers. Hence, improvement of MtA leads directly to significant improvements for all state-of-the-art threshold ECDSA schemes.

In cryptography and algorithmic number theory, modular inversion is viewed as one of the most common and time-consuming operations. It is hard to be directly accomplished on resource-constrained clients (e.g., mobile devices and IC cards) since modular inversion involves a great amount of operations on large numbers in practice. To address the above problem, this paper proposes a novel unimodular matrix transformation technique to realize secure outsourcing of modular inversion. This technique makes our algorithm achieve several amazing properties. First, to the best of our knowledge, it is the first secure outsourcing computation algorithm that supports arbitrary and variable modulus, which eliminates the restriction in previous work that the protected modulus has to be a fixed composite number. Second, our algorithm is based on the single untrusted program model, which avoids the non-collusion assumption between multiple servers. Third, for each given instance of modular inversion, it only needs one round interaction between the client and the cloud server, and enables the client to verify the correctness of the results returned from the cloud server with the (optimal) probability 1. Furthermore, we propose an extended secure outsourcing algorithm that can solve modular inversion in multi-variable case. Theoretical analysis and experimental results show that our proposed algorithms achieve remarkable local-client’s computational savings. At last, as two important and helpful applications of our algorithms, the outsourced implementations of the key generation of RSA algorithm and the Chinese Reminder Theorem are given.

Two-party ECDSA signatures have received much attention due to their widespread deployment in cryptocurrencies. Depending on whether or not the message is required, we could divide two-party signing into two different phases, namely, offline and online. Ideally, the online phase should be made as lightweight as possible. At the same time, the cost of the offline phase should remain similar to that of a normal signature generation. However, the existing two-party protocols of ECDSA are not optimal: either their online phase requires decryption of a ciphertext, or their offline phase needs at least two executions of multiplicative-to-additive conversion which dominates the overall complexity. This paper proposes an online-friendly two-party ECDSA with a lightweight online phase and a single multiplicative-to-additive function in the offline phase. It is constructed by a novel design of a re-sharing of the secret key and a linear sharing of the nonce. Our scheme significantly improves previous protocols based on either oblivious transfer or homomorphic encryption. We implement our scheme and show that it outperforms prior online-friendly schemes (i.e., those have lightweight online cost) by a factor of roughly 2 to 9 in both communication and computation. Furthermore, our two-party scheme could be easily extended to the 2-out-of-n threshold ECDSA.

There only exists one deterministic identity-based encryption (DIBE) scheme which is adaptively secure in the auxiliary-input setting, under the learning with errors (LWE) assumption. However, the master public key consists of O(λ) basic matrices. In this paper, we consider to construct adaptively secure DIBE schemes with more compact public parameters from the LWE problem. (i) On the one hand, we gave a generic DIBE construction from lattice-based programmable hash functions with high min-entropy. (ii) On the other hand, when instantiating our generic DIBE construction with four LPHFs with high min-entropy, we can get four adaptively secure DIBE schemes with more compact public parameters. In one of our DIBE schemes, the master public key only consists of ω(log⁡λ) basic matrices.

In this paper, we propose a hierarchical identity-based encryption (HIBE) scheme in the random oracle (RO) model based on the learning with rounding (LWR) problem over small modulus $q$. Compared with the previous HIBE schemes based on the learning with errors (LWE) problem, the ciphertext expansion ratio of our scheme can be decreased to 1/2. Then, we utilize the HIBE scheme to construct a deterministic hierarchical identity-based encryption (D-HIBE) scheme based on the LWR problem over small modulus. Finally, with the technique of binary tree encryption (BTE) we can construct HIBE and D-HIBE schemes in the standard model based on the LWR problem over small modulus.