Provable Security

Ciphertext-policy attribute-based encryption, denoted by CP-ABE, is a promising extension of identity-based encryption which enables fine-grained data access control by taking a set of attributes as users’ public key. However, owing to the fact that an attribute set may be shared by multiple users, malicious users dare to share their decryption keys to others for profits. Furthermore, the central authority is able to issue arbitrary decryption keys for any unauthorized users. To prevent these two kinds of key abuses in CP-ABE system, we propose an accountable CP-ABE scheme which allows any third party to publicly verify the identity embedded in a leaked decryption key, allows an auditor to publicly check whether a malicious user or the authority should be responsible for an exposed decryption key, and the malicious user or the authority can’t deny it. The proposed accountable CP-ABE scheme supports any LSSS realizable access structures. At last, the confidentiality and public verifiability of the proposed scheme can be proved to be tightly related to the atomic CP-ABE scheme and the signature scheme that it composed from.

A promising solution to protect data privacy in cloud storage services is known as ciphertext-policy attribute-based encryption (CP-ABE). However, in a traditional CP-ABE scheme, a ciphertext is bound with an explicit access structure, which may leak private information about the underlying plaintext in that anyone having access to the ciphertexts can tell the attributes of the privileged recipients by looking at the access structures. A notion called CP-ABE with partially hidden access structures [14, 15, 18, 19, 24] was put forth to address this problem, in which each attribute consists of an attribute name and an attribute value and the specific attribute values of an access structure are hidden in the ciphertext. However, previous CP-ABE schemes with partially hidden access structures only support access structures in AND gates, whereas a few other schemes supporting expressive access structures are computationally inefficient since they are built from bilinear pairings over the composite-order groups. In this paper, we focus on addressing this problem, and present an expressive CP-ABE scheme with partially hidden access structures in prime-order groups.

Attribute-based encryption (ABE) allows one-to-many encryption with static access control. In many occasions, the access control policy must be updated and the original encryptor might be required to re-encrypt the message, which is impractical, since the encryptor might be unavailable. Unfortunately, to date the work in ABE does not consider this issue yet, and hence this hinders the adoption of ABE in practice. In this work, we consider how to efficiently update access policies in Ciphertext-policy Attribute-based Encryption (CP-ABE) systems without re-encryption. We introduce a new notion of CP-ABE supporting access policy update that captures the functionalities of attribute addition and revocation to access policies. We formalize the security requirements for this notion, and subsequently construct two provably secure CP-ABE schemes supporting AND-gate access policy with constant-size ciphertext for user decryption. The security of our schemes are proved under the Augmented Multi-sequences of Exponents Decisional Diffie-Hellman assumption.

Next, we establish two results that clarify the strength of our definition when compared with existing ones that use the game-based definitional approach. On the positive side, we demonstrate that both read and write-access guarantees in the sense of game-based security are implied by UC security of an access control system. Perhaps expected, this result serves as confirmation that the definition we propose is sound.

Our main technical result is a proof that simulation-based security requires impractical assumptions on the encryption scheme that is employed. As in other simulation-based settings, the source of inefficiency is the well known “commitment problem” which naturally occurs in the context of cryptographic access control to file systems.

As an important method, cloud-based data auditing can realize the integrity checking of the outsourced data efficiently. However, the existing public auditing schemes are mainly based on the PKI (public key infrastructure). In this infrastructure, the auditor must validate the certificates of data user before auditing data integrity. Thus, there exist some drawbacks in such infrastructure. (1) It brings the heavy computation burdens on the auditor in the auditing process (2) Complicated management of public key certificate makes the whole auditing protocol inefficient, in particular, in the multi-user setting. To overcome complicated key management and key exposure and reduce computation cost in the auditing process, we propose ID-based data integrity public auditing scheme with forward security in this paper. After a private key of data user is compromised, all previous produced authentication tags still remain valid. And we also show that our construction is provably secure under the RSA assumption with prime exponents. Due to being based on RSA, none of pairing operation is required in any algorithm, it makes that auditing efficiency is greatly improved since the implementations of pairings are much harder than those of exponentiations in a RSA group. The highlight in our scheme is that the auditor’s verification cost is constant, it is independent of the number of the challenged set. Comparing with Yu et al.’s scheme, our scheme has more advantages in terms of computation cost and communication overhead. And implementation results also show that our scheme is very practical and suitable for the multi-user setting in the real life.

In order to ensure the remote data integrity in cloud storage, provable data possession (PDP) is of crucial importance. For most clients, dynamic data operations are indispensable. This paper proposes an efficient dynamic PDP scheme for verifying the remote dynamic data integrity in an untrusted cloud storage. Our dynamic PDP scheme is constructed from dynamic binary tree and bilinear pairings, supporting the dynamic data operations, such as, insertion, deletion, modification. From the computation cost, communication cost, and storage cost, our proposed dynamic PDP scheme is efficient. On the other hand, our proposed concrete dynamic PDP scheme is provably secure.

Provable Data Possession (PDP) is a technique for checking whether data is correctly stored in remote servers without retrieving the entire data. For many previous PDP schemes, correctly choosing public key for clients relies on the security of Public Key Infrastructure (PKI), but PKI itself still faces many kinds of security vulnerabilities. In addition, the verification of certificates introduces heavy computation and communication cost. In this paper, we propose an Identity-Based Batch Provable Data Possession (ID-BPDP) scheme to eliminate the certificate management. Meanwhile, to the best of our knowledge, it is the first identity-based provable data possession scheme supporting batch verification for multiple owners and multiple clouds simultaneously to reduce computation cost greatly. Our scheme is provably correct and secure based on bilinear pairings and the hardness assumption of Computational Diffie-Hellman problem, and our analyses/simulations show that the scheme is able to verify the integrity of data efficiently.

To enjoy the advantage of cloud service while preserving security and privacy, huge data is increasingly outsourced to cloud in encrypted form. Unfortunately, encryption may impede the analysis and computation over the outsourced dataset. Naïve Bayesian classification is an effective algorithm to predict the class label of unlabeled samples. In this paper, we investigate naïve Bayesian classification on encrypted dataset in cloud and propose a secure scheme for the challenging problem. In our scheme, all the computation task of naïve Bayesian classification are completed by the cloud, which can dramatically reduce the burden of data owner and users. Based on the theoretical proof, our scheme can guarantee the security of both input dataset and output classification results, and the cloud can learn nothing useful about the training data of data owner and the test samples of users throughout the computation. Additionally, we evaluate our computation complexity and communication overheads in detail.

Searchable symmetric encryption is an efficient way to perform keyword search over encrypted data in cloud storage. However, most existing methods do not take into account the integrity verification of the search result. Moreover, existing methods can only verify the integrity of single-keyword search results, which cannot meet the requirements of multi-keyword conjunctive search. To address this problem, we proposed a multi-keyword searchable encryption scheme with an authentication mechanism that can efficiently verify the integrity of search results. The proposed scheme is based on the searchable symmetric encryption and adopts the bilinear map accumulator to prove the correctness of set operations. It supports multiple keywords as input for conjunctive search and gives the server the ability to prove the integrity of the search result to the user. Formal proofs show that the proposed scheme is unforgeable and adaptive secure against chosen-keyword attacks. To the best of our knowledge, this is the first work that can authenticate the multi-keyword search result over encrypted data.

Oblivious keyword search (OKS) allows a user to search and retrieve the data associated with a chosen keyword in an oblivious way. The database supplier issues a trapdoor (used for searching) of a specific keyword chosen by the user while learns nothing about this keyword. In this paper, we propose a new cryptographic primitive called oblivious keyword search with authorization (OKSA). In OKSA, the supplier is able to verify the to-be-search keyword belonging to the authorized keyword set for a user before running the OKS protocol. The proposed OKSA augments the traditional OKS by providing assurance of keyword authorization besides oblivious search. Then we present an OKSA protocol and formally prove its security. The proposed protocol features with one-round (two-pass) interaction and constant size communication cost between the supplier and the user in the transfer phase. Precisely, the communication cost nseeds only four group elements (three group elements for keyword token and proof, and one group element for assigned trapdoor), independent of the size of authorized keyword set.

We are studing the problem of searching on hidden index in asymmetric setting. We define a mechanism that enables receiver to provide a token to the server and enables the server to test whether an encapsulated index matches the token without learning anything else about them. We refer to this mechanism as Asymmetric Index Encapsulation. We suggest to using the AIE as the core protocol of anonymous content-oriented networking. A construction of AIE which strikes a balance between efficiency and security is also given. Our scheme is proved secure base on the DBDH/CDH assumption in the random oracle with tight reduction, while the encapsulated header and the token in our system consists of only three elements.

In this paper, we propose a two-round dynamic multi-cast key distribution (DMKD) protocol under the star topology with a central authentication server. Users can share a common session key without revealing any information of the session key to the server, and can join/leave to/from the group at any time even after establishing the session key. Our protocol is scalable because communication and computation costs of each user are independent from the number of users. Also, our protocol is still secure if either private key or session-specific randomness of a user is exposed. Furthermore, time-based backward secrecy is guaranteed by renewing the session key for every time period even if the session key is exposed. We introduce the first formal security definition for DMKD under the star topology in order to capture such strong exposure resilience and time-based backward secrecy. We prove that our protocol is secure in our security model in the standard model.

Attribute-based authenticated key exchange (AB-AKE) is a useful primitive that allows a group of users to establish a shared secret key and at the same time enables fine-grained access control. A straightforward approach to design an AB-AKE protocol is to extend a key exchange protocol using attribute-based authentication technique. However, insider security is a challenge security issue for AB-AKE in the multi-party setting and cannot be solved using the straightforward approach. In addition, many existing key exchange protocols for the multi-party setting (e.g., the well-known Burmester-Desmedt protocol) require multiple broadcast rounds to complete the protocol. In this paper, we propose a novel one-round attribute-based key exchange (OAKE) protocol in the multi-party setting. We define the formal security models, including session key security and insider security, for OAKE, and prove the security of the proposed protocol under some standard assumptions in the random oracle model.

Key agreement protocol is generic way to establish a secure private conversation over a public network. Recently, certificateless key agreement (CL-KA) protocol has drawn much attention because it not only efficiently eliminates the problems of key escrow and certificate management but also is more suitable for universal wireless communication environment. However, it is a challenge to design a CL-KA protocol to meet security and efficiency requirement concurrently. In this paper, we propose a new two-party CL-KA protocol with short message under GDH and GBDH assumption. We also present a full security proof for the proposed protocol in extended Canetti-Krawczyk (eCK) security model. The performance shows that the proposed protocol can capture the security requirements and is more efficient than similar CL-KA protocol.

We study the security of authenticated encryption based on a stream cipher and a universal hash function. We consider ChaCha20-Poly1305 and generic constructions proposed by Sarkar, where the generic constructions include 14 AEAD (authenticated encryption with associated data) schemes and 3 DAEAD (deterministic AEAD) schemes. In this paper, we analyze the integrity of these schemes both in the standard INT-CTXT notion and in the RUP (releasing unverified plaintext) setting called INT-RUP notion. We present INT-CTXT attacks against 3 out of the 14 AEAD schemes and 1 out of the 3 DAEAD schemes. We then show INT-RUP attacks against 1 out of the 14 AEAD schemes and the 2 remaining DAEAD schemes. We next show that ChaCha20-Poly1305 is provably secure in the INT-RUP notion. Finally, we show that 4 out of the remaining 10 AEAD schemes are provably secure in the INT-RUP notion.

Broadcast encryption with dealership (BED) has been proposed to achieve more innovative and scalable business models for broadcast services. It has an extensive application future. However, designing secure BED is a challenging task. The only known BED construction so far is by Gritti et al. We aim to raise the profile of BED primitives which has not received much attention despite of its importance. This paper presents a selectively chosen plaintext attack (CPA) secure BED scheme supporting maximum number of accountability and privacy (hides the group of users from broadcaster). Our scheme is a key encapsulation mechanism and practically more efficient. It reduces the parameter sizes and computation cost compared to Gritti et al. More interestingly, the broadcaster does not need to rely on users to detect the dishonest dealer. We provide concrete security analysis of our design under reasonable assumptions.

Group Encryption (GE) is a recently proposed cryptographic primitive protecting the privacy of the receivers in a communication system. A majority of group encryption schemes are implicitly based on public key infrastructure (PKI) setting in which the management of certificates are complicated. Identity based encryption (IBE) seems to be a good alternative for PKI in GE, but the private key escrow and the user revocation problem are inherent in IBE system. Certificate-based encryption (CBE) overcomes drawbacks of PKI and IBE. In this paper, we propose a new cryptographic primitive, referred to as certificate-based group encryption (CBGE). In this notion, a certificate authority issues the certificate as a part of decryption key corresponding to a user’s public key and other information; and the user can register himself as a group member to a group manager. Then anyone can verifiably send confidential messages to a group member whose identity information is hidden within a group of certified users. If required, the group manager (GM) can trace the receiver. Following this model, we propose a scheme towards CBGE, where the roles of the verifier and the GM are taken by a single entity. We formally prove the scheme is secure in the random oracle model. Unlike the users existing in GE schemes, users in our scheme need not to check the certificates. CBGE provides an implicit certification mechanism and allows a periodical update of certificate status.

Lossy trapdoor functions (LTFs) were firstly introduced by Peikert and Waters [2]. Since their introduction, LTFs have found numerous applications. In this paper we focus on the LTFs in the continuous leakage. We introduce the new notion of updatable LTFs (ULTFs) and give its formal definition and security properties. Based on these, we extend the security model of the LTFs to continuous leakage. Under the DDH assumption and DCR assumption respectively, we show two explicit LTFs against continuous leakage in the standard model. We also show the performance of the proposed schemes compared with the known existing continuous leakage resilient LTFs.

Due to the imperfect implementation of cryptosystems, adversaries are able to obtain secret state of the systems via side-channel attacks which are not considered in the traditional security notions of cryptographic primitives, and thus break their security. Leakage-resilient cryptography was proposed to prevent adversaries from doing so. Katz et al. and Boyle et al. proposed signature schemes which are existentially unforgeable in the bounded leakage model. However, neither takes measures to prevent the adversary from forging on messages that have been signed before. Recently, Wang et al. showed that any signature scheme can be transformed to one that is strongly unforgeable in the leakage environment with the help of a leakage-resilient chameleon hash function. However, their transformation requires changing the key pair of the signature scheme.

Cloud servers save their storage cost by applying deduplication. Duplicated copies of the same file uploaded by the cloud service clients can be reduced to a single copy by maintaining a list of clients who own the same file. Nowadays it is a common practice to rely on the message digest of the file for showing its possession. Yet, this property has been exploited to make the cloud storage service effectively become a content distribution network, by sharing a short message digest.

Proof of ownership (PoW) has been proposed to address this problem. PoW is an interactive protocol by which the prover can prove to the verifier about the ownership of a file. Under this setting, the adversary is motivated to leak some knowledge of the file, for helping a non-owner to also claim ownership. We are intrigued to ask, what is the strongest possible form of leakage, such that a PoW protocol can be provably secure?

In this paper, we propose a leakage-resilient PoW under a strong model, such that any adversary who holds leakage derived from a form of one-way function cannot falsely claim the file ownership.

In this paper, we present a unidirectional homomorphic proxy re-encryption (PRE) scheme from learning with errors assumption, which can homomorphically evaluates ciphertexts at input or output side, no matter ciphertexts are fresh or re-encrypted (re-encrypted ciphertexts can come from different identities). Our PRE scheme modify the recent HE scheme of Gentry etc. We also use the approximate eigenvector method to manage the noise level and decrease the decryption complexity without introducing additional assumptions. Furthermore, with the security definition of Nishimai etc., we prove that our homomorphic PRE is indistinguishable against chosen-plaintext attacks, key privacy secure and master secret secure.

A major open problem is to protect levelled homomorphic encryption from adaptive attacks that allow an adversary to learn the private key. The only positive results in this area are by Loftus, May, Smart and Vercauteren. They use a notion of “valid ciphertexts” and obtain an IND-CCA1 scheme under a strong knowledge assumption, but they also show their scheme is not secure under a natural adaptive attack based on a “ciphertext validity oracle”.

The main contribution of this paper is to explore a new approach to achieve security against adaptive attacks, which does not rely on a notion of “valid ciphertexts”. Instead, our idea is to generate a “one-time” private key every time the decryption algorithm is run, so that even if an attacker can learn some bits of the one-time private key from each decryption query, this does not allow them to compute a valid private key. We demonstrate how this idea can be implemented with the Gentry-Sahai-Waters levelled homomorphic encryption scheme, and we give an informal explanation of why the known attacks no longer break the system.

One of the recent focus within the auction field has been multi-attribute auctions where buyer is not restricted to selecting the best option only by price but also other attributes. Due to the increase in the awareness of securing private information, in this paper, we design a secure reverse multi-attribute first-price auction scheme, in which the auction is processed on the bidders’ encrypted bids by multiple auctioneer servers. As a result, auctioneer servers can determine the winner without knowing the real value of bids, which let bidder’s privacy would not be revealed. At last, an analysis on the privacy of bids is conducted.