Public Key Cryptography

Public Key Cryptography

Speakers: Olivier Blazy, Professor, Ecole Polytechnique

Conference: RSAC 2024

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

Overview

This talk, presented by Olivier Blazy, a Professor at Ecole Polytechnique, delves into advanced concepts within public key cryptography, specifically focusing on predicate encryption and its application to identity-based revocation (IBR) and inner product encryption (IPE) schemes. The core objective of the research is to overcome significant limitations in existing cryptographic primitives, particularly the absence of fully secure non-zero inner product encryption (NIPE) and efficient identity-based revocation systems that offer strong privacy guarantees in the standard model. The work aims to construct schemes that are not only confidential but also achieve full attribute-hiding and function privacy, ensuring that sensitive information embedded in ciphertexts and secret keys remains concealed.

Blazy highlights a critical gap in the cryptographic ecosystem: while various forms of predicate encryption exist, achieving comprehensive security properties like full attribute-hiding and function privacy simultaneously, especially for non-zero conditions or revocation scenarios, has remained an open challenge. The presentation introduces novel constructions and generic transformations designed to bridge this gap. By proposing a new underlying assumption and a compiler, the research demonstrates how to build NIPE and IBR schemes that meet these stringent privacy requirements, offering a significant theoretical advancement with practical implications for secure access control and data sharing in complex systems.

The significance of this work lies in its contribution to building more robust and privacy-preserving cryptographic tools. As digital interactions become increasingly nuanced, requiring fine-grained access control and selective data disclosure, the ability to hide attributes and functions associated with cryptographic keys and ciphertexts becomes paramount. This research provides foundational elements for designing systems where, for instance, a user can decrypt a message if they meet certain criteria, without revealing those criteria to unauthorized parties, or even without knowing the exact criteria themselves, thus enhancing the overall security and privacy posture of cryptographic applications.

Background

▶ Watch: Introduction: Public Key Identity-Based Revocation (0:00)

The foundation of this research lies in predicate encryption, a powerful generalization of standard public key encryption. In traditional public key cryptography, a ciphertext can only be decrypted by the holder of a specific secret key associated with the public key used for encryption. Predicate encryption extends this by allowing decryption if and only if a predefined predicate is verified. This predicate is a mathematical relation between a secret embedded within the ciphertext (often denoted as Y) and a secret possessed by the user's decryption key (X). This allows for more flexible and expressive access control mechanisms than simple one-to-one encryption.

Two prominent forms of predicate encryption are central to this talk: inner product encryption (IPE) and identity-based multi-recipient encryption.

Inner Product Encryption (IPE):

IPE schemes enable decryption based on the inner product of two vectors, X (user's secret) and Y (ciphertext secret).

• Zero Inner Product Encryption (ZIPE): The most common variant, where decryption is possible if the inner product of X and Y is zero (i.e., X and Y are orthogonal).
• Non-Zero Inner Product Encryption (NIPE): The inverse, where decryption is possible if the inner product of X and Y is not zero. This variant presents unique challenges, as simply stating "not zero" makes it difficult to use the reconciliation techniques common in ZIPE.

Identity-Based Multi-Recipient Encryption:

This is a generalization of identity-based encryption (IBE), where instead of encrypting for a single identity, one can encrypt for a set of identities or for all identities except a specific set.

• Identity-Based Broadcast Encryption: A message can be decrypted by anyone whose identity belongs to a specified set (e.g., "all female cryptographers").
• Identity-Based Revocation (IBR): A message can be decrypted by anyone whose identity is not in a specified revocation set. This is crucial for managing access when certain users need to be excluded.

Security Properties:

Beyond basic confidentiality (indistinguishability of ciphertexts for unauthorized users), the research emphasizes two more advanced security properties:

• Attribute Hiding: This property concerns the privacy of the attributes or predicates themselves.
• Weak Attribute Hiding: An adversary should not be able to distinguish between two different predicates (Y0 or Y1) used to generate a ciphertext, as long as they are not authorized to decrypt for either.
• Full Attribute Hiding: A stronger version where the adversary cannot distinguish between predicates (Y0 or Y1) even if their key is authorized to decrypt for both. They should only know their key works, not why it works in terms of the specific predicate. This is vital for privacy, preventing an adversary from learning the criteria for encryption.
• Predicate (or Function) Privacy: This property relates to the privacy of the attributes associated with a secret key. An adversary, upon receiving a secret key, should not be able to determine which specific set of constraints or attributes (X0 or X1) that key is associated with. While in some applications users might want to know their key's capabilities, in others, especially when keys are generated for a group with varied, potentially sensitive access rights, function privacy is highly desirable.

Existing Gaps and Challenges:

The speaker identifies several critical gaps:

1. Lack of Fully Anonymous NIPE: There was no known NIPE scheme in the standard model that offered even weak anonymity, let alone full attribute-hiding or function privacy. The traditional linear encoding methods used for ZIPE rely on the inner product evaluating to a single known value (zero), allowing for reconciliation. When the inner product is merely "non-zero," this reconciliation becomes problematic, as it could be any non-zero value, making it difficult to hide X and Y.
2. Limitations of IPE to IBR Transformations: While generic transformations exist to convert IPE to identity-based multi-receiver encryption (including IBR), they often preserve only confidentiality and lose stronger privacy properties. Furthermore, existing transformations from anonymous or fully anonymous ZIPE to IBR are often theoretical, relying on the existence of fully anonymous ZIPE schemes, which were previously unknown.
3. Bounding Collusion in IBR: Previous IBR schemes often had restrictions, such as "bounding collusion," meaning they could only guarantee security against a limited number of colluding adversaries (e.g., 10 users). This significantly limits their practical applicability.
4. Inability to Re-issue Keys: In some prior IBR schemes, revoking a key for a user meant revoking all possible keys for that user, without the ability to issue a new, valid key for the same identity.

These challenges highlight the need for new cryptographic constructions and transformations that can robustly achieve strong privacy properties like full attribute-hiding and function privacy for advanced predicate encryption schemes in the standard model, without artificial restrictions.

Key Findings

▶ Watch: Four Key Security Properties for Encryption Schemes (2:00)

The research presented by Olivier Blazy introduces several significant contributions that address the identified gaps in predicate encryption, particularly concerning non-zero inner product encryption (NIPE) and identity-based revocation (IBR). The core findings revolve around novel constructions and generic compilers that achieve strong privacy guarantees in the standard model.

1. Construction of a Novel N-predicate-only-ZIPE Scheme:

The first key finding is the successful construction of a new N-predicate-only-ZIPE (Zero Inner Product Encryption) scheme operating in bilinear groups. This scheme is not just a standard ZIPE; it is specifically designed with properties amenable to later transformation into NIPE. Crucially, this scheme is proven to be fully attribute-hiding and function private under a new, reasonable assumption called the KMDDH assumption (K-Matrix Decisional Diffie-Hellman). The security is also demonstrated in the generic group model, bolstering confidence in the new assumption. This represents a foundational building block for the subsequent advancements.

1. Development of a Generic Compiler from Predicate-only-ZIPE to NIPE:

A major breakthrough is the development of a generic compiler that transforms any predicate-only-ZIPE scheme into a Non-Zero Inner Product Encryption (NIPE) scheme. This compiler is designed to preserve all the security properties of the original ZIPE, including the coveted full attribute-hiding and function privacy. This is particularly significant because, prior to this work, there was no NIPE scheme in the standard model that offered even weak anonymity, let alone these stronger forms of privacy. The resulting NIPE is the first of its kind to achieve full attribute-hiding and function privacy.

1. First Efficient Identity-Based Revocation (IBR) System with Strong Privacy:

Leveraging the new NIPE and a modified transformation from inner product encryption to identity-based multi-receiver encryption, the research also yields the first efficient, somewhat identity-based revocation (IBR) system that is fully attribute-hiding and function private. This new IBR scheme overcomes critical limitations of previous systems:

• No Bounding Collusion: Unlike prior schemes that were limited to a fixed number of colluding adversaries, this new IBR system removes such artificial restrictions, making it robust against an arbitrary number of colluding users.
• Ability to Re-issue Keys: The scheme allows for the revocation of a specific key while simultaneously enabling the issuance of a new, valid key for the same user identity, a crucial feature for practical access management.

1. Overcoming the Non-Zero Challenge:

A fundamental contribution is the innovative approach to handling the "non-zero" condition in NIPE. Instead of attempting to reconcile to a single explicit value (as in ZIPE), the scheme exploits the fact that a zero randomized is still a zero, while a non-zero randomized is still a non-zero. This method provides one bit of information during decoding, which is then used in a bit-by-bit encryption strategy, albeit with some efficiency trade-offs.

In summary, these findings provide a robust theoretical framework and practical constructions for advanced predicate encryption schemes, significantly enhancing the privacy and flexibility of cryptographic access control mechanisms. The introduction of the KMDDH assumption, the generic compiler for NIPE, and the improved IBR system collectively represent a substantial step forward in public key cryptography.

Technical Deep Dive

▶ Watch: Identifying the Gap: No Non-Zero IPE in Standard Model (4:40)

The technical core of Blazy's presentation centers on a novel construction for a N-predicate-only-ZIPE (Zero Inner Product Encryption) and subsequent generic transformations to achieve Non-Zero Inner Product Encryption (NIPE) and Identity-Based Revocation (IBR) with strong privacy guarantees.

1. The N-predicate-only-ZIPE Construction (Adaptation of Killspan V15):

The foundational scheme is an adaptation of the Killspan V15 quasi-adaptive zero-knowledge proof framework. This framework is chosen for its generic nature and ability to be instantiated with various underlying assumptions. The speaker acknowledges the initial complexity of the notation, which utilizes matrix algebra, but clarifies its interpretation:

• Master Secret Key (MSK): Consists of several matrices of discrete logarithms. For example, if A is an element in bold without square brackets, it represents a matrix of discrete logarithms. These are the fundamental secrets from which all other keys are derived.
• Public Key (PK): Derived from the MSK. When elements are enclosed in square brackets (e.g., [A]), it signifies the group element associated with the discrete logarithm matrix A. Thus, the public key comprises matrices of group elements. Products of these elements (e.g., a group element raised to a scalar) remain group elements, but the underlying discrete logarithms are hidden from an adversary.
• Encryption Process:
• Random elements (discrete logarithms) are chosen.
• The ciphertext is generated using these random elements, incorporating the secret vector Y that defines the predicate.
• An "extra term" is included to prevent malleability, ensuring that the ciphertext cannot be easily altered without detection.
• The final ciphertext is a set of several group elements.
• Key Generation (KeyGen):
• Similar to encryption but operates "on the other side," using the user's secret vector X.
• The secret key is generated in a different group (e.g., group two instead of group one in a bilinear pairing setting).
• The structure of the key depends on whether it's for a J0 or J1 condition, though the general process remains consistent.
• Decryption (Test):
• Decryption involves performing pairings between elements from the ciphertext and elements from the secret key.
• If the pairing result matches a predefined condition (e.g., e(C_i, SK_j) equals e(G, G)^0 for ZIPE), the message is decrypted (or a bit 1 is returned, signifying a match). If it doesn't match, it signifies a non-match (bit 0).

Scalability and Assumptions:

The scheme's security can be scaled by varying a parameter K:

• If K=1, the matrices collapse to standard elements, resembling a Diffie-Hellman or symmetric external Diffie-Hellman scheme (like ElGamal).
• If K=2, it relates to the Decisional Linear Problem on symmetric curves.
• Increasing K enhances security but increases the size of the elements. The speaker notes that against a quantum adversary, increasing K beyond a certain point might not be beneficial, but it provides robustness against classical attacks or issues with specific curve choices.

Security Proofs:

The constructed ZIPE scheme is proven secure for all desired properties (confidentiality, full attribute-hiding, function privacy) under the KMDDH (K-Matrix Decisional Diffie-Hellman) assumption. This is a new assumption, and its reasonableness is supported by a proof of security in the generic group model. A "linear loss" in the adversary's query capability is noted, implying that the reduction might not be perfectly tight, but tricks exist to improve tightness at the cost of efficiency.

2. The Compiler: Predicate-only-ZIPE to NIPE:

The transition from ZIPE to NIPE is achieved through a generic compiler. The beauty of this compiler is its simplicity in setup and key generation:

• Setup and KeyGen: The setup and key generation procedures of the underlying predicate-only-ZIPE scheme are used without modification.
• Encryption: This is where the transformation introduces a key change and a trade-off in efficiency.
• For each bit of the message to be encrypted, a new value is generated. This means that instead of a single vector for the secret Y, the ciphertext effectively becomes a matrix of elements.
• To achieve the "non-zero" property, the computed vector is XORed with a vector of all ones (111...). This ensures that if the original inner product was zero, it becomes non-zero after the XOR, and vice-versa, effectively reversing the predicate.

Efficiency vs. Security Trade-offs:

• Efficiency: The NIPE resulting from this compiler is less efficient than previous NIPE attempts because its efficiency now directly depends on the length of the encrypted message. This "linear loss in message length" means that longer messages result in significantly larger ciphertexts and encryption times.
• Security: Despite the efficiency hit, the security gains are substantial. The resulting NIPE is fully attribute-hiding and function private, a significant improvement over previous schemes that were only weakly attribute-hiding or had restrictions on adversary queries. The compiler preserves these strong security properties, demonstrating that such a transformation is indeed possible.

3. Transformation: NIPE to IBR (Identity-Based Revocation):

The final step involves transforming the NIPE into an IBR system. This also leverages a classical transformation framework but applies it to the newly secured NIPE.

• Identity Representation: User identities are converted into a vector, typically by using exponentiation of the identity up to a certain value (e.g., (ID^0, ID^1, ..., ID^k)).
• Encryption for Revocation:
• A polynomial interpolation technique is used to embed the identities of the revoked users into the ciphertext.
• The secret coefficients s0, ..., sk for this interpolation are chosen.
• Decryption: Remarkably, the decryption process for IBR works "magically" similar to the underlying IPE scheme, using pairings with the master public key, secret key, and ciphertext. The way the polynomial is embedded means that no explicit "reversing trick" (like the XOR in NIPE) is needed at the decryption stage.

Efficiency and Security Gains for IBR:

This transformation yields an IBR scheme with significant improvements over previous state-of-the-art:

• No Bounding Collusion: A major advantage is the removal of the "bounding collusion" restriction. The scheme remains secure against an arbitrary number of colluding adversaries.
• Key Re-issuance: It allows for a key to be revoked and a new, valid key to be issued for the same user identity, which was not possible in many prior schemes.
• Full Attribute-Hiding and Function Privacy: These strong privacy properties are preserved, making the IBR system highly suitable for sensitive applications.
• Efficiency Comparison:
• Master Public Key: The master public key is larger than in previous IBR schemes, being linear in both the vector length and the encrypted message length.
• Secret Key: A significant gain here, as the secret key size is reduced from quadratic in the message length to just linear.
• Ciphertext: The ciphertext size is slightly larger but of the same order of magnitude as previous schemes.

Overall, the technical deep dive reveals a sophisticated approach that combines a novel ZIPE construction with generic, property-preserving compilers. While some efficiency trade-offs are noted, particularly for NIPE, the achievement of full attribute-hiding and function privacy in the standard model for these complex cryptographic primitives represents a substantial advancement.

Demo / Proof of Concept

▶ Watch: Our Multi-Step Solution Approach and Compiler (6:20)

The talk focused on the theoretical constructions, security proofs, and efficiency analysis of the proposed cryptographic schemes and compilers. No live demonstration or specific proof of concept implementation was presented during Olivier Blazy's session. The discussion remained at a conceptual and mathematical level, detailing the design principles and security properties rather than showcasing a working prototype.

Defensive Implications

▶ Watch: Overview of Our Proposed Scheme Adaptation (7:50)

The advancements presented in this talk, while theoretical in nature, carry significant implications for the design and implementation of secure systems, particularly in areas requiring fine-grained access control, data privacy, and identity management. Defenders and system architects should consider the following:

1. Enhanced Privacy for Access Control: The achievement of full attribute-hiding and function privacy in identity-based revocation (IBR) and non-zero inner product encryption (NIPE) schemes offers a powerful tool for privacy-preserving access control. In scenarios where access criteria (attributes) or the specific capabilities encoded in a user's key are sensitive, these schemes ensure that even authorized users or external observers cannot infer this information. For example, in a medical research setting, a researcher might be granted access to patient data based on specific, complex criteria (e.g., "patients with condition X, aged between 40-50, not on medication Y"). With fully attribute-hiding encryption, the data access system can verify these criteria without revealing them to the researcher or any other party, protecting sensitive policy details.

1. Robust Revocation Mechanisms: The new IBR scheme, free from "bounding collusion" limitations and supporting key re-issuance, provides a more robust and practical solution for managing user access. Defenders can implement systems where compromise of a subset of keys does not threaten the entire system's integrity beyond the compromised keys themselves. The ability to revoke a specific key and issue a new one for the same user identity is crucial for dynamic environments where user roles or security statuses change frequently. This is particularly relevant for IoT ecosystems, enterprise access management, or supply chain security, where rapid and secure user management is essential.

1. Foundation for Future Secure Systems: While the schemes are currently "academic efficient" rather than "practically efficient" due to the linear loss in message length for NIPE, they lay a strong theoretical foundation. Defenders should be aware that these primitives represent the cutting edge of what is cryptographically possible in terms of privacy guarantees. As research progresses and more efficient instantiations or optimizations emerge, these schemes could become practical building blocks for next-generation security protocols. This means staying informed about such developments will be key.

1. Trade-offs in Implementation: The presented work highlights inherent trade-offs between security properties and efficiency. For example, achieving full attribute-hiding and function privacy in NIPE comes at the cost of efficiency, with ciphertext size scaling linearly with message length. Defenders need to carefully evaluate their specific security requirements against performance constraints. For applications handling very short messages or where privacy is paramount, these schemes might be acceptable. For high-throughput or large-data applications, current versions might be too resource-intensive, necessitating a search for alternative solutions or a willingness to accept weaker privacy guarantees.

1. Adoption of New Assumptions: The security of the new ZIPE construction relies on the novel KMDDH assumption. While proven reasonable in the generic group model, new assumptions always warrant careful scrutiny and community validation over time. Defenders adopting systems based on such new primitives should understand the underlying assumptions and monitor ongoing cryptographic research for any potential breaks or challenges to these assumptions.

In essence, this research empowers defenders by expanding the cryptographic toolkit with primitives that offer superior privacy and flexibility in complex access control scenarios. It encourages a shift towards systems that not only control who can access data but also how and why, without revealing the underlying policy logic, thereby fostering more secure and privacy-respecting digital environments.

Key Takeaways

• First Fully Attribute-Hiding and Function Private NIPE: The research successfully constructs the first Non-Zero Inner Product Encryption (NIPE) scheme in the standard model that achieves both full attribute-hiding (hiding the predicate in the ciphertext) and function privacy (hiding the predicate in the secret key).
• Novel Identity-Based Revocation (IBR) System: A new, efficient IBR system is presented that offers strong privacy guarantees (fully attribute-hiding and function private) without the previous limitations of "bounding collusion" and enables the ability to revoke a key and re-issue a new one for the same identity.
• Generic Compiler for NIPE: A significant contribution is a generic compiler that transforms any predicate-only Zero Inner Product Encryption (ZIPE) scheme into a NIPE, crucially preserving all strong security properties of the original ZIPE.
• New KMDDH Assumption: The underlying ZIPE construction is proven secure under a new cryptographic assumption, the KMDDH (K-Matrix Decisional Diffie-Hellman) assumption, which is shown to be reasonable in the generic group model.
• Efficiency Trade-offs: While providing unprecedented security, the transformation to NIPE introduces a "linear loss in message length," making it "academic efficient" but "moderately efficient" for practical applications, highlighting a trade-off between strong privacy and performance.
• Exploiting Randomizability: The core technique for handling non-zero conditions involves exploiting the property that a randomized zero remains zero, while a randomized non-zero remains non-zero, allowing for one bit of information at decoding for each message bit.

About the Speaker(s)

Olivier Blazy is a Professor at Ecole Polytechnique. His research focuses on public key cryptography, particularly predicate encryption, inner product encryption, and identity-based cryptographic schemes. This work was presented at RSAC 2024 and represents a joint effort with Sayantan Mukherjee, who is affiliated with IIT Jammu.