Research on Non-interactive Construction based on Fuzzy Conditional Proxy Re-encryption

Chunpeng Ge, Jiandong Wang, Liming FangInternational Journal of Security and Its Applications 2015 · DOI

Abstract

In a conditional proxy re-encryption (C-PRE) scheme, a semi-trusted proxy can transform Alice's ciphertext into Bob's ciphertext without learning the underlying plaintext, provided the ciphertext satisfies a specific condition. To enable more fine-grained delegation, the concept of fuzzy conditional proxy re-encryption (FC-PRE) was introduced, where conditions are treated as sets of descriptive keywords. In this model, a proxy can perform re-encryption if and only if the keyword set of the ciphertext and the keyword set of the re-encryption key are sufficiently close, as measured by a "set overlap" distance metric. This paper addresses two significant gaps in existing FC-PRE research: the requirement for interactivity during key generation and the reliance on the random oracle model for security proofs. We present the first non-interactive FC-PRE scheme and demonstrate its security in the standard model.

Introduction

Proxy Re-encryption (PRE) is a cryptographic primitive that allows a proxy to transform a ciphertext intended for one user (the delegator) into a ciphertext for another user (the delegatee) without ever accessing the original message. Conditional Proxy Re-encryption (C-PRE) adds a layer of control, allowing the delegator to specify conditions under which the transformation can occur.

While C-PRE is powerful, its requirement for exact condition matching is often too restrictive for dynamic environments. Fuzzy Conditional Proxy Re-encryption (FC-PRE) relaxes this by allowing re-encryption based on keyword overlap. However, prior constructions of FC-PRE were hindered by two issues: they required the delegator and delegatee to interact to generate re-encryption keys, and their security was only proven using the "random oracle" heuristic—a mathematical simplification that may not hold in real-world implementations. This research provides a robust, non-interactive solution proven secure under standard mathematical assumptions.

The Mechanism of Fuzzy Delegation

The core innovation of FC-PRE is the use of a "set overlap" metric. Instead of requiring an exact match of tags, the system defines a threshold $d$. If the set of keywords $W$ attached to a ciphertext and the set of keywords $W'$ associated with a re-encryption key share at least $d$ elements ($|W \cap W'| \geq d$), the proxy can successfully transform the data.

To achieve this "fuzziness" non-interactively, the authors utilize several advanced cryptographic building blocks:

  • Bilinear Pairings: The scheme operates within groups where a bilinear map ($e: G \times G \to G_T$) allows for complex operations on encrypted values, facilitating the transformation process without decryption.
  • Lagrange Interpolation: The threshold logic is managed through polynomial secret sharing. Keywords are treated as points on a polynomial; if the proxy possesses enough overlapping keywords (points), it can reconstruct the secret necessary to complete the re-encryption.
  • Non-interactive Key Generation: Unlike previous models, the RKeyGen algorithm allows the delegator to create a re-encryption key using only their secret key and the delegatee’s public key. This is essential for asynchronous systems where the recipient may not be online at the time of delegation.

Technical Framework and Algorithms

The paper defines a comprehensive system consisting of eight core algorithms:

  1. GlobalSetup: Establishes the public parameters and the threshold $d$.
  2. KeyGen: Generates public and private key pairs for users.
  3. RKeyGen: Produces the re-encryption key for a specific keyword set non-interactively.
  4. Enc: Encrypts the original plaintext with a set of condition keywords.
  5. REnc: The proxy-led process that transforms the ciphertext if the overlap condition is met.
  6. Dec1: Allows the delegatee to decrypt a re-encrypted ciphertext.
  7. Dec2: Allows the original delegator to decrypt their own original ciphertext.

Security in the Standard Model

A primary contribution of this work is the rigorous security proof. Most existing schemes rely on the Random Oracle Model (ROM), which assumes the existence of a perfectly random function. This paper moves beyond this heuristic, proving the scheme's security in the Standard Model.

The authors demonstrate that the scheme achieves IND-CCA (Indistinguishability under Chosen-Ciphertext Attack) security. This proof is based on the hardness of the 3-weak decisional bilinear Diffie-Hellman inversion (3-wDBDHI) problem. By grounding the security in a well-studied mathematical hard problem without the use of random oracles, the authors provide a more reliable guarantee for real-world cryptographic applications.

Conclusion and Future Directions

This research successfully fills a gap in delegated cryptography by providing a non-interactive, standard-model FC-PRE scheme. This advancement makes fuzzy delegation viable for practical applications like secure cloud storage and encrypted email forwarding, where users cannot be expected to interact for every access grant.

Despite these gains, the authors identify several areas for future work:

  • Anonymity: Currently, the keywords used as conditions are public. Future iterations could explore "anonymous" FC-PRE to hide metadata.
  • Efficiency: The reliance on bilinear pairings and Lagrange coefficients introduces computational overhead. Developing pairing-free or more computationally efficient versions remains a challenge.
  • Multi-hop Delegation: The current scheme is "single-hop," meaning a transformed ciphertext cannot be transformed a second time for a third party. Extending this to multi-hop scenarios would further increase the flexibility of the system.

Summary updated

Abstract

In a conditional proxy re-encryption (C-PRE) scheme, a semi-trusted proxy can transform Alice's ciphertext into Bob's ciphertext without learning the underlying plaintext, if the ciphertext satisfies a certain condition. To achieve more fine-grained delegation on conditions, Fang, Wang and Ge introduced the notion of fuzzy conditional proxy re-encryption (FC-PRE), whereby the conditions is viewed a set of descriptive keywords. The proxy with a re-encryption key for a condition word set can convert a ciphertext encrypted with a condition word set , if and only if and are close to each other as measured by the "set overlap" distance metric. Nonetheless, they left an open problem on how to construct a non-interactive FC-PRE scheme. Furthermore, their scheme is only proved secure in the random oracle model. In this paper, we answer the above problems affirmatively by presenting a non-interactive fuzzy conditional proxy reencryption scheme. Moreover, our scheme is proved secure without random oracles.
BibTeX
@article{ge2015research,
  author = {Chunpeng Ge and Jiandong Wang and Liming Fang},
  title = {{Research on Non-interactive Construction based on Fuzzy Conditional Proxy Re-encryption}},
  journal = {International Journal of Security and Its Applications},
  year = {2015},
  doi = {10.14257/ijsia.2015.9.12.36},
}
Figure