Conventional blockchains can provide data availability and integrity only. Tons of applications additionally need confidentiality with flexible access control such that data providers can decide how their data are shared through blockchains. This paper aims at enhancing Byzantine Fault Tolerance (BFT)-based permissioned blockchains with controllable access control. To this goal, we extend the concept of Proxy Re-Encryption (PRE) to a new variant called Controllable Threshold PRE (CT-PRE). The traditional PRE enables a proxy, using a re-encryption key, to convert a ciphertext meant for delegator A into another ciphertext meant for delegatee B, all without exposing the original message. CT-PRE extends PRE into the setting with multiple proxies (corresponding to blockchain servers and avoiding a single point of failure) and enables the delegator to fully take control of its ciphertext. We formally define CT-PRE and construct a provably secure CTPRE scheme. We further extend the CTPRE scheme to a verifiable one VCTPRE. We implement the Verifiable CT-PRE scheme with stronger security, integrate it in our BFT-based blockchain system, and deploy our system in a WAN on Amazon EC2 with 22 nodes across four continents. We show that our system is highly efficient, achieving a throughput of 5.15 ktx/sec (for access control operations) and 10.83 ktx/sec (for write operations, only slightly slower than our BFT write operations), respectively.

A key management service (KMS) is vital to modern mission-critical systems. At the core of KMS are the key generation process and the key refresh process. In this paper, we design and implement a purely asynchronous system for completely distributed KMS supporting traditional applications such as threshold cryptosystems and multiparty computation (MPC) as well as emerging blockchains and Web3 applications. In this system, we have built a number of new asynchronous distributed key generation (ADKG) protocols and their corresponding asynchronous distributed key refresh (ADKR) protocols. We have demonstrated that our ADKG and ADKR protocols in the standard model outperform existing ones of the same kind, while our protocols in the random oracle model (ROM) are more efficient than other protocols with small and medium-sized networks.

Distributed key generation (DKG) allows bootstrapping threshold cryptosystems without relying on a trusted party, nowadays enabling fully decentralized applications in blockchains and multiparty computation (MPC). While we have recently seen new advancements for asynchronous DKG (ADKG) protocols, their performance remains the bottleneck for many applications, with only one protocol being implemented (DYX+ ADKG, IEEE S&P 2022). DYX+ ADKG relies on the Decisional Composite Residuosity assumption (being expensive to instantiate) and the Decisional Diffie-Hellman assumption, incurring a high latency (more than 100s with a failure threshold of 16). Moreover, the security of DYX+ ADKG is based on the random oracle model (ROM) which takes hash function as an ideal function; assuming the existence of random oracle is a strong assumption, and up to now, we cannot find any theoretically-sound implementation. Furthermore, the ADKG protocol needs public key infrastructure (PKI) to support the trustworthiness of public keys. The strong models (ROM and PKI) further limit the applicability of DYX+ ADKG, as they would add extra and strong assumptions to underlying threshold cryptosystems. For instance, if the original threshold cryptosystem works in the standard model, then the system using DYX+ ADKG would need to use ROM and PKI. In this paper, we design and implement a modular ADKG protocol that offers improved efficiency and stronger security guarantees. We explore a novel and much more direct reduction from ADKG to the underlying blocks, reducing the computational overhead and communication rounds of ADKG in the normal case. Our protocol works for both the low-threshold and high-threshold scenarios, being secure under the standard assumption (the well-established discrete logarithm assumption only) in the standard model (no trusted setup, ROM, or PKI).

Biometric features are quite suitable for identity authentication due to its inherent properties – universality, uniqueness and persistence. In fact, biometric authentication has been widely used in our daily life, especially in mobile devices. However, biometric features are quite sensitive, and once a feature is leaked to an evil adversary, it cannot be used in authentication any more. This leads to a push on research of biometric privacy protection. In this paper, we propose a face-based authentication system with the help of a computational secure sketch. The computational secure sketch takes charge of error tolerance on the face samplings. Then the face features of the same user are used to extract an authentication key, which is in turn used to do the identity authentication for the user. The computational security of the computational secure sketch makes sure that the public information obtained by the adversary does not affect the pseudorandomness of the authentication key, hence the privacy of face features is guaranteed. Moreover, the privacy protection technique in our face-based authentication system can be extended to other biometric-based authentication.

Abstract A fuzzy extractor derives uniformly random strings from noisy sources that are neither reliably reproducible nor uniformly random. The basic definition of fuzzy extractor was first formally introduced by Dodis et al. and has achieved various applications in cryptographic systems. However, it has been proved that a fuzzy extractor could become totally insecure when the same noisy random source is extracted multiple times. To solve this problem, the reusable fuzzy extractor is proposed. In this paper, we propose the first reusable fuzzy extractor based on the LPN assumption, which is efficient and resilient to linear fraction of errors. Furthermore, our construction serves as an alternative post-quantum reusable fuzzy extractor.

Location-based service (LBS) provides more and more conveniences to people. However, it also brings potential threats of offending users' privacy. How to protect users' privacy in LBS schemes has aroused increasing research interests in recent years. Most of the existing privacy-preserving LBS schemes are based on the hardness of traditional number-theoretic problems such as the integer factorization or the discrete logarithm problems. However, with the development of large scale quantum computers, these traditional problems can be easily solved by Shor's algorithms, hence the security of these LBS schemes is greatly threatened. In this paper, we solve this problem by constructing a privacy-preserving LBS scheme against quantum attacks from an LWE-based key-homomorphic pseudorandom functions (PRF). In our scheme, due to the key-homomorphic property of the PRF, an LBS user only has to compute one PRF value of the target location and the remaining computation is outsourced to a cloud server, which releases the user from heavy computation burden. In addition, by dividing the key encrypting LBS data into two parts and assigning the two parts to the cloud sever and each user respectively, our scheme avoids the threats of key abuse and information leaking of LBS data. Moreover, we use this PRF to realize an authenticated protocol, which protects the communications between the LBS users and the cloud server. We stress that the security of our scheme is based only on the security of the LWE-based key-homomorphic PRF, hence our scheme is the first LBS scheme secure against quantum attacks.

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.

Abstract Due to the proliferation of side‐channel attacks, many efforts have been made to construct cryptographic systems that remain provably secure even if part of the secret information is leaked to the adversary. Recently, there have been many identity‐based encryption (IBE) schemes proposed in this context, almost all of which, however, can only achieve chosen plaintext attack (CPA) security. As far as we know, Alwenet al.'sIBE is the unique practical scheme secure against adaptive chosen ciphertext attacks (CCA2) in the standard model. Unfortunately, this scheme suffers from an undesirable shortcoming that the leakage parameterλand the message lengthmare subject toλ+m≤ logp−ω(logκ), whereκandpdenote the security parameter and the prime order of the underlying group, respectively. Beyond that, the leakage ratio in this scheme is very low, which can just reach 1/6. In this work, we put forward two new IBE schemes, both of which areλ‐leakage‐resilient CCA2 secure in the standard model. Specifically, the first construction is proposed based on Gentry's IBE, which is quite practical and almost as efficient as the original scheme. Moreover, its leakage parameter,λ≤ logp−ω(logκ), is independent of the size of the message space. To the best of our knowledge, it is the first practical leakage‐resilient fully CCA2 secure IBE scheme in the standard model, tolerating up to (logp−ω(logκ))‐bit leakage of the private key and its leakage parameter being independent of the message length. As to the second construction, it is proposed based on the scheme of Alwenet al., which has the same leakage parameter as Alwenet al., but has a better efficiency performance and a higher leakage ratio. As far as we know, it is the first practical and fully CCA2 secure leakage‐resilient IBE scheme with leakage ratio up to 1/4. Copyright © 2016 John Wiley & Sons, Ltd.

Efficient user revocation in Identity-Based Encryption (IBE) has been a challenging problem and has been the subject of several research efforts in the literature. Among them, the tree-based revocation approach, due to Boldyreva, Goyal and Kumar, is probably the most efficient one. In this approach, a trusted Key Generation Center (KGC) periodically broadcasts a set of key updates to all (non-revoked) users through public channels, where the size of key updates is only $$O(r\log \frac{N}{r})$$ , with N being the number of users and r the number of revoked users, respectively; however, every user needs to keep at least $$O(\log N)$$ long-term secret keys and all non-revoked users are required to communicate with the KGC regularly. These two drawbacks pose challenges to users who have limited resources to store their secret keys or cannot receive key updates in real-time. To alleviate the above problems, we propose a novel system model called server-aided revocable IBE. In our model, almost all of the workloads on users are delegated to an untrusted server which manages users’ public keys and key updates sent by a KGC periodically. The server is untrusted in the sense that it does not possess any secret information. Our system model requires each user to keep just one short secret key and does not require users to communicate with either the KGC or the server during key updating. In addition, the system supports delegation of users’ decryption keys, namely it is secure against decryption key exposure attacks. We present a concrete construction of the system that is provably secure against adaptive-ID chosen plaintext attacks under the DBDH assumption in the standard model. One application of our server-aided revocable IBE is encrypted email supporting lightweight devices (e.g., mobile phones) in which an email server plays the role of the untrusted server so that only non-revoked users can read their email messages.

A leakage‐resilient public‐key encryption (PKE) scheme provides security even if an adversary obtains some information on the secret key. In recent years, much attention has been focused on designing provably secure PKE in the presence of key‐leakage and almost all the constructions rely on an important building block namely hash proof system (HPS). However, in the setting of adaptive chosen‐ciphertext attacks (CCA2), there are not many HPS‐based leakage‐resilient PKE schemes available. Moreover, most of them have an unsatisfactory leakage rate. In this study, the authors propose a new method of constructing leakage‐resilient CCA2‐secure PKE scheme from any tag‐based strongly universal 2 HPS. The striking advantage of the authors scheme is the leakage rate, which is the best one among all known HPS‐based indistinguishability key leakage CCA2‐secure constructions. In particular, they present an instantiation under the n ‐linear assumption. In the cases of n = 1 (resp. n = 2), they actually obtain a decisional Diffie–Hellman (DDH)‐based [resp. decisional linear (DLIN)‐based] PKE scheme, where the leakage rate can be made to 1/4 (resp. 1/6). The authors DDH‐based scheme achieves the best leakage rate among all known DDH‐based (Cramer–Shoup‐type) schemes. Their DLIN‐based scheme is the first one that can achieve leakage of L /6 bits without pairing, where L is the length of the secret key.

In this paper, we propose the notion of n-evasive all-but-many lossy trapdoor functions ABM-LTFs, which is an extended abstraction of all-but-n lossy trapdoor functions ABN-LTFs proposed by Hemenway et al. in Asiacrypt 2011 and, at the same time, is a special case of ABM-LTFs proposed by Hofheinz in Eurocrypt 2012. We show two constructions of n-evasive ABM-LTFs. The first one is based on the decisional composite residuosity DCR assumption, and the second one is from chameleon hash functions and ABN-LTFs. Both of the constructions are based on reasonable assumptions with tight security reductions. Similar to ABN-LTFs and ABM-LTFs, n-evasive ABM-LTFs can be employed to construct indistinguishability-based selective opening chosen-ciphertext secure public-key encryption PKE schemes and may have other applications in cryptography. The instantiation of n-evasive ABM-LTFs can be based on the well-known assumption, for example, DCR, and the security reduction is much tighter than that of ABM-LTFs. On the other hand, the black-box PKE construction from n-evasive ABM-LTFs is more general than that from ABN-LTFs. Copyright © 2014 John Wiley & Sons, Ltd.

Attribute-based encryption (ABE) with outsourced decryption not only enables fine-grained sharing of encrypted data, but also overcomes the efficiency drawback (in terms of ciphertext size and decryption cost) of the standard ABE schemes. In particular, an ABE scheme with outsourced decryption allows a third party (e.g., a cloud server) to transform an ABE ciphertext into a (short) El Gamal-type ciphertext using a public transformation key provided by a user so that the latter can be decrypted much more efficiently than the former by the user. However, a shortcoming of the original outsourced ABE scheme is that the correctness of the cloud server's transformation cannot be verified by the user. That is, an end user could be cheated into accepting a wrong or maliciously transformed output. In this paper, we first formalize a security model of ABE with verifiable outsourced decryption by introducing a verification key in the output of the encryption algorithm. Then, we present an approach to convert any ABE scheme with outsourced decryption into an ABE scheme with verifiable outsourced decryption. The new approach is simple, general, and almost optimal. Compared with the original outsourced ABE, our verifiable outsourced ABE neither increases the user's and the cloud server's computation costs except some nondominant operations (e.g., hash computations), nor expands the ciphertext size except adding a hash value (which is <;20 byte for 80-bit security level). We show a concrete construction based on Green et al.'s ciphertext-policy ABE scheme with outsourced decryption, and provide a detailed performance evaluation to demonstrate the advantages of our approach.

SUMMARY Chosen‐ciphertext security has been well‐accepted as a standard security notion for public‐key encryption. But in a multi‐user surrounding, it may not be sufficient, because the adversary may corrupt some users to obtain the random coins as well as the plaintexts used to generate ciphertexts. The attack is named ‘selective opening attack’. We study how to achieve full‐fledged chosen‐ciphertext security in selective opening setting directly from the Decisional Diffie–Hellman assumption. Our construction is actually a tag‐based public‐key encryption scheme free of chameleon hashing and has a tight security reduction to the Decisional Diffie–Hellman assumption and the collision‐resistant assumption of hash functions. The tag for each ciphertext is generated in a flexible way to serve the chosen‐ciphertext security proof in selective opening settings. Copyright © 2013 John Wiley & Sons, Ltd.

ABSTRACT In EUROCRYPT 2009, Hofheinz and Kiltz introduced a new practical chosen ciphertext secure public‐key encryption scheme under the assumption that factoring is intractable. They also proposed a variant that features a slightly more efficient decryption but unfortunately leads to large public key, of size about O(k), where k is a security parameter. In this paper, we propose a novel method to balance the efficiency and the key size of those previous two schemes. Although the public key in our scheme only consists of one RSA modulus and three group elements, it is still more efficient at decrypting than Hofheinz and Kiltz's scheme. By remarking that under certain assumptions factoring the modulus is still hard over much smaller subgroups of signed quadratic residues (i.e., semismooth subgroup), we were able to construct a new scheme that performs extremely efficient decryption. In fact, to date, this is the most efficient scheme for decryption among all public‐key encryption schemes (mainly including Hofheinz and Kiltz's schemes and their follow‐up works) whose security against chosen ciphertext attacks is based on the intractability of factoring in the standard model. Copyright © 2012 John Wiley & Sons, Ltd.