Receiver selective opening (RSO) attack for public key encryption (PKE) captures a situation where one sender sends messages to multiple receivers, an adversary can corrupt a set of receivers and get their messages and secret keys. Security against RSO attack for a PKE scheme ensures confidentiality of other uncorrupted receivers' ciphertexts. Among all of the RSO security notions, simulation-based RSO security against chosen ciphertext attack (SIM-RSO-CCA security) is the strongest notion. In this paper, we explore constructions of SIM-RSO-CCA secure PKE from various computational assumptions. Toward this goal, we show that a SIM-RSO-CCA secure PKE scheme can be constructed based on an IND-CPA secure PKE scheme and a designated-verifier non-interactive zero-knowledge (DV-NIZK) argument satisfying one-time simulation soundness. Moreover, we give the first construction of DV-NIZK argument satisfying one-time simulation soundness. Consequently, through our generic construction, we obtain the first SIM-RSO-CCA secure PKE scheme under the computational Diffie-Hellman (CDH) or learning parity with noise (LPN) assumption.

Collecting and analyzing personal data is important in modern information applications. Though the privacy of data providers should be protected, the need to track certain data providers often arises, such as tracing specific patients or adversarial users. Thus, tracking only specific persons without revealing normal users' identities is quite important for operating information systems using personal data. It is difficult to know in advance the rules for specifying the necessity of tracking since the rules are derived by the analysis of collected data. Thus, it would be useful to provide a general way that can employ any data analysis method regardless of the type of data and the nature of the rules. In this paper, we propose a privacy-preserving data analysis construction that allows an authority to detect specific users while other honest users are kept anonymous. By using the cryptographic techniques of group signatures with message-dependent opening (GS-MDO) and public key encryption with non-interactive opening (PKENO), we provide a correspondence table that links a user and data in a secure way, and we can employ any anonymization technique and data analysis method. It is particularly worth noting that no “big brother” exists, meaning that no single entity can identify users who do not provide anomaly data, while bad behaviors are always traceable. We show the result of implementing our construction. Briefly, the overhead of our construction is on the order of 10 ms for a single thread. We also confirm the efficiency of our construction by using a real-world dataset.

Searchable encryption with advanced query function is an important technique in today's cloud environment. To date, in the public key setting, the best query function supported by the previous schemes are conjunctive or disjunctive keyword search, which are elementary but not enough to satisfy the user's query requirements. In this paper, we make a progress for constructing a searchable public key encryption scheme with advanced query function called simple Boolean keyword search. To create our scheme, we proposed a keywords conversion method that projects the index and query keywords into a group of vectors. Based on a combination of these obtained vectors and an adaptively secure inner product encryption scheme, a public key encryption with simple Boolean keyword search scheme is proposed. We also present both theoretical and experimental analysis to show the effectiveness of this scheme. To the best of our knowledge, it is the first time to give a searchable public key encryption scheme supporting queries like q1op1q2op2…opi-1qiopi…opn-1qn, where opi is a logical operator which can be and(∨) or or(∧) and qi is a keyword.

The enhanced chosen-ciphertext security (ECCA) is motivated by the concept of randomness recovering encryption, which was presented by Dana Dachman-Soled et al. in PKC 2014 [9]. ECCA security is the enhanced version of CCA security. CCA security often appears to be somewhat too strong, so ECCA security is also too strong: there exist encryption schemes that are not ECCA secure but still have some practical application. Canetti et al. proposed a relaxed variant of CCA security called Replayable CCA (RCCA) security in CRYPTO 2003 [3]. In this paper, we propose a relaxed variant of ECCA security called Replayable security (RECCA). RECCA security is the enhanced version of RCCA security. Since RCCA security suffices for the most existing application of CCA security, RECCA security also suffices for them, too. Moreover, RECCA security provides a useful general version of security against active attacks.

The concept of threshold public key encryption (TPKE) with the special property called key re-splittability (re-splittable TPKE, for short) was introduced by Hanaoka et al. (CT-RSA 2012), and used as one of the building blocks for constructing their proxy re-encryption scheme. In a re-splittable TPKE scheme, a secret key can be split into a set of secret key shares not only once, but also multiple times, and the security of the TPKE scheme is guaranteed as long as the number of corrupted secret key shares under the same splitting is smaller than the threshold. In this paper, we show several new constructions of a re-splittable TPKE scheme by extending the previous (ordinary) TPKE schemes. All of our proposed schemes are based on discrete logarithm (DL)-type assumptions. Therefore, our results suggest that key re-splittability is a very natural property for DL-type TPKE schemes.

Two new authenticated key agreement protocols in the certificateless setting are presented in this paper. Both are proved secure in the extended Canetti-Krawczyk model, under the BDH assumption. The first one is more efficient than the Lippold et al.'s (LBG) protocol, and is proved secure in the same security model. The second protocol is proved secure under the Swanson et al.'s security model, a weaker model. As far as we know, our second proposed protocol is the first one proved secure in the Swanson et al.'s security model. If no pre-computations are done, the first protocol is about 26% faster than LBG, and the second protocol is about 49% faster than LBG, and about 31% faster than the first one. If pre-computations of some operations are done, our two protocols remain faster.

The primitive called public key encryption with non-interactive opening (PKENO) is a class of public key encryption (PKE) with additional functionality. By using this, a receiver of a ciphertext can prove that the ciphertext is an encryption of a specified message in a publicly verifiable manner. In some situation that a receiver needs to claim that a ciphertext is NOT decrypted to a specified message, if he/she proves the fact by using PKENO straightforwardly, the real message of the ciphertext is revealed and a verifier checks that it is different from the specified message about which the receiver wants to prove. However, this naive solution is problematic in terms of privacy. Inspired by this problem, we propose the notion of disavowable public key encryption with non-interactive opening (disavowable PKENO) where, with respect to a ciphertext and a message, the receiver of the ciphertext can issue a proof that the plaintext of the ciphertext is NOT the message. Also, we give a concrete construction. Specifically, a disavowal proof in our scheme consists of 61 group elements. The proposed disavowable PKENO scheme is provably secure in the standard model under the decisional linear assumption and strong unforgeability of the underlying one-time signature scheme.

Up until now, the best public key encryption with multi-dimensional range query (PKMDRQ) scheme has two problems which need to be resolved. One is that the scheme is selectively secure. The other is that the time of decryption is long. To address these problems, we present a method of converting a predicate encryption supporting inner product (IPE) scheme into a PKMDRQ scheme. By taking advantage of this approach, an instance is also proposed. The comparison between the previous work and ours shows that our scheme is more efficient over the time complexity. Moreover, our scheme is adaptively secure.

In this letter, we formally present the definition of KDM-CCA1 security in public key setting, which falls in between the existing KDM-CPA and KDM-CCA2 security. We also prove that if a public key encryption scheme is CCA1 secure and has the properties of secret-key multiplication (or addition) homomorphism, and conditioned plaintext-restorability, then it is KDM-CCA1 secure w.r.t. two ensembles of functions that had been used in [15],[17], respectively. For concrete scheme, we show that the (tailored) Damgård's Elgamal scheme achieves this KDM-CCA1 security based on different assumptions.

We consider the problem of constructing public-key encryption (PKE) schemes that are resilient to a-posteriori chosen-ciphertext and key-leakage attacks (LR-CCA2). In CTYPTO'09, Naor and Segev proved that the Naor-Yung generic construction of PKE which is secure against chosen-ciphertext attack (CCA2) is also secure against key-leakage attacks. They also presented a variant of the Cramer-Shoup cryptosystem, and showed that this PKE scheme is LR-CCA2-secure under the decisional Diffie-Hellman assumption. In this paper, we apply the generic construction of “Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption” (EUROCRYPT'02) to generalize the above work of Naor-Segev. In comparing to the first construction of Naor-Segev, ours is more efficient because of not using simulation-sound NIZK. We also extend it to stateful PKE schemes. Concretely, we present the notion of LR-CCA2 attack in the case of stateful PKE, and a generic construction of stateful PKE that is secure against this attack.

Ranking the encrypted documents stored on secure cloud computing servers is becoming prominent with the expansion of the encrypted data collection. In our work, order preserving encryption is employed to pre-rank the encrypted documents. Paillier's additive homomorphic encryption is used to re-rank the top pre-ranked documents of some considerate scale.

This paper shows a simple methodology for shortening a ciphertext of reproducible key encapsulation mechanisms. Specifically, it transforms a key encapsulation mechanism having OW-CCCA security and reproducibility into that of IND-CCA secure in the random oracle model whose ciphertext is shorter. Various existing chosen-ciphertext secure key encapsulation mechanisms (in the standard model) are reproducible, and thus their ciphertext can be shortened by the proposed transformation. The transformed scheme requires only one additional hashing for encryption. This property enables us to implement both the original scheme and the transformed scheme into a single chip simultaneously with small gate-size overhead. Using this chip, a sender can flexibly switch schemes to encrypt a message in a message-by-message manner. Such a use of schemes is also analyzed.

In proxy re-encryption schemes, a semi-trusted entity called a proxy can convert a ciphertext encrypted for Alice into a new ciphertext for Bob without seeing the underlying plaintext. Several proxy re-encryption schemes have been proposed, however, only two schemes which enables the conversion of IBE ciphertexts to PKE ciphertexts has been proposed. One of schemes has some drawbacks such that the size of the re-encrypted ciphertext increases and Bob must be aware of existence of the proxy, which means Bob cannot decrypt a re-encrypted ciphertext with same PKE decryption algorithm. The other one achieves security under Selective-ID model. We propose a new, efficient scheme that enables the conversion of IBE ciphertexts to PKE ciphertexts, and prove full-ID CPA security in the standard model. In our scheme, the size of the re-encrypted ciphertext is optimal and Bob should not aware of existence of the proxy. As far as we know, this is the first IBE-PKE type scheme that holds the above properties.

In this paper, we propose two new chosen-ciphertext (CCA) secure schemes from the computational Diffie-Hellman (CDH) and bilinear computational Diffie-Hellman (BCDH) assumptions. Our first scheme from the CDH assumption is constructed by extending Cash-Kiltz-Shoup scheme. This scheme yields the same ciphertext as that of Hanaoka-Kurosawa scheme (and thus Cramer-Shoup scheme) with cheaper computational cost for encryption. However, key size is still the same as that of Hanaoka-Kurosawa scheme. Our second scheme from the BCDH assumption is constructed by extending Boyen-Mei-Waters scheme. Though this scheme requires a stronger underlying assumption than the CDH assumption, it yields significantly shorter key size for both public and secret keys. Furthermore, ciphertext length of our second scheme is the same as that of the original Boyen-Mei-Waters scheme.

In this paper, we introduce the intermediate hashed Diffie-Hellman (IHDH) assumption which is weaker than the hashed DH (HDH) assumption (and thus the decisional DH assumption), and is stronger than the computational DH assumption. We then present two public key encryption schemes with short ciphertexts which are both chosen-ciphertext secure under this assumption. The short-message scheme has smaller size of ciphertexts than Kurosawa-Desmedt (KD) scheme, and the long-message scheme is a KD-size scheme (with arbitrary plaintext length) which is based on a weaker assumption than the HDH assumption.

The Hidden Vector Encryption scheme is one of the searchable public key encryption schemes that allow for searching encrypted data. The Hidden Vector Encryption scheme supports conjunctive equality, comparison, and subset queries, as well as arbitrary conjunctive combinations of these queries. In a Hidden Vector Encryption scheme, a receiver generates a token for a vector of searchable components and sends the token to a query server which has the capability to evaluate it on encrypted data. All of the existing Hidden Vector Encryption schemes, which are all pairing-based, require token elements and pairing computations proportional to the number of searchable components in the token. In this paper, we suggest an improved paring-based Hidden Vector Encryption scheme where the token elements and pairing computations are independent of the number of searchable components. Namely, for an arbitrary conjunctive search query, the token is of size O(1) and the query server only needs O(1) pairing computations. The latter improvement in particular might be very attractive to a query server in a larger search system with many users. To achieve our goal, we introduce a novel technique to generate a token, which may be of independent interest.

To deal with the problem of secret key exposure, Dodis, Katz, Xu and Yung [6] proposed a key-insulated public key encryption (KIE), which uses the secure helper key to update the secret key more often and helps to minimize the damage overall. We take this idea further in improving the helper key security by introducing an auxiliary helper key besides of the main helper key. The auxiliary helper key is used less than the main helper key and can help the system to reduce the damage even in case of helper key exposure. This paper give two different schemes of KIE with auxiliary helper key. There are trade-offs between public key length and ciphertext size, as well as between encryption algorithms and decryption algorithms in these two schemes. With these trade-offs, it is flexible to choose an efficient one to implement in reality. We also show concrete constructions with chosen-ciphertext security. The formal security proofs for all schemes are given in this paper, based on the CBDH assumption [2] in the random oracle model.

In this paper, we will show that the status certificate-based encryption scheme proposed by Yum and Lee is insecure against key substitution attacks by two types of attackers.