Kwangsu Lee

Kwangsu Lee

Cloud computing can provide a flexible way to effectively share data among multiple users since it can overcome the time and location constraints of computing resource usage. However, the users of cloud computing are still reluctant to share sensitive data to a cloud server since the cloud server should be treated as an untrusted entity. In order to support secure and efficient data sharing in cloud computing environment, Wei et al. recently extended the concept of identity-based encryption (IBE) to support key revocation and ciphertext update functionalities, and proposed a revocable-storage identity-based encryption (RS-IBE) scheme. In this paper, we show that the RS-IBE scheme of Wei et al. does not satisfy the correctness property of RS-IBE. In addition, we propose a method to modify the existing RS-IBE scheme to be a correct and secure scheme.

Kwangsu Lee

Cloud storage is a new computing paradigm that allows users to store their data in the cloud and access them anytime anywhere through the Internet. To address the various security issues that may arise in the cloud storage accessed by a large number of users, cryptographic encryption should be considered. Currently, researches on revocable attribute-based encryption (RABE) systems, which provide user revocation function and ciphertext update function by extending attribute-based encryption (ABE) systems that provide access control to ciphertexts, are actively being studied. Recently, Xu et al. proposed a new RABE scheme that combines ABE and identity-based encryption (IBE) schemes to efficiently handle ciphertext update and user revocation functionality. In this paper, we show that there is a serious security problem in Xu et al.'s RABE scheme such that a cloud server can obtain the plaintext information of stored ciphertexts by gathering invalidated credentials of revoked users. Additionally, we also show that the RABE scheme of Xu et al. can be secure in a weaker security model where the cloud server cannot obtain any invalidated credentials of revoked users.

Jieun Eom, Dong Hoon Lee, Kwangsu Lee

Order-revealing encryption is a useful cryptographic primitive that provides range queries on encrypted data since anyone can compare the order of plaintexts by running a public comparison algorithm. Most studies on order-revealing encryption focus only on comparing ciphertexts generated by a single client, and there is no study on comparing ciphertexts generated by multiple clients. In this paper, we propose the concept of multi-client order-revealing encryption that supports comparisons not only on ciphertexts generated by one client but also on ciphertexts generated by multiple clients. We also define a simulation-based security model for multi-client order-revealing encryption. The security model is defined with respect to the leakage function which quantifies how much information is leaked from the scheme. Next, we present two specific multi-client order-revealing encryption schemes with different leakage functions in bilinear maps and prove their security in the random oracle model. Finally, we give the implementation of the proposed schemes and suggest methods to improve the performance of ciphertext comparisons.

Kwangsu Lee

A block cipher is a bijective function that transforms a plaintext to a ciphertext. A block cipher is a principle component in a cryptosystem because the security of a cryptosystem depends on the security of a block cipher. A Feistel network is the most widely used method to construct a block cipher. This structure has a property such that it can transform a function to a bijective function. But the previous Feistel network is unsuitable to construct block ciphers that have large input-output size. One way to construct block ciphers with large input-output size is to use an unbalanced Feistel network that is the generalization of a previous Feistel network. There have been little research on unbalanced Feistel networks and previous work was about some particular structures of unbalanced Feistel networks. So previous work didn't provide a theoretical base to construct block ciphers that are secure and efficient using unbalanced Feistel networks. In this thesis, we analyze the minimal number of rounds of pseudo-random permutation generators that use unbalanced Feistel networks. That is, after categorizing unbalanced Feistel networks as source-heavy structures and target-heavy structures, we analyze the minimal number of rounds of pseudo-random permutation generators that use each structure. Therefore, in order to construct a block cipher that is secure and efficient using unbalanced Feistel networks, we should follow the results of this thesis. Additionally, we propose a new unbalanced Feistel network that has some advantages such that it can extend a previous block cipher with small input-output size to a new block cipher with large input-output size. We also analyze the minimum number of rounds of a pseudo-random permutation generator that uses this structure.

Kwangsu Lee

Predicate encryption is a new paradigm of public key encryption that enables searches on encrypted data. Using the predicate encryption, we can search keywords or attributes on encrypted data without decrypting the ciphertexts. In predicate encryption, a ciphertext is associated with attributes and a token corresponds to a predicate. The token that corresponds to a predicate $f$ can decrypt the ciphertext associated with attributes $x$ if and only if $f(x)=1$. Hidden vector encryption (HVE) is a special kind of predicate encryption. In this thesis, we consider the efficiency, the generality, and the security of HVE schemes. The results of this thesis are described as follows. The first results of this thesis are efficient HVE schemes where the token consists of just four group elements and the decryption only requires four bilinear map computations, independent of the number of attributes in the ciphertext. The construction uses composite order bilinear groups and is selectively secure under the well-known assumptions. The second results are efficient HVE schemes that are secure under any kind of pairing types. To achieve our goals, we proposed a general framework that converts HVE schemes from composite order bilinear groups to prime order bilinear groups. Using the framework, we convert the previous HVE schemes from composite order bilinear groups to prime order bilinear groups. The third results are fully secure HVE schemes with short tokens. Previous HVE schemes were proven to be secure only in the selective security model where the capabilities of the adversaries are severely restricted. Using the dual system encryption techniques, we construct fully secure HVE schemes with match revealing property in composite order groups.

Kwangsu Lee

Predicate encryption is a new type of public key encryption that enables searches on encrypted data. By using predicate encryption, we can search keywords or attributes on encrypted data without decrypting ciphertexts. Hidden vector encryption (HVE) is a special kind of predicate encryption. HVE supports the evaluation of conjunctive equality, comparison, and subset operations between attributes in ciphertexts and attributes in tokens. In this paper, we construct efficient HVE schemes in prime order bilinear groups derived from previous HVE schemes in composite order bilinear groups, and prove their selective security under simple assumptions. To achieve this result, we present a conversion method that transforms HVE schemes from composite order bilinear groups into prime order bilinear groups. Our method supports any types of prime order bilinear groups and uses simple assumptions.

Seunghwan Park, Dong Hoon Lee, Kwangsu Lee

In identity-based encryption (IBE) systems, an efficient key delegation method to manage a large number of users and an efficient key revocation method to handle the dynamic credentials of users are needed. Revocable hierarchical IBE (RHIBE) can provide these two methods by organizing the identities of users as a hierarchy and broadcasting an update key for non-revoked users per each time period. To provide the key revocation functionality, previous RHIBE schemes use a tree-based revocation scheme. However, this approach has an inherent limitation such that the number of update key elements depends on the number of revoked users. In this paper, we propose two new RHIBE schemes in multilinear maps that use the public-key broadcast encryption scheme instead of using the tree-based revocation scheme to overcome the mentioned limitation. In our first RHIBE scheme, the number of private key elements and update key elements is reduced to $O(\ell)$ and $O(\ell)$ respectively where $\ell$ is the depth of a hierarchical identity. In our second RHIBE scheme, we can further reduce the number of private key elements from $O(\ell)$ to $O(1)$.

Kwangsu Lee, Jong Hwan Park, Dong Hoon Lee

Anonymous Hierarchical Identity-Based Encryption (HIBE) is an extension of Identity-Based Encryption (IBE), and it provides not only a message hiding property but also an identity hiding property. Anonymous HIBE schemes can be applicable to anonymous communication systems and public key encryption systems with keyword searching. However, previous anonymous HIBE schemes have some disadvantages that the security was proven in the weaker model, the size of ciphertexts is not short, or the construction was based on composite order bilinear groups. In this paper, we propose the first efficient anonymous HIBE scheme with short ciphertexts in prime order (asymmetric) bilinear groups, and prove its security in the full model with an efficient reduction. To achieve this, we use the dual system encryption methodology of Waters. We also present the benchmark results of our scheme by measuring the performance of our implementation.

Kwangsu Lee, Dong Hoon Lee, Moti Yung

The notion of aggregate signature has been motivated by applications and it enables any user to compress different signatures signed by different signers on different messages into a short signature. Sequential aggregate signature, in turn, is a special kind of aggregate signature that only allows a signer to add his signature into an aggregate signature in sequential order. This latter scheme has applications in diversified settings such as in reducing bandwidth of certificate chains and in secure routing protocols. Lu, Ostrovsky, Sahai, Shacham, and Waters (EUROCRYPT 2006) presented the first sequential aggregate signature scheme in the standard model. The size of their public key, however, is quite large (i.e., the number of group elements is proportional to the security parameter), and therefore, they suggested as an open problem the construction of such a scheme with short keys. In this paper, we propose the first sequential aggregate signature schemes with short public keys (i.e., a constant number of group elements) in prime order (asymmetric) bilinear groups that are secure under static assumptions in the standard model. Furthermore, our schemes employ a constant number of pairing operations per message signing and message verification operation. Technically, we start with a public-key signature scheme based on the recent dual system encryption technique of Lewko and Waters (TCC 2010). This technique cannot directly provide an aggregate signature scheme since, as we observed, additional elements should be published in a public key to support aggregation. Thus, our constructions are careful augmentation techniques for the dual system technique to allow it to support sequential aggregate signature schemes. We also propose a multi-signature scheme with short public parameters in the standard model.

Kwangsu Lee, Dong Hoon Lee

Aggregate signatures allow anyone to combine different signatures signed by different signers on different messages into a single short signature. An ideal aggregate signature scheme is an identity-based aggregate signature (IBAS) scheme that supports full aggregation since it can reduce the total transmitted data by using an identity string as a public key and anyone can freely aggregate different signatures. Constructing a secure IBAS scheme that supports full aggregation in bilinear maps is an important open problem. Recently, Yuan {\it et al.} proposed an IBAS scheme with full aggregation in bilinear maps and claimed its security in the random oracle model under the computational Diffie-Hellman assumption. In this paper, we show that there exists an efficient forgery attacker on their IBAS scheme and their security proof has a serious flaw.