With the demand of cryptocurrencies, threshold ECDSA recently regained popularity. So far, several methods have been proposed to construct threshold ECDSA, including the usage of OT and homomorphic encryptions (HE). Due to the mismatch between the plaintext space and the signature space, HE-based threshold ECDSA always requires zero-knowledge range proofs, such as Paillier and Joye-Libert (JL) encryptions. However, the overhead of range proofs constitutes a major portion of the total cost.

In this paper, we propose a new optimization for the Paillier’s additively homomorphic encryption scheme (Eurocrypt’99). At the heart of our optimization is a well-chosen subgroup of the underlying , which is used as the randomness space for masking messages during encryption. The size of the subgroup is significantly smaller than that of , leading to faster encryption and decryption algorithms of our optimization. We establish the one-wayness and semantic security of our optimized Paillier scheme upon those of an optimization (i.e., “Scheme 3”) made by Paillier in Eurocrypt’99. Thus, our optimized scheme is one-way under the partial discrete logarithm (PDL) assumption, and is semantically secure under the decisional PDL (DPDL) assumption. On the other hand, we present a detailed analysis on the concrete security of our optimized scheme under several known methods. To provide 112-bit security, our analysis suggests that a 2048-bit modulus N and a well-chosen subgroup of size 448-bit would suffice. We compare our optimization with existing optimized Paillier schemes, including the Jurik’s optimization proposed by Jurik in his Ph.D. thesis and the Paillier’s optimization in Eurocrypt’99. Our experiments show that, – the encryption of our optimization is about 2.7 times faster than that of the Jurik’s optimization and is about 7.5 times faster than that of the Paillier’s optimization;

Abstract We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction. We provide two distinct, but closely related constructions and show that multilinear analogues of the $${\text {DDH}} $$ DDH assumption hold for them. Our first construction is symmetric and comes with a $$\kappa $$ κ -linear map $$\mathbf{e }: {{\mathbb {G}}}^\kappa \longrightarrow {\mathbb {G}}_T$$ e:Gκ⟶GT for prime-order groups $${\mathbb {G}}$$ G and $${\mathbb {G}}_T$$ GT . To establish the hardness of the $$\kappa $$ κ -linear $${\text {DDH}} $$ DDH problem, we rely on the existence of a base group for which the $$\kappa $$ κ -strong $${\text {DDH}} $$ DDH assumption holds. Our second construction is for the asymmetric setting, where $$\mathbf{e }: {\mathbb {G}}_1 \times \cdots \times {\mathbb {G}}_{\kappa } \longrightarrow {\mathbb {G}}_T$$ e:G1×⋯×Gκ⟶GT for a collection of $$\kappa +1$$ κ+1 prime-order groups $${\mathbb {G}}_i$$ Gi and $${\mathbb {G}}_T$$ GT , and relies only on the 1-strong $${\text {DDH}} $$ DDH assumption in its base group. In both constructions, the linearity $$\kappa $$ κ can be set to any arbitrary but a priori fixed polynomial value in the security parameter. We rely on a number of powerful tools in our constructions: probabilistic indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness-indistinguishability, and zero knowledge), and additively homomorphic encryption for the group $$\mathbb {Z}_N^{+}$$ ZN+ . At a high level, we enable “bootstrapping” multilinear assumptions from their simpler counterparts in standard cryptographic groups and show the equivalence of PIO and multilinear maps under the existence of the aforementioned primitives.

Proofs of retrievability (PoR) enables clients to outsource huge amount of data to cloud servers, and provides an efficient audit protocol, which can be employed to check that all the data is being maintained properly and can be retrieved from the server. In this paper, we present a generic construction of PoR from linearly homomorphic structure-preserving signature (LHSPS), which makes public verification possible. Authenticity and retrievability of our PoR scheme are guaranteed by the unforgeability of LHSPS. We further extend our result to dynamic PoR, which supports dynamic update of outsourced data. Our construction is free of complicated data structures like Merkle hash tree. With an instantiation of a recent LHSPS scheme proposed by Kiltz and Wee (EuroCrypt15), we derive a publicly verifiable (dynamic) PoR scheme. The security is based on standard assumptions and proved in the standard model.

ℱ-Related-Key Attacks (RKAs) allow an adversary to tamper the key k stored in a cryptographic device by specifying related-key deriving (RKD) functions f in ℱ and subsequently learn the outcome of the device under related keys f(k)⁠. In this paper, we present RKA secure public-key encryption (PKE) and symmetric encryption (SE) schemes admitting a tight security reduction to the standard s-Linear assumption. The security loss depends only on the security parameter and is independent of the number of tampering queries made by the adversary. Our encryption schemes are resilient to RKAs w.r.t. the set of restricted affine functions ℱraff⁠, of which the set of linear functions ℱlin is a subset. In particular, • Our encryption schemes serve as the first ones possessing tight RKA security for a non-trivial RKD function class ℱ under standard assumptions. • Moreover, our encryption schemes enjoy tight super-strong RKA securities, which are the strongest ones among the existing RKA security notions.

In a selective-opening, chosen-ciphertext attack (SO-CCA) against a public key encryption scheme (PKE scheme), a probabilistic polynomial time (PPT) adversary obtains a vector of challenge ciphertexts, has access to a decryption oracle, adaptively selects to open some of the challenge ciphertexts and sees the corresponding messages together with the random coins. The simulation-based, selective-opening security against chosen-ciphertext attacks (SIM-SO-CCA security) protects the security of the unopened messages in a semantic way, i.e. it requires that the output of the adversary can be simulated by a simulator who sees only the opened messages. In particular, all information that the adversary can get from the unopened messages can also be simulated from the opened messages alone by the simulator. All security proofs of the available PKEs achieving SIM-SO-CCA security are not tight, and the security loss depends either on the number of challenge ciphertexts or on the number of decryption queries. In this work, we present the first PKE scheme which achieves SIM-SO-CCA security with a tight reduction to standard assumptions. This partially solves the open problem proposed by Hofheinz in EuroCrypt 2012.

Robust fuzzy extractor is able to distill almost uniform strings from non-uniform noisy sources while robustness enables the extractor to detect adversaries’ active attacks. Its security used to be defined information-theoretically. Information-theoretical security model is nice but too restricted and the extracted uniform string output by robust fuzzy extractors might be too short to be useful. This occurs even for the nearly optimal statistical robust fuzzy extractor constructed by Cramer et al. (Eurocrypt 2008). In this paper, we introduce the notion of computational robust fuzzy extractor by relaxing information-theoretical security to computational security and defining computational privacy and computational robustness for it. We give a simple construction of computational robust fuzzy extractor based on the hardness of Subgroup Membership Problem and Discrete Logarithm assumption. Thanks to computational security, our construction obtains much longer extracted uniform string than the nearly optimal (information-theoretically) robust fuzzy extractor proposed by Cramer et al.

KDM [F] -CCA security of public-key encryption (PKE) ensures the privacy of key-dependent messages f(sk) which are closely related to the secret key sk , where f∈F , even if the adversary is allowed to make decryption queries. In this paper, we study the design of KDM-CCA secure PKE. To this end, we develop a new primitive named Auxiliary-Input Authenticated Encryption (AIAE). For AIAE, we introduce two related-key attack (RKA) security notions, including IND-RKA and weak-INT-RKA. We present a generic construction of AIAE from tag-based hash proof system (HPS) and one-time secure authenticated encryption (AE) and give an instantiation of AIAE under the Decisional Diffie-Hellman (DDH) assumption. Using AIAE as an essential building block, we give two constructions of efficient KDM-CCA secure PKE based on the DDH and the Decisional Composite Residuosity (DCR) assumptions. Specifically, (i) our first PKE construction is the first one achieving KDM [Faff] -CCA security for the set of affine functions and compactness of ciphertexts simultaneously. (ii) Our second PKE construction is the first one achieving KDM [Fpolyd] -CCA security for the set of polynomial functions and almost compactness of ciphertexts simultaneously. Our PKE constructions are very efficient; in particular, they are pairing-free and NIZK-free.

Proofs of Data Possession/Retrievability (PoDP/PoR) schemes are essential to cloud storage services, since they can increase clients' confidence on the integrity and availability of their data. The majority of PoDP/PoR schemes are constructed from homomorphic linear authentication (HLA) schemes, which decrease the price of communication between the client and the server. In this paper, a new subclass of authentication codes, named ε-authentication codes, is proposed, and a modular construction of HLA schemes from ε-authentication codes is presented. We prove that the security notions of HLA schemes are closely related to the size of the authenticator/tag space and the successful probability of impersonation attacks (with non-zero source states) of the underlying ε-authentication codes. We show that most of HLA schemes used for the PoDP/PoR schemes are instantiations of our modular construction from some ε-authentication codes. Following this line, an algebraic-curves-based ε-authentication code yields a new HLA scheme.

The authors present a new general construction of public key encryption (PKE) based on the restricted subset membership (RSM) assumption, which can achieve the bounded‐memory leakage resilient security and the auxiliary‐input leakage resilient security simultaneously. The construction is BHHO‐type, as Brakerski et al . work, but the message space is much larger and the proof is more concise benefiting from the RSM assumption. Instantiating the construction with the QR assumption, the authors get the first QR‐based auxiliary‐input secure PKE with a larger message space than {0,1}. Moreover, the authors generalise the Goldreich–Levin theorem to large rings. This theorem helps to improve the construction to achieve the same security level with fewer public parameters and shorter ciphertexts compared with Brakerski et al . work. For the bounded‐memory leakage resilient security, the construction can achieve leakage rate of 1 − o (1) and avoid the dependence between the message length and the amount of leakage. Based on the general construction, the authors also can achieve both bounded‐memory leakage resilient chosen ciphertext attack (CCA) security and the auxiliary‐input leakage resilient CCA security via the well‐known Naor–Yung paradigm.