International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: A new paradigm of chosen ciphertext secure public key encryption scheme

Xianhui Lu
Xuejia Lai
Dake He
Search ePrint
Search Google
Abstract: For all current adaptive chosen ciphertext(CCA) secure public key encryption schemes in standard model there are two operations in the decryption algorithm, ``validity check" and decryption. The decryption algorithm returns the corresponding plaintext if the ciphertext is valid otherwise it returns a rejection symbol $\perp$. We call this paradigm ``invalid ciphertext rejection". However the ``validity check" is not necessary for an encryption scheme. Also in this case the adversary will get the information that the ciphertext is "invalid" which he may not know before the decryption query. We propose a new paradigm for constructing CCA secure public key encryption schemes which combines ``validity check" and decryption together. The decryption algorithm will execute the same operation regardless of the ciphertext's validity. We call this new paradigm ``uniform decryption". Compared with the "invalid ciphertext rejection" paradigm, the decryption oracle of schemes in the new paradigm will reveal less information. The attacker even can not get whether the queried ciphertext is ``valid" or not. Moreover the combination of ``validity check" and the decryption will yield more efficient schemes. Using the new paradigm we construct an efficient public key encryption scheme. Our scheme is more efficient than CS98 in both computation and bandwidth. Compered with KD04 and HK07 the new scheme is more efficient in bandwidth and the same efficient in computation. The new scheme is as efficient as Kiltz07 both in computation and bandwidth. However the new scheme is CCA secure based on DDH assumption which is more flexible than GHDH assumption that Kiltz07 based on. Kurosawa and Desmedt proposed an efficient hybrid scheme named as KD04\cite{Kurosawa2004}. Although the key encapsulation part of KD04(KD04-KEM) is not CCA secure \cite{Hofheinz2006}, the whole scheme can be proved to be CCA secure. We show that if the key derivation function(KDF) of KD04-KEM is a non-malleable hash function it will be a CCA secure KEM in the new paradigm.
  title={A new paradigm of chosen ciphertext secure public key encryption scheme},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / PKE,KEM,IND-CCA2},
  note={ 13860 received 13 Jun 2007, last revised 12 Dec 2007},
  author={Xianhui Lu and Xuejia Lai and Dake He},