Identity-Based Encryption

Identity-Based Encryption: Pushing the Boundaries of Compactness and Efficiency in a Post-Quantum World

Speakers: Parhat Abla; Huiwen Jia, Yipu Hu, Chunming Tang, Lin Wang

Conference: RSAC 2024

YouTube: https://www.youtube.com/watch?v=kmBAIJQBFIs

Overview

Identity-Based Encryption (IBE), initially conceived by Shamir and first constructed by Boneh and Franklin, represents a powerful generalization of traditional public key encryption. In an IBE system, a user's unique identity (e.g., email address, name) directly serves as their public key, eliminating the need for complex certificate management infrastructure often associated with Public Key Infrastructure (PKI). This streamlined approach makes IBE particularly attractive for resource-constrained environments and applications requiring simplified key management. However, the foundational number-theoretic assumptions underlying many early IBE schemes, such as those based on bilinear maps or quadratic residues, are known to be vulnerable to quantum computing attacks, posing a significant challenge for their long-term security.

This article delves into two distinct yet complementary advancements in the realm of post-quantum IBE, both presented within the same conference session. The first contribution, by Parhat Abla, focuses on constructing a highly compact IBE scheme based on the Learning With Errors (LWE) problem, a robust lattice-based assumption believed to be quantum-resistant. Abla's work introduces a novel technique for achieving an unprecedentedly compact Master Public Key (MPK), significantly improving upon the state-of-the-art in LWE-based IBE. The second contribution, led by Huiwen Jia, addresses the crucial aspect of efficiency in lattice-based IBE by developing an improved preimage sampler for ideal lattices. This sampler offers critical tradeoffs between security and compactness, making the often computationally intensive key extraction procedure more practical.

Together, these works represent significant strides towards the deployment of practical, secure, and compact IBE systems in a future dominated by quantum computers. Abla's research tackles the fundamental problem of public key size, a major hurdle for many cryptographic schemes, while Jia's work enhances the underlying cryptographic primitives necessary for efficient operation. Their combined efforts pave the way for IBE to fulfill its promise as a versatile and efficient encryption paradigm in the post-quantum era.

Background

▶ Watch: Introduction to Identity-Based Encryption (IBE) concepts (0:00)

The journey of Identity-Based Encryption began in 1984 with Adi Shamir's seminal idea, envisioning a cryptographic system where any arbitrary string could function as a public key. This concept was finally realized by Boneh and Franklin in 2001 with the first fully functional IBE scheme. The core appeal of IBE lies in its ability to simplify public key management: a Key Generation Center (KGC), possessing a Master Secret Key (MSK), can generate a user's secret key based on their publicly known identity. Anyone with the Master Public Key (MPK) can then encrypt messages directly to a user's identity, bypassing the certificate issuance, distribution, and revocation complexities inherent in traditional PKI.

The security of IBE schemes is typically defined by notions like adaptive security and selective security. In an adaptively secure scheme, an adversary can query secret keys for identities before choosing a challenge identity. In contrast, selective security requires the adversary to commit to a challenge identity at the outset of the game, before receiving the MPK. Adaptive security is a stronger and more desirable property. Early compact constructions, such as Waters' design, achieved adaptive security as compactly as selective IBE, but these were based on number-theoretic assumptions (e.g., bilinear maps), rendering them vulnerable to quantum attacks.

The advent of quantum computing necessitates a shift to post-quantum cryptography (PQC). Lattice-based cryptography, built on the presumed hardness of problems like Learning With Errors (LWE) and Short Integer Solution (SIS), has emerged as a leading candidate for PQC due to its strong security foundations, versatility, and often good performance. However, designing efficient and compact lattice-based IBE schemes has presented its own set of challenges.

Prior work in lattice-based IBE has grappled with the size of the MPK. The ABB10 scheme, for instance, required O(n) matrices in its MPK, where 'n' relates to the security parameter. More recently, Yam17 improved this to O(log n) matrices, but their scheme relied on Barrington's theorem, making the modulus implicitly defined and thus difficult to parameterize explicitly. This left a critical question: could a lattice-based IBE be constructed with an explicitly defined, even more compact MPK, without resorting to Barrington's theorem?

Furthermore, a fundamental component of many lattice-based cryptographic schemes, including IBE, is the preimage sampling algorithm. This algorithm is essential for the KGC to extract user secret keys. The pioneering work by GPV (Gentry, Peikert, Vaikuntanathan) in 2008 provided a provably secure framework for lattice trapdoor inversion, ensuring that the distribution of generated preimages is independent of the trapdoor, thus preventing statistical attacks that had broken earlier deterministic methods. GPV-IBE can be instantiated on NTRU lattices or hard random lattices. While NTRU-based schemes often show good performance, their implementation can be complex. Gadget-based samplers, such as those by Micciancio and Peikert (MP), are versatile and compatible with LWE, but historically suffered from large sizes. Subsequent improvements by CGM introduced approximate trapdoors for size reduction, and YJW achieved the most compact samplers for hash-and-sign signatures by using a square matrix as the gadget. However, YJW's approach, while compact, introduced relatively large errors in preimages, making it less suitable for applications like GPV-IBE, which require much smaller preimage norms relative to the modulus. The challenge for practical lattice-based IBE, therefore, was to enhance the efficiency and flexibility of these core preimage sampling algorithms while maintaining security and compactness.

Key Findings

▶ Watch: Our compact IBE scheme's main contribution (3:10)

The two talks presented distinct, yet highly impactful, advancements in the field of Identity-Based Encryption, particularly concerning compactness and efficiency in the post-quantum era.

Parhat Abla's Contribution: A More Compact LWE-Based IBE

Abla's primary contribution is the development of an LWE-based IBE scheme featuring an unprecedentedly compact Master Public Key (MPK). Specifically, their construction achieves an MPK size containing O(log n / log log n) matrices. This represents a significant improvement over prior state-of-the-art LWE-based IBE schemes, which required O(n) or O(log n) matrices. Crucially, Abla's scheme is explicitly designed, meaning all parameters can be clearly defined, addressing a limitation of implicitly designed schemes like Yam17.

The cornerstone of this compactness lies in a novel and more efficient LWE-based homomorphic equality test algorithm. This algorithm can compactly test for equality of integers within a range of 0 to log n / log log n. Unlike previous bitwise comparison methods that required O(log n) matrices, Abla's technique leverages Lagrange interpolation in conjunction with L-adic representation to achieve its superior compactness. This breakthrough in homomorphic equality testing directly translates to the reduced MPK size for the overall IBE scheme.

Huiwen Jia's Contribution: Improved Preimage Sampler for Ideal Lattices

Huiwen Jia's work, a collaborative effort with Yipu Hu, Chunming Tang, and Lin Wang, focuses on enhancing the practicality of lattice-based IBE by introducing an improved preimage sampler. This sampler, designed for ideal lattices, offers crucial tradeoffs between security and compactness, providing greater flexibility for parameter selection in real-world applications.

The innovation in Jia's sampler stems from a hybrid approach: it combines the gadget structure of the MP (Micciancio and Peikert) sampler with the semi-random technique of the YJW sampler. This allows for the generation of preimages with significantly smaller norms compared to YJW, which is essential for schemes like GPV-IBE. Furthermore, the sampler incorporates the non-spherical Gaussian technique in its offline phase, further improving efficiency by reducing the preimage norm. As a direct application, the researchers specify a concrete compact GPV-IBE instantiation on commonly used power-of-two cyclotomic rings, demonstrating its practical utility. This instantiation removes the reliance on complex NTRU trapdoor generation, an attractive feature for many deployments.

Technical Deep Dive

▶ Watch: Recap of ABB10's IBE construction with trapdoors (4:00)

The advancements presented build upon sophisticated mathematical and cryptographic techniques, pushing the boundaries of what is achievable in lattice-based cryptography.

Parhat Abla's Compact IBE Scheme: The Homomorphic Equality Test

Abla's construction significantly optimizes the MPK size by focusing on the underlying homomorphic evaluation of an admissible hash function, a critical component in many IBE schemes. The talk first recaps the ABB10 IBE scheme, where the MPK consists of L+1 matrices. The Master Secret Key (MSK) is a trapdoor (TA) of a matrix A. Key generation for an identity ID involves computing an FID matrix and using the trapdoor TA with the SampleLeft algorithm to generate a Gaussian sample SKID such that FID * SKID = U. In the simulation game, without the MSK, the simulator needs to generate secret keys without TA. ABB10 observed that if FID is a homomorphic evaluation of an admissible hash function, and if the hash value for a queried identity ID equals one, then the corresponding matrices form a trapdoor for FID. Using SampleRight, the simulator can generate the secret key. For a challenge identity, the hash value equals zero, and the simulator generates the ciphertext. The problem here is that homomorphically evaluating this hash value typically requires L matrices in the MPK (e.g., B1 to BL).

To improve compactness, Abla draws inspiration from AFWW21's ring LWE-based IBE, which achieved O(1) ring matrices in the MPK. AFWW21 constructed a basic hash function that, for an input ID, outputs an ECC (Error Correcting Code) representation of ID concatenated with alpha and minus beta. By parallelly repeating this basic function T times and embedding it into a ring element, they achieved an admissible hash function with a desirable "partition property."

Abla follows the first two steps of AFWW21, mapping an ID to an ECC representation, selecting alpha's place, and minus beta, and then repeating this T times. However, instead of embedding this into a ring element, Abla embeds it into a number. The core challenge then becomes how to more compactly homomorphically evaluate this admissible hash function.

The hash function can be rewritten such that if J equals alpha_I, a specific term becomes one, and zero otherwise. The overall function then simplifies to a desired "double function." The problem reduces to compactly constructing a homomorphic equality test of J and alpha_I, where alpha_I ranges from 1 to L.

Previous approaches for homomorphic equality testing involved encoding each bit of alpha and performing a bitwise comparison with J. This method, however, requires log L matrices (one for each bit of alpha), making it "somewhat non-compact."

Abla's breakthrough solution utilizes Lagrange interpolation. A polynomial P_J(alpha) can be constructed such that P_J(alpha) = 1 if J = alpha and P_J(alpha) = 0 if J != alpha. This polynomial directly serves as an equality test. The challenge with Lagrange interpolation is that if L is large (e.g., O(n)), its homomorphic evaluation can lead to an exponential modulus, which is undesirable for IBE schemes. However, Abla observes that if L is constrained to O(log n / log log n), the homomorphic evaluation of this Lagrange polynomial P_J(alpha) results in a small polynomial modulus, enabling a compact homomorphic evaluation for this specific range. For larger ranges of alpha, Abla proposes using an L-adic representation for alpha, which further enables a more compact equality test. This combined approach leads to a homomorphic equality testing algorithm that requires only O(log n / log log n) matrices, a significant improvement over the log n matrices needed for bitwise comparison. Applying this novel equality testing directly results in an IBE scheme with an MPK containing O(log n / log log n) matrices, making it significantly more compact than prior explicit lattice-based constructions.

Huiwen Jia's Improved Preimage Sampler: A Hybrid Gadget Approach

Jia's work focuses on improving the efficiency and flexibility of the preimage sampling algorithm, a cornerstone for key extraction in lattice-based IBE. The algorithm is essentially a lattice trapdoor inversion for Ajtai's one-way function, F(x) = Ax mod Q. Inverting F is hard without a trapdoor, relating to the Closest Vector Problem (CVP) on the orthogonal lattice defined by A. With a trapdoor, a short preimage can be efficiently produced. The GPV framework (2008) provided a randomized, provably secure method, ensuring the output distribution is independent of the trapdoor.

In GPV-IBE, the short and fat matrix A acts as the MPK, and the corresponding trapdoor serves as the MSK for the KGC to extract user secret keys. Messages are protected using dual Regev encryption, requiring the inner product of the secret key x and the noise vector e to be less than Q/4 for correct decryption.

Jia details the evolution of gadget-based preimage samplers.

1. MP (Micciancio and Peikert): The trapdoor T satisfies AT = G mod Q, where G is a gadget matrix (tensor product of identity and a gadget vector g). F is inverted by reducing it to inverting F indexed by G, which is simpler. The MP sampler has an offline phase (samples a perturbation vector from a Gaussian distribution) and an online phase (samples a short Gaussian vector from a specific coset). While optimal in speed, it suffered from large sizes due to the "wide gadget."
2. CGM: Introduced an "approximate trapdoor" and replaced the MP gadget vector G with a truncated version F, reducing size by half.
3. YJW: Minimized sizes by using a square matrix as the gadget, which could be a scalar P. Their "semi-random gadget sampler" computes a small error e deterministically (v - e = PC) and samples a short z from a one-dimensional lattice coset. YJW is the most compact for "hash-and-sign" signatures, but for GPV-IBE, which requires much smaller preimage norms (much less than Q), increasing the parameter Q in YJW leads to larger errors, making it inconvenient.

Jia's new sampler proposes a hybrid approach to provide tradeoffs between security and sizes.

• Online Phase: It combines the MP gadget (expanding the gadget vector from a scalar to a vector) with the YJW semi-random technique. Given a target v, it computes a deterministic error e such that v - e = PC (like YJW). Then, it samples a short z from the coset of a w-dimensional lattice determined by G and C (like MP).
• Offline Phase: It adapts the non-spherical Gaussian technique to further reduce the preimage norm, enhancing efficiency.

A key aspect of this new sampler is its simulatability, meaning a simulator can generate a specific joint distribution without the trapdoor. This property is proven through a lemma for gadget sampling (a generalization of YJW) and a theorem for the overall sampler, ensuring indistinguishability between distributions generated with and without the trapdoor.

The comparison table shows that Jia's gadget sampling is a true combination. For the same modulus Q, the norms of the gadget preimage z and error term e are smaller than in YJW, because b is much smaller than Q and P is smaller. This is achieved at the cost of an increased gadget dimension w. Notably, the sampler is a natural generalization of YJW, becoming equivalent when w=1. This flexibility allows for better parameter selection based on specific application needs.

Demo / Proof of Concept

▶ Watch: Designing a compact homomorphic equality test (7:30)

While Parhat Abla's talk did not include a live demonstration or explicit proof-of-concept implementation, the presenter emphasized that their construction is explicitly designed. This means that, unlike some prior schemes that were implicitly defined (e.g., due to reliance on Barrington's theorem), all parameters for their compact LWE-based IBE can be concretely specified and used for implementation.

Huiwen Jia's presentation, however, explicitly detailed a proof-of-concept implementation of their improved preimage sampler and the resulting GPV-IBE scheme.

• Implementation Details: The sample P procedure (the offline phase for generating the perturbation vector) was accomplished using the GM algorithm. This algorithm samples the perturbation vector by gradually updating the center and covariance matrix at the ring level, which is a sophisticated technique for efficient Gaussian sampling on ideal lattices.
• Correctness and Modulus: To allow for the use of a slightly smaller modulus Q, the implementation incorporated an error correcting code to ensure the correctness of the decryption process, highlighting a practical consideration for optimizing parameters.
• Parameter Sets: The researchers presented two concrete parameter sets for their semi-random non-spherical Gaussian GPV-IBE, which is critical for guiding future implementations and evaluations.
• Performance Comparison: A comparison with the MSO (NTRU-based) GPV-IBE showed that while NTRU-based schemes might be more compact, Jia's instantiation offers slightly higher security. Importantly, their construction removes the NTRU assumption, thereby avoiding the complexities associated with NTRU trapdoor generation. This simplifies implementation, especially for applications with overstretched parameters, and makes it more adaptable to unstructured settings due to the absence of costly matrix inversions in key generation. The team also noted that both the online and offline phases of their sampler still have room for further implementation improvements.

Defensive Implications

▶ Watch: Lagrange interpolation for compact equality testing (9:10)

The advancements presented in these talks have profound defensive implications for organizations and individuals transitioning to a post-quantum cryptographic landscape, particularly concerning Identity-Based Encryption.

Firstly, the overarching message is clear: post-quantum IBE is becoming increasingly practical. The works demonstrate that the foundational challenges of large public key sizes and inefficient key extraction, often associated with lattice-based cryptography, are being systematically addressed through innovative research.

For cryptographic developers and security architects, Parhat Abla's work on reducing the Master Public Key (MPK) size to O(log n / log log n) matrices is a game-changer. A smaller MPK means:

• Reduced storage overhead: Less space required on servers, edge devices, or in embedded systems to store the MPK.
• Lower bandwidth consumption: Faster distribution and retrieval of the MPK, which is crucial for dynamic or large-scale IBE deployments.
• Improved efficiency for resource-constrained environments: Devices with limited memory or processing power can more easily integrate IBE.

These factors directly impact the feasibility and scalability of deploying IBE in real-world applications, such as secure messaging, IoT device authentication, or attribute-based access control systems, where the MPK might need to be widely distributed.

Huiwen Jia's contributions, focusing on an improved preimage sampler, directly impact the Key Generation Center (KGC) operations. The KGC is responsible for extracting secret keys for users based on their identities. An efficient and flexible preimage sampler means:

• Faster key extraction: The KGC can process secret key requests more quickly, reducing latency for user onboarding or key updates.
• More practical KGC deployment: The computational burden on the KGC is lessened, potentially allowing for more modest hardware requirements or handling a larger user base.
• Enhanced parameter selection flexibility: The ability to trade off security for compactness allows implementers to fine-tune schemes for specific threat models and performance requirements, moving beyond "one-size-fits-all" approaches.

The removal of the complex NTRU assumption and the adaptability to unstructured settings also simplifies the implementation process, reducing the likelihood of errors and making the technology more accessible to a broader range of developers.

Collectively, these advancements mean that deploying lattice-based IBE, which offers strong post-quantum security guarantees, is no longer solely a theoretical exercise but is moving towards robust, practical implementations. Defenders should actively monitor these developments, prioritize LWE/SIS-based cryptographic primitives in their post-quantum migration strategies, and consider the benefits of IBE (simplified key management, no certificate authority overhead) when designing future secure systems. The explicit designs and concrete parameter sets provided by these researchers are invaluable resources for those looking to build and secure systems with cutting-edge post-quantum IBE.

Key Takeaways

• Post-Quantum IBE is Advancing Rapidly: The research presented demonstrates significant progress in making Identity-Based Encryption practical and secure against quantum threats, primarily through lattice-based cryptography.
• Record-Compact Master Public Key (MPK): Parhat Abla's work achieved an unprecedentedly compact MPK for LWE-based IBE, requiring only O(log n / log log n) matrices, a substantial improvement over previous O(n) or O(log n) schemes.
• Novel Homomorphic Equality Testing: This MPK compactness was enabled by a breakthrough in LWE-based homomorphic equality testing, which leverages Lagrange interpolation and L-adic representation to efficiently compare integers.
• Improved and Flexible Preimage Sampler: Huiwen Jia introduced a new preimage sampler for ideal lattices that combines the strengths of MP and YJW gadget techniques, along with the non-spherical Gaussian technique, offering crucial tradeoffs between security and compactness.
• Practical GPV-IBE Instantiation: Jia's work includes a concrete implementation of a compact GPV-IBE on cyclotomic rings, simplifying deployment by avoiding complex NTRU trapdoor generation and providing explicit parameter sets.
• Enhanced Practicality for Defenders: These innovations lead to smaller public key sizes and more efficient key extraction procedures, directly contributing to the feasibility, scalability, and performance of deploying post-quantum IBE in real-world, resource-constrained, and large-scale environments.

About the Speaker(s)

Parhat Abla presented research on achieving a more compact Master Public Key for Identity-Based Encryption from LWE problems. No institutional affiliation was mentioned in the transcript for this presentation.

Huiwen Jia is from Guangzhou University and presented work on "Towards compact identity-based encryption on ideal lattices." This research was a joint effort with Professors Yipu Hu, Chunming Tang, and Lin Wang.