Paper 2007/232
A new paradigm of chosen ciphertext secure public key encryption scheme
Xianhui Lu, Xuejia Lai, and Dake He
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 . 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.
Note: a one-way hash function , is not enough, we need a non-malleable hash function
