Provably Secure Timed-Release Public Key Encryption

Jung Hee Cheon, Nicholas Hopper, Yongdae Kim, Ivan OsipkovACM Trans. Inf. Syst. Secur 2008 · DOI

TL;DR

This paper introduces and formalizes the concept of "timed-release public key encryption" (TR-PKE), a cryptographic primitive that allows messages to be encrypted such that they can only be decrypted after a specified future time. The authors provide provably secure constructions and demonstrate its equivalence to identity-based encryption (IBE) and key-insulated encryption, offering practical solutions for applications requiring delayed access to information.

What Problem Does This Paper Address?

Imagine needing to send a secret message that should only be accessible at a specific point in the future. This is the core problem addressed by "timed-release cryptography." Think of applications like preventing auctioneers from opening bids early, ensuring fair exchange of digital assets, or securely releasing classified information at a predetermined time. Previous solutions fell into two categories: "time-lock puzzles" that require significant, non-parallelizable computation from the recipient, and "trusted decryption agents" who hold the key to unlock the message at the designated time. Both approaches have drawbacks: time-lock puzzles are computationally burdensome, and trusted agents introduce a single point of failure and require trust. This paper aims to formalize the security of timed-release encryption and provide provably secure, efficient constructions that address these limitations.

Methods

The authors formalize the security notions for timed-release public key encryption (TR-PKE) and authenticated timed-release public key encryption (TR-PKAE). They establish that secure TR-PKE is equivalent to identity-based encryption (IBE) and strongly key-insulated encryption (SKIE).

Key contributions include:

  • Formalization of TR-PKE and TR-PKAE: Defining rigorous security models (IND-CCA2, IND-RTR-CCA2, TUF-CTXT, RUF-CTXT) to capture the security properties required for timed-release encryption, including confidentiality and unforgeability.
  • Generic Construction: Presenting a generic TR-PKAE scheme that combines existing primitives like PKE, IBE, and digital signatures. This construction highlights the relationship between TR-PKE and IBE.
  • Efficient Constructions: Developing more efficient TR-PKE and TR-PKAE schemes based on bilinear pairings. These constructions aim to be as efficient as existing IBE schemes and are proven secure in either the random oracle model or the standard model.
  • Equivalence Proofs: Demonstrating the equivalence between TR-PKE and SKIE, providing a deeper understanding of the underlying cryptographic principles.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • TR-PKE is fundamentally linked to IBE: The paper shows that the concept of timed-release encryption, when formalized with a trusted third party for decryption, is equivalent to identity-based encryption. This explains why many existing timed-release schemes leverage IBE.
  • The role of the "timed-release agent" (TiPuS): This agent acts as a central authority that publishes public parameters and generates "tokens" necessary for decryption after a specified time. The security of the system relies on the agent's ability to securely manage these tokens.
  • Balancing security and efficiency: The authors explore different constructions, ranging from generic ones that are provably secure but potentially less efficient, to more specialized schemes that achieve better performance by leveraging specific cryptographic assumptions like bilinear pairings.
  • Standard Model vs. Random Oracle Model: The paper highlights the importance of constructing secure schemes in the standard model (without relying on random oracles), which is generally considered a stronger security guarantee.

Key Results

The paper presents several provably secure constructions for TR-PKE and TR-PKAE.

  • Generic TR-PKAE: A construction is provided that is secure against IND-KC-CCA2, IND-RTR-KC-CCA2, TUF-CTXT, and RUF-CTXT, provided underlying primitives (PKE, IBE, one-time signatures) are secure.
  • Efficient TR-PKAEbm: A scheme is proposed that is nearly as efficient as the Boneh-Franklin IBE scheme and is provably secure and authenticated in the random oracle model.
  • Efficient TR-PKEstd: A scheme is presented that is provably secure in the standard model, offering a strong security guarantee without relying on random oracles. This scheme is shown to be secure against IND-KEM-CCA2 and IND-KEM-RTR-CCA2, with security against IND-KEM-RTR-CCA2 relying on the hardness of the decisional TDHP.

Limitations and Future Work

  • Trusted Agent Dependency: The proposed schemes, particularly those relying on a timed-release agent (TiPuS), still depend on the trustworthiness and availability of this agent. While the paper explores distributed threshold protocols to mitigate this, the core reliance remains.
  • Efficiency Trade-offs: While the paper presents efficient constructions, there are still trade-offs between security guarantees (e.g., standard model vs. random oracle model) and performance. Further research could focus on optimizing these schemes.
  • Practical Implementations: The paper lays the theoretical groundwork. Future work could involve practical implementations and performance evaluations of these schemes in real-world scenarios.
  • Alternative Models: The paper discusses alternative models for TR-PKE, such as those that bind a receiver's public key to a specific server. Further exploration of these models and their implications for security and usability could be beneficial.

Summary updated

BibTeX
@article{cheon2008provably,
  author = {Jung Hee Cheon and Nicholas Hopper and Yongdae Kim and Ivan Osipkov},
  title = {{Provably Secure Timed-Release Public Key Encryption}},
  journal = {ACM Trans. Inf. Syst. Secur.},
  year = {2008},
  doi = {10.1145/1330332.1330336},
}
Figure