Cramer-Shoup Satis¬es a Stronger Plaintext Awareness 125

References

[BDPR98] Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations Among No-

tions of Security for Public-Key Encryption Schemes. In: Krawczyk, H. (ed.)

CRYPTO 1998. LNCS, vol. 1462, pp. 26“45. Springer, Heidelberg (1998)

[BP04] Bellare, M., Palacio, A.: Towards plaintext-aware public-key encryption

without random oracles. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS,

vol. 3329, pp. 48“62. Springer, Heidelberg (2004)

[BR94] Bellare, M., Rogaway, P.: Optimal Asymmetric Encryption. In: De Santis, A.

(ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92“111. Springer, Heidelberg

(1995)

[BD08] Birkett, J., Dent, A.W.: Relations Among Notions of Plaintext Awareness.

In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 47“64. Springer, Hei-

delberg (2008)

[B01] Boneh, D.: Simpli¬ed OAEP for the RSA and Rabin Functions. In: Kilian,

J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 275“291. Springer, Heidelberg

(2001)

[CS98] Cramer, R., Shoup, V.: A Practical Public Key Cryptosystem Provably Se-

cure Against Adaptive Chosen Ciphertext Attack. In: Krawczyk, H. (ed.)

CRYPTO 1998. LNCS, vol. 1462, pp. 13“25. Springer, Heidelberg (1998)

[CS01] Cramer, R., Shoup, V.: Design and Analysis of Practical Public-Key En-

cryption Schemes (2001)

[D91] Damg˚ ard, I.: Towards practical public key systems secure against chosen

ciphertext attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576,

pp. 445“456. Springer, Heidelberg (1992)

[D06] Dent, A.W.: Cramer-Shoup is Plaintext-Aware in the Standard Model. In:

EUROCRYPT 2006 (2006)

[F06] Fujisaki, E.: Plaintext Simulatability. IEICE Trans. Fundamentals, E89-A,

pp.55-65. Preliminary version (2006), http://eprint.iacr.org/2004/218.pdf

[FO99] Fujisaki, E., Okamoto, T.: How to Enhance the Security of Public-Key En-

cryption at Minimum Cost. In: Imai, H., Zheng, Y. (eds.) PKC 1999. LNCS,

vol. 1560, pp. 53“68. Springer, Heidelberg (1999)

[FOPS01] Fujisaki, E., Okamoto, T., Pointcheval, D., Stern, J.: RSA-OAEP Is Secure

under the RSA Assumption. In: CRYPTO 2001, pp. 260“274; J. Cryptology

17(2), pp.81-104 (2004)

[HLM03] Herzog, J., Liskov, M., Micali, S.: Plaintext Awareness via Key Registration.

In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 548“564. Springer,

Heidelberg (2003)

[M01] Manger, J.: A Chosen Ciphertext Attack on RSA Optimal Asymmetric En-

cryption Padding (OAEP) as Standardized in PKCS #1 v2. In: Kilian, J. (ed.)

CRYPTO 2001. LNCS, vol. 2139, pp. 230“238. Springer, Heidelberg (2001)

[S00] Shoup, V.: Using Hash Functions as a Hedge against Chosen Ciphertext

Attack. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 275“

288. Springer, Heidelberg (2000)

[S01] Shoup, V.: OAEP Reconsidered. In: CRYPTO 2001, pp.239“259 (2001); J.

Cryptology, 15(4), 223“249 (2002)

[TO06] Teranishi, I., Ogata, W.: Relationship between Standard Model Plaintext

Awareness and Message Hiding. In: ASIACRYPT 2006. IEICE Transactions

2008 91-A(1), pp.244-261

[TO08] Teranishi, I., Ogata, W.: Relationship between Two Approaches for De¬ning

the Standard Model PA-ness. In: ACISP 2008 (2008)

General Certi¬cateless Encryption

and Timed-Release Encryption

Sherman S.M. Chow1, , Volker Roth2 , and Eleanor G. Rie¬el2

1

Department of Computer Science

Courant Institute of Mathematical Sciences

New York University, NY 10012, USA

schow@cs.nyu.edu

2

FX Palo Alto Laboratory

3400 Hillview Avenue

Palo Alto, CA 94304, USA

{vroth,rieffel}@fxpal.com

Abstract. While recent timed-release encryption (TRE) schemes are

implicitly supported by a certi¬cateless encryption (CLE) mechanism,

the security models of CLE and TRE di¬er and there is no generic

transformation from a CLE to a TRE. This paper gives a generalized

model for CLE that ful¬lls the requirements of TRE. This model is se-

cure against adversaries with adaptive trapdoor extraction capabilities,

decryption capabilities for arbitrary public keys, and partial decryption

capabilities. It also supports hierarchical identi¬ers. We propose a con-

crete scheme under our generalized model and prove it secure without

random oracles, yielding the ¬rst strongly-secure security-mediated CLE

and the ¬rst TRE in the standard model. In addition, our technique of

partial decryption is di¬erent from the previous approach.

Keywords: Security-mediated certi¬cateless encryption, timed-release

encryption, standard model.

1 Introduction

In identity-based encryption (IBE) [29], encryption is done with respect to any

arbitrary string viewed an identi¬er (ID). Since the birth of practical IBE con-

structions, this idea has been used to achieve other security goals, such as cer-

ti¬cateless encryption (CLE) [1,14,16] and timed-release encryption (TRE) [3].

CLE is intermediate between IBE and traditional public key encryption

(PKE). Traditional PKE requires a certi¬cation infrastructure but allows users

to create their own public/private key pairs so that their private keys are truly

private. Conversely, IBE avoids the need for certi¬cates at the expense of adding

a trusted key generation center (KGC) that generates the private keys, which

means the KGC has the capability to decrypt all messages. CLE combines the

This research is done while the ¬rst author was a research intern of FXPAL. We

thank Wolfgang Polak for helpful discussions and the reviewers for their feedback.

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 126“143, 2008.

c Springer-Verlag Berlin Heidelberg 2008

General Certi¬cateless Encryption and Timed-Release Encryption 127

advantages of both: no certi¬cates are needed and messages can only be de-

crypted by the recipient. Generally, CLE is constructed by combining IBE and

PKE. The existence of the PKE component means that the KGC cannot de-

crypt messages. Instantaneous revocation is di¬cult for typical CLE schemes.

Security-mediated certi¬cateless encryption (SMCLE) addresses this issue.

In TRE, a message is encrypted under a public key and a time; both the

private key and a time-dependent trapdoor are needed for decryption. A time-

server is trusted to keep a trapdoor con¬dential until an appointed time. Apart

from delayed release of information, TRE supports many other applications due

to its small trapdoor size and its commitment provision (see [11,18]).

1.1 The Di¬culty of Converting between CLE and TRE

A practical TRE requires system parameters to be small relative to the number of

supported time periods. IBE supports an e¬cient time-based unlock mechanism

by treating the identities as time periods [4,26]. This approach supports only

universal disclosure of encrypted documents since one trapdoor can decrypt all

ciphertexts for a speci¬c time; the inherent key-escrow property of IBE prohibits

the encryption for a designated receiver.

Since CLE is an “escrow-free version” of IBE, and both TRE and CLE are a

kind of double-encryption, it is natural to think CLE is what we are looking for to

realize a TRE. While most recent TRE schemes can be viewed as containing an

implicit CLE mechanism, a generic transformation from CLE to TRE is unlikely

to be provable secure [7]. Di¬culty in reducing the con¬dentiality of TRE to that

of CLE arises when the adversary is a “curious” time-server. In CLE, an identity

is associated with only one public key, so a curious KGC is not allowed to replace

the public key associated with an identi¬er arbitrarily (otherwise, decryption is

trivial since it holds both parts of secrets). On the other hand, in TRE a time

identi¬er is never bound to any public key, so the public key associated with a

time identi¬er can be replaced. There is no way to simulate this implicit public

key replacement when CLE is viewed as a black box.

There is another subtle di¬erence in modeling of curious users. In a secure

multi-user system, the security of a user is preserved even if other users are

compromised. In CLE, the user secret key together with the trapdoor given by

the KGC give the full private key. With the assumption that the user secret key

will be securely deleted after the combination, most CLE models assume the

adversary can get only trapdoors and full private keys. For most CLE schemes

under this model (e.g. [17]), the user secret key cannot be recovered from the

trapdoor and the full private key. Moreover, some CLE formulations [2,24,30] do

not have user secret keys at all. In TRE, user secret keys are held by each user,

which makes it impossible to reduce the security of TRE to that of CLE.

1.2 Our Contributions

Our generalized model for CLE overcomes the aforementioned di¬culties and

has su¬cient power to ful¬ll the requirements of TRE. Our model is secure

128 S.S.M. Chow, V. Roth, and E.G. Rie¬el