Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Asia Conference on Computer and Communications Security (ASIA CCS)

Hierarchical Identity-based Puncturable Encryption from Lattices with Application to Forward Security

Priyanka Dutta, Mei Jiang, Dung Hoang Duong, Willy Susilo, Kazuhide Fukushima, Shinsaku Kiyomoto

Published May 24, 2022• 15 citations
Publisher

Abstract

Puncturable encryption (PE), introduced by Green and Miers at IEEE S$&$P 2015, allows recipients to update their decryption keys to revoke decryption capability for selected messages without communicating with senders. In general, it allows users to control which ciphertexts their keys may decrypt. The notion of PE has been found very useful in many applications, such as asynchronous messaging systems, group messaging systems, public-key watermarking schemes, secure cloud emails, and many more. In this paper, we introduce a new primitive called hierarchical identity-based puncturable encryption (HIBPE) that enhances the concept of PE by allowing more general key delegation and flexible key puncture. It enhances the capability of the data owner for multi-level encrypted data sharing within a group of users by delegating the decryption keys of the users in higher-levels to generate decryption keys for the users in lower-levels. Moreover, it allows users to puncture (update) their decryption keys on tags so that a decryption key punctured on a tag can no longer decrypt ciphertexts under this tag. In addition, to control access to the users' data, the higher-level users can further puncture the delegated keys (for lower-level users) with some tags such that the part of the owner's data is labeled by the punctured tags will no longer be accessible by the lower-level users. These features offer an efficient and flexible solution for encrypted data sharing as well as data-access control mechanisms in a hierarchical setting. We propose the formal definition and security model for HIBPE schemes and provide a concrete HIBPE scheme based on the hardness of the learning with errors problem in the standard model. Further, we provide a generic construction of forward secure hierarchical identity-based encryption (fs-HIBE) from HIBPE, which enables the first quantum-safe construction of fs-HIBE in the standard model. Moreover, this is the first fs-HIBE construction by exploring the concept of PE. The proposed fs-HIBE provides quantum-safe protection for secret keys from exposure in multi-level encrypted data sharing by evolving the keys with time.

DOI
10.1145/3488932.3517400

Related papers

Privacy‐Enhanced Data Sharing Systems from Hierarchical ID‐Based Puncturable Functional Encryption with Inner Product Predicates

Cheng-Yi Lee, Ziyuan Liu, Masahiro Mambo +1 more

The emergence of cloud computing enables users to upload data to remote clouds and compute them. This drastically reduces computing and storage costs for users. Considering secure computing for multilevel users in enterprises, the notion of hierarchical identity‐based inner product functional encryption (HIB‐IPFE) is proposed. In this cryptosystem, a sender can encrypt a vector into a ciphertext with a hierarchical identity, while a receiver who possesses a secret key corresponding to the same hierarchical identity and a vector can decrypt the ciphertext and obtain the inner product . However, HIB‐IPFE is not sufficient to capture flexible data sharing and forward security. In this study, we present a notion of hierarchical identity‐based puncturable HIBP‐IPFE. Furthermore, we present a formal definition and security model of HIBP‐IPFE to guarantee data confidentiality and receiver anonymity. Compared with HIB‐IPFE, our proposed scheme enables users to puncture keys on specific tags ensuring that the punctured keys cannot be used to decrypt the ciphertexts associated with those tags. The proposed scheme is provably secure under d ‐DBDHE assumption in the standard model. The experimental results indicate that our scheme is more practical in cloud computing, with superior functionality.

IET Information Security•Jan 1, 2024•1 citation

Efficient hierarchical identity based encryption scheme in the standard model over lattices

Fenghe Wang, Chunxiao Wang, Zhenhua Liu

Using lattice basis delegation in a fixed dimension, we propose an efficient lattice-based hierarchical identity based encryption (HIBE) scheme in the standard model whose public key size is only ( dm 2 + mn ) log q bits and whose message-ciphertext expansion factor is only log q , where d is the maximum hierarchical depth and ( n , m , q ) are public parameters. In our construction, a novel public key assignment rule is used to averagely assign one random and public matrix to two identity bits, which implies that d random public matrices are enough to build the proposed HIBE scheme in the standard model, compared with the case in which 2 d such public matrices are needed in the scheme proposed at Crypto 2010 whose public key size is (2 dm 2 + mn + m ) log q . To reduce the message-ciphertext expansion factor of the proposed scheme to log q , the encryption algorithm of this scheme is built based on Gentry’s encryption scheme, by which m 2 bits of plaintext are encrypted into m 2 log q bits of ciphertext by a one time encryption operation. Hence, the presented scheme has some advantages with respect to not only the public key size but also the message-ciphertext expansion factor. Based on the hardness of the learning with errors problem, we demonstrate that the scheme is secure under selective identity and chosen plaintext attacks.

Frontiers of Information Technology & Electronic Engineering•Aug 1, 2016•5 citations

Lattice-Based Puncturable Identity-Based Encryption with Keyword Search for Cloud Storage

Bo Yang, Ruiqiao Zhao, Jie Wei

To ensure the privacy and security of the stored data, the data can be encrypted first and then stored on the cloud. However, it faces the problem that users cannot search keywords in a large amount of data, which limits the flexibility of file sharing in the cloud environment. Searchable encryption can effectively support users to retrieve encrypted data in the cloud. Public key searchable encryption (PEKS) is used to retrieve the target encrypted data by searching specific keywords. However, the development of quantum computers has led to attacks on conventional encryption algorithms, and it is necessary to design searchable encryption schemes that can resist quantum attacks. Therefore, we propose a lattice puncturable PEKS scheme. Besides resisting quantum attacks, the proposed scheme attains efficient and flexible user revocation. Firstly, identity-based encryption is employed to minimize the complexity of key management. Secondly, the puncturable encryption technology is integrated into the proposed encryption to revoke the decryption capability for selected messages, enabling authorized recipients to repeatedly update their decryption keys to retrieve the currently encrypted messages. Finally, we prove the security of our scheme under the indistinguishability against chosen keyword attack (IND-PUN-sID-CKA), and conduct a comparison with other schemes to emphasize its advantages. Although the scheme does not have an edge in size, it holds an advantage in key update after adding the puncture function and also realizes higher security.

•Mar 21, 2025•2 citations

Generic Construction of Forward-Secure Identity-Based Encryption

Yang Lu, Jiguo Li

The primitive of forward-secure identity-based encryption was proposed in order to minimize the damage of private key exposure in identity-based encryption setting. This new primitive guarantees that even if the current private keys are compromised, it is not possible to compromise past secret keys and past communications. In this paper, we propose a generic construction of forward-secure identity-based encryption. To do so, we first introduce a relaxed variant of hierarchical identity-based encryption called identity-based binary tree encryption and construct a concrete identity-based binary tree encryption scheme that is provably chosen-ciphertext secure in the standard model. We then show how to generically construct forward-secure identity-based encryption from identity-based binary tree encryption. Based on the proposed identity-based binary tree encryption scheme, we obtain a forward-secure identity-based encryption scheme with chosen-ciphertext security in the standard model.

Journal of Computers•Dec 1, 2012•3 citations

Tightly Secure Hierarchical Identity-Based Encryption

Roman Langrehr, Jiaxin Pan

Abstract We construct the first tightly secure hierarchical identity-based encryption (HIBE) scheme based on standard assumptions, which solves an open problem from Blazy, Kiltz, and Pan (CRYPTO 2014). At the core of our constructions is a novel randomization technique that enables us to randomize user secret keys for identities with flexible length. The security reductions of previous HIBEs lose at least a factor of Q, which is the number of user secret key queries. Different to that, the security loss of our schemes is only dependent on the security parameter. Our schemes are adaptively secure based on the Matrix Diffie-Hellman assumption, which is a generalization of standard Diffie-Hellman assumptions such as k-Linear. We have two tightly secure constructions, one with constant ciphertext size, and the other with tighter security at the cost of linear ciphertext size. Among other things, our schemes imply the first tightly secure identity-based signature scheme by a variant of the Naor transformation.

Journal of Cryptology•Sep 15, 2020•16 citations

Lattice-based public key encryption with equality test in standard model, revisited.

Dung Hoang Duong, Partha Sarathi Roy, Willy Susilo +3 more

Public key encryption with equality test (PKEET) allows testing whether two ciphertexts are generated by the same message or not. PKEET is a potential candidate for many practical applications like efficient data management on encrypted databases. Potential applicability of PKEET leads to intensive research from its first instantiation by Yang et al. (CT-RSA 2010). Most of the followup constructions are secure in the random oracle model. Moreover, the security of all the concrete constructions is based on number-theoretic hardness assumptions which are vulnerable in the post-quantum era. Recently, Lee et al. (ePrint 2016) proposed a generic construction of PKEET schemes in the standard model and hence it is possible to yield the first instantiation of PKEET schemes based on lattices. Their method is to use a $2$-level hierarchical identity-based encryption (HIBE) scheme together with a one-time signature scheme. In this paper, we propose, for the first time, a direct construction of a PKEET scheme based on the hardness assumption of lattices in the standard model. More specifically, the security of the proposed scheme is reduces to the hardness of the Learning With Errors problem.

arXiv:2005.03178•May 7, 2020•0 citations
Puncturable encryption (PE), introduced by Green and Miers at IEEE S&P 2015, allows recipients to update their decryption keys to revoke decryption capability for selected messages without communicating with senders. In general, it allows users to control which ciphertexts their keys may decrypt. The notion of PE has been found very useful in many applications, such as asynchronous messaging systems, group messaging systems, public-key watermarking schemes, secure cloud emails, and many more. In this paper, we introduce a new primitive called hierarchical identity-based puncturable encryption (HIBPE) that enhances the concept of PE by allowing more general key delegation and flexible key puncture. It enhances the capability of the data owner for multi-level encrypted data sharing within a group of users by delegating the decryption keys of the users in higher-levels to generate decryption keys for the users in lower-levels. Moreover, it allows users to puncture (update) their decryption keys on tags so that a decryption key punctured on a tag can no longer decrypt ciphertexts under this tag. In addition, to control access to the users' data, the higher-level users can further puncture the delegated keys (for lower-level users) with some tags such that the part of the owner's data is labeled by the punctured tags will no longer be accessible by the lower-level users. These features offer an efficient and flexible solution for encrypted data sharing as well as data-access control mechanisms in a hierarchical setting. We propose the formal definition and security model for HIBPE schemes and provide a concrete HIBPE scheme based on the hardness of the learning with errors problem in the standard model. Further, we provide a generic construction of forward secure hierarchical identity-based encryption (fs-HIBE) from HIBPE, which enables the first quantum-safe construction of fs-HIBE in the standard model. Moreover, this is the first fs-HIBE construction by exploring the concept of PE. The proposed fs-HIBE provides quantum-safe protection for secret keys from exposure in multi-level encrypted data sharing by evolving the keys with time.
The emergence of cloud computing enables users to upload data to remote clouds and compute them. This drastically reduces computing and storage costs for users. Considering secure computing for multilevel users in enterprises, the notion of hierarchical identity‐based inner product functional encryption (HIB‐IPFE) is proposed. In this cryptosystem, a sender can encrypt a vector into a ciphertext with a hierarchical identity, while a receiver who possesses a secret key corresponding to the same hierarchical identity and a vector can decrypt the ciphertext and obtain the inner product . However, HIB‐IPFE is not sufficient to capture flexible data sharing and forward security. In this study, we present a notion of hierarchical identity‐based puncturable HIBP‐IPFE. Furthermore, we present a formal definition and security model of HIBP‐IPFE to guarantee data confidentiality and receiver anonymity. Compared with HIB‐IPFE, our proposed scheme enables users to puncture keys on specific tags ensuring that the punctured keys cannot be used to decrypt the ciphertexts associated with those tags. The proposed scheme is provably secure under d ‐DBDHE assumption in the standard model. The experimental results indicate that our scheme is more practical in cloud computing, with superior functionality.
Using lattice basis delegation in a fixed dimension, we propose an efficient lattice-based hierarchical identity based encryption (HIBE) scheme in the standard model whose public key size is only ( dm 2 + mn ) log q bits and whose message-ciphertext expansion factor is only log q , where d is the maximum hierarchical depth and ( n , m , q ) are public parameters. In our construction, a novel public key assignment rule is used to averagely assign one random and public matrix to two identity bits, which implies that d random public matrices are enough to build the proposed HIBE scheme in the standard model, compared with the case in which 2 d such public matrices are needed in the scheme proposed at Crypto 2010 whose public key size is (2 dm 2 + mn + m ) log q . To reduce the message-ciphertext expansion factor of the proposed scheme to log q , the encryption algorithm of this scheme is built based on Gentry’s encryption scheme, by which m 2 bits of plaintext are encrypted into m 2 log q bits of ciphertext by a one time encryption operation. Hence, the presented scheme has some advantages with respect to not only the public key size but also the message-ciphertext expansion factor. Based on the hardness of the learning with errors problem, we demonstrate that the scheme is secure under selective identity and chosen plaintext attacks.
To ensure the privacy and security of the stored data, the data can be encrypted first and then stored on the cloud. However, it faces the problem that users cannot search keywords in a large amount of data, which limits the flexibility of file sharing in the cloud environment. Searchable encryption can effectively support users to retrieve encrypted data in the cloud. Public key searchable encryption (PEKS) is used to retrieve the target encrypted data by searching specific keywords. However, the development of quantum computers has led to attacks on conventional encryption algorithms, and it is necessary to design searchable encryption schemes that can resist quantum attacks. Therefore, we propose a lattice puncturable PEKS scheme. Besides resisting quantum attacks, the proposed scheme attains efficient and flexible user revocation. Firstly, identity-based encryption is employed to minimize the complexity of key management. Secondly, the puncturable encryption technology is integrated into the proposed encryption to revoke the decryption capability for selected messages, enabling authorized recipients to repeatedly update their decryption keys to retrieve the currently encrypted messages. Finally, we prove the security of our scheme under the indistinguishability against chosen keyword attack (IND-PUN-sID-CKA), and conduct a comparison with other schemes to emphasize its advantages. Although the scheme does not have an edge in size, it holds an advantage in key update after adding the puncture function and also realizes higher security.
The primitive of forward-secure identity-based encryption was proposed in order to minimize the damage of private key exposure in identity-based encryption setting. This new primitive guarantees that even if the current private keys are compromised, it is not possible to compromise past secret keys and past communications. In this paper, we propose a generic construction of forward-secure identity-based encryption. To do so, we first introduce a relaxed variant of hierarchical identity-based encryption called identity-based binary tree encryption and construct a concrete identity-based binary tree encryption scheme that is provably chosen-ciphertext secure in the standard model. We then show how to generically construct forward-secure identity-based encryption from identity-based binary tree encryption. Based on the proposed identity-based binary tree encryption scheme, we obtain a forward-secure identity-based encryption scheme with chosen-ciphertext security in the standard model.
Abstract We construct the first tightly secure hierarchical identity-based encryption (HIBE) scheme based on standard assumptions, which solves an open problem from Blazy, Kiltz, and Pan (CRYPTO 2014). At the core of our constructions is a novel randomization technique that enables us to randomize user secret keys for identities with flexible length. The security reductions of previous HIBEs lose at least a factor of Q, which is the number of user secret key queries. Different to that, the security loss of our schemes is only dependent on the security parameter. Our schemes are adaptively secure based on the Matrix Diffie-Hellman assumption, which is a generalization of standard Diffie-Hellman assumptions such as k-Linear. We have two tightly secure constructions, one with constant ciphertext size, and the other with tighter security at the cost of linear ciphertext size. Among other things, our schemes imply the first tightly secure identity-based signature scheme by a variant of the Naor transformation.
Public key encryption with equality test (PKEET) allows testing whether two ciphertexts are generated by the same message or not. PKEET is a potential candidate for many practical applications like efficient data management on encrypted databases. Potential applicability of PKEET leads to intensive research from its first instantiation by Yang et al. (CT-RSA 2010). Most of the followup constructions are secure in the random oracle model. Moreover, the security of all the concrete constructions is based on number-theoretic hardness assumptions which are vulnerable in the post-quantum era. Recently, Lee et al. (ePrint 2016) proposed a generic construction of PKEET schemes in the standard model and hence it is possible to yield the first instantiation of PKEET schemes based on lattices. Their method is to use a 222-level hierarchical identity-based encryption (HIBE) scheme together with a one-time signature scheme. In this paper, we propose, for the first time, a direct construction of a PKEET scheme based on the hardness assumption of lattices in the standard model. More specifically, the security of the proposed scheme is reduces to the hardness of the Learning With Errors problem.