Recently, Luo et al. proposed an efficient hierarchical identity based encryption (HIBE) scheme with constant size of ciphertexts, and proved its full security under standard assumptions. To construct the scheme, they used the dual system encryption technique of Waters, and devised a method that compresses the tag values of dual system encryption. In this paper, we show that the security proof of Luo et al. is wrong since there exists an algorithm that distinguishes whether it is a simulation or not.

A multisignature (MS) scheme enables a group of signers to produce a compact signature on a common message. In analyzing security of MS schemes, a key registration protocol with proof-of-possession (POP) is considered to prevent rogue key attacks. In this paper, we refine the POP-based security model by formalizing a new strengthened POP model and showing relations between the previous POP models and the new one. We next suggest a MS scheme that achieves: (1) non-interactive signing process, (2) O(1) pairing computations in verification, (3) tight security reduction under the co-CDH assumption, and (4) security under the new strengthened POP model. Compared to the tightly-secure BNN-MS scheme, the verification in ours can be at least 7 times faster at the 80-bit security level and 10 times faster at the 128-bit security level. To achieve our goal, we introduce a novel and simple POP generation method that can be viewed as a one-time signature without random oracles. Our POP technique can also be applied to the LOSSW-MS scheme (without random oracles), giving the security in the strengthened POP model.

Recently, Hu et al. have suggested a fully secure hierarchical identity-based encryption (HIBE) scheme that achieves constant size ciphertext and tight security reduction. Their construction was based on Gentry's IBE scheme that supports their security proof. In this paper, we show that their security proof is incorrect. We point out the difference between Gentry's proof and that of Hu et al., and we show that the security of Hu et al.'s HIBE scheme cannot be reduced to their claimed complexity 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.

In 2006, Chatterjee and Sarkar proposed a hierarchical identity-based encryption (HIBE) scheme which can support an unbounded number of identity levels. This property is particularly useful in providing forward secrecy by embedding time components within hierarchical identities. In this paper we show that their scheme does not provide the claimed property. Our analysis shows that if the number of identity levels becomes larger than the value of a fixed public parameter, an unintended receiver can reconstruct a new valid ciphertext and decrypt the ciphertext using his or her own private key. The analysis is similarly applied to a multi-receiver identity-based encryption scheme presented as an application of Chatterjee and Sarkar's HIBE scheme.

In INDOCRYPT 2006, Chatterjee and Sarkar suggested a multi-receiver identity-based key encapsulation mechanism that is secure in the full model without random oracles. Until now, it has been believed that their scheme is the only one to provide such a security feature, while achieving sub-linear size ciphertext. In this letter, we show that their scheme is insecure in the sense that any revoked user can retrieve a message encryption key, even without colluding with other revoked users. Our attack comes from an analysis of a publicly computable surjective function used in the scheme.

Broadcast encryption scheme with personalized messages (BEPM) is a new primitive that allows a broadcaster to encrypt both a common message and individual messages. BEPM is necessary in applications where individual messages include information related to user's privacy. Recently, Fujii et al. suggested a BEPM that is extended from a public key broadcast encryption (PKBE) scheme by Boneh, Gentry, and Waters. In this paper, we point out that 1) Conditional Access System using Fujii et al.'s BEPM should be revised in a way that decryption algorithm takes as input public key as well, and 2) performance analysis of Fujii et al.'s BEPM should be done depending on whether the public key is transmitted along with ciphertext or stored into user's device. Finally, we propose a new BEPM that is transmission-efficient, while preserving O(1) user storage cost. Our construction is based on a PKBE scheme suggested by Park, Kim, Sung, and Lee, which is also considered as being one of the best PKBE schemes.

Recently, Park and Lee suggested a new framework for realizing Identity-Based Encryption (IBE) trapdoor called ‘two-equation-revocation’, and proposed a new IBE system that makes use of a Map-To-Point hash function. In this paper, we present a variant of the PL system by giving a simple way to remove the Map-To-Point hash function from the PL system. Our variant is proven to be secure under non-standard security assumptions, which results in the degradation of security. Instead, our variant can have several efficiency advantages over the PL system: (1) it provides receiver's anonymity, (2) it has no correctness error, (3) it has shorter ciphertext, and (4) it has faster encryption. As a result, (when not considering security assumptions and security losses) our variant is as efficient as the Boneh-Boyen and Sakai-Kasahara IBE systems that are considered as being the most practical ones.