Paper 2001/009

Robust key-evolving public key encryption schemes

Wen-Guey Tzeng and Zhi-Jia Tzeng


We propose a key-evolving paradigm to deal with the key exposure problem of public key encryption schemes. The key evolving paradigm is like the one used for forward-secure digital signature schemes. Let time be divided into time periods such that at time period $j$, the decryptor holds the secret key $SK_j$, while the public key PK is fixed during its lifetime. At time period $j$, a sender encrypts a message $m$ as $\langle j, c\rangle$, which can be decrypted only with the private key $SK_j$. When the time makes a transit from period $j$ to $j+1$, the decryptor updates its private key from $SK_j$ to $SK_{j+1}$ and deletes $SK_j$ immediately. The key-evolving paradigm assures that compromise of the private key $SK_j$ does not jeopardize the message encrypted at the other time periods. \par We propose two key-evolving public key encryption schemes with $z$-resilience such that compromise of $z$ private keys does not affect confidentiality of messages encrypted in other time periods. Assuming that the DDH problem is hard, we show one scheme semantically secure against passive adversaries and the other scheme semantically secure against the adaptive chosen ciphertext attack under the random oracle.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. manuscript
public-key cryptographykey-evolvingforward scurity
Contact author(s)
tzeng @ cis nctu edu tw
2001-02-17: received
Short URL
Creative Commons Attribution


      author = {Wen-Guey Tzeng and Zhi-Jia Tzeng},
      title = {Robust key-evolving public key encryption schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2001/009},
      year = {2001},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.