Efficient construction of completely non-malleable CCA secure public key encryption

Shi Feng Sun, Dawu Gu, Joseph K. Liu, Udaya Parampalli, Tsz Hon Yuen

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


    Non-malleability is an important and intensively studied security notion for many cryptographic primitives. In the context of public key encryption, this notion means it is infeasible for an adversary to transform an encryption of some message m into one of a related message m' under the given public key. Although it has provided a strong security property for many applications, it still does not suffice for some scenarios like the system where the users could issue keys on-the-y. In such settings, the adversary may have the power to transform the given public key and the ciphertext. To withstand such attacks, Fischlin introduced a stronger notion, known as complete non-malleability, which requires that the non-malleability property be preserved even for the adversaries attempting to produce a ciphertext of some related message under the transformed public key. To date, many schemes satisfying this stronger security have been proposed, but they are either inefficient or proved secure in the random oracle model. In this work, we put forward a new encryption scheme in the common reference string model. Based on the standard DBDH assumption, the proposed scheme is proved completely non-malleable secure against adaptive chosen ciphertext attacks in the standard model. In our scheme, the well-formed public keys and ciphertexts could be publicly recognized without drawing support from unwieldy techniques like non-interactive zero knowledge proofs or one-time signatures, thus achieving a better performance.

    Original languageEnglish
    Title of host publicationASIA CCS 2016 - Proceedings of the 11th ACM Asia Conference on Computer and Communications Security
    EditorsXiaoFeng Wang, Xinyi Huang
    Place of PublicationNew York NY USA
    PublisherAssociation for Computing Machinery (ACM)
    Number of pages6
    ISBN (Print)9781450342339
    Publication statusPublished - 30 May 2016
    EventACM Symposium on Information, Computer and Communications Security 2016 - Xi'an, China
    Duration: 30 May 20163 Jun 2016
    Conference number: 11th


    ConferenceACM Symposium on Information, Computer and Communications Security 2016
    Abbreviated titleAsiaCCS 2016
    Internet address


    • Chosen-ciphertext attack
    • Complete non-malleability
    • Public Key encryption
    • Standard model

    Cite this