Abstract
Modern information technology relies heavily on public-key encryption for applications ranging from e-commerce to mobile databases. This paper presents two secure receiptor-oriented encryption (ROE) systems where decryption keys evolve across different time periods. This temporal evolution provides "backward-and-future security," ensuring that the compromise of a key in one time period does not jeopardize data from past or future periods. Built upon bilinear pairings over elliptic curves, these schemes offer semantic security and are analyzed through a heuristic security framework.
Introduction
In traditional public-key cryptography, the compromise of a private key typically results in a total breach of all communications associated with that identity. In dynamic environments such as mobile databases, where devices may be lost or temporarily compromised, this "all-or-nothing" security model is insufficient. There is a pressing need for systems that can contain the impact of a security breach within a specific temporal window.
This paper introduces Receiptor-Oriented Encryption (ROE), a framework designed to provide temporal compartmentalization. By utilizing bilinear pairings on elliptic curves, the proposed schemes ensure that even if an attacker gains access to a decryption key for a specific time interval, they remain unable to decrypt messages sent before that interval or predict keys for future intervals.
The ROE Framework and Methodology
The authors propose two non-identity-based ROE schemes. Unlike some previous elliptic curve implementations that utilize only the x-coordinate of a point for efficiency, these schemes utilize the whole point and bilinear pairings (such as modified Weil or Tate pairings) on supersingular curves. This approach simplifies the construction of security proofs and enhances the robustness of the system.
System Components
The ROE model is defined by three primary procedures:
- Key Generation: This phase produces long-term public and private keys for both the sender and the receiver. Crucially, it also generates a sequence of "time-stage" keys ($pk_{t_i}, sk_{t_i}$) for the receiver, corresponding to specific time intervals.
- Encryption: A probabilistic algorithm where the sender incorporates their own long-term keys, the receiver's long-term public key, and the receiver’s public key for the current time stage to produce a ciphertext.
- Decryption: A deterministic algorithm where the receiver utilizes their full suite of keys—both long-term and the specific time-stage private key—to recover the original plaintext.
The security of these operations rests on two foundational "hard problems" in cryptography: the Bilinear Diffie-Hellman (BDH) assumption and the Inversion-with-Fixed-Element (IWP) assumption.
Key Innovations: Backward-and-Future Security
The core contribution of this research is the formalization and implementation of backward-and-future security. While semantic security protects against the recovery of plaintext from ciphertext, backward-and-future security addresses the relationship between keys across time.
In the proposed ROE schemes, time-stage keys are chosen randomly and uniformly. Because there is no mathematical dependency between $sk_{t_i}$ and $sk_{t_{i+1}}$, an attacker who compromises the key for period $i$ gains no advantage in deriving the keys for period $i-1$ (backward security) or period $i+1$ (future security). This creates a "blast shield" effect, limiting the damage of a device theft or localized hack to the specific duration the compromised key was active.
Performance and Security Analysis
The paper evaluates the schemes based on three critical criteria:
- Soundness: The algorithms are proven to correctly decrypt any validly encrypted ciphertext.
- Semantic Security: The authors provide a heuristic analysis demonstrating that an attacker cannot distinguish between a ciphertext and a random element in polynomial time.
- Efficiency: The "expansion factor"—the ratio of ciphertext size to plaintext size—is maintained between 1 and 2. This makes the schemes suitable for bandwidth-constrained environments like mobile networks.
Scheme 1 is particularly efficient, requiring only one pairing evaluation and one modular exponentiation for both the encryption and decryption processes. This low computational overhead is vital for practical implementation in resource-limited mobile devices.
Conclusion and Future Work
The proposed ROE schemes offer a significant advancement in protecting data within dynamic, time-sensitive environments. By decoupling long-term identity from temporal decryption capabilities, the system provides a robust defense against key compromise.
However, the authors note that the current analysis focuses on security against chosen-plaintext attacks (CPA). Future research should focus on extending these schemes to achieve security against Chosen-Ciphertext Attacks (CCA), which represents a more rigorous security standard. Additionally, while the mathematical framework is sound, the practical infrastructure for synchronizing and distributing time-stage keys across a network remains an area for further development.
Summary updated