Public key encryption without random oracle made truly practical

In this paper, we report our success in identifying an efficient public key encryption scheme whose formal security proof does not require a random oracle. Specifically, we focus our attention on a universal hash based public key encryption scheme proposed by Zheng and Seberry at Crypto’92. Although Zheng and Seberry’s encryption scheme is very simple and efficient, its reductionist security proof has not been provided. We show how to tweak the Zheng–Seberry scheme so that the resultant scheme not only preserves the efficiency of the original scheme but also admits provable security against adaptive chosen ciphertext attack without random oracle. For the security proof, our first attempt is based on a strong assumption called the oracle Diffie–Hellman+ assumption. This is followed by a more challenging proof that employs a weaker assumption called the adaptive decisional Diffie–Hellman assumption, which is in alignment with adaptively secure assumptions advocated by Pandey, Pass and Vaikuntanathan.

Figure optionsDownload as PowerPoint slideHighlights
► We introduce the adaptive decisional Diffie–Hellman assumption (DDH).
► The Zheng–Seberry encryption is secure under the oracle DDH+ assumption.
► The modified Zheng–Seberry encryption is secure under the adaptive DDH assumption.