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

    Abstract

    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)
    Pages901-906
    Number of pages6
    ISBN (Print)9781450342339
    DOIs
    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: 11
    http://meeting.xidian.edu.cn/conference/AsiaCCS2016/

    Conference

    ConferenceACM Symposium on Information, Computer and Communications Security 2016
    Abbreviated titleAsiaCCS 2016
    CountryChina
    CityXi'an
    Period30/05/163/06/16
    Internet address

    Keywords

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

    Cite this

    Sun, S. F., Gu, D., Liu, J. K., Parampalli, U., & Yuen, T. H. (2016). Efficient construction of completely non-malleable CCA secure public key encryption. In X. Wang, & X. Huang (Eds.), ASIA CCS 2016 - Proceedings of the 11th ACM Asia Conference on Computer and Communications Security (pp. 901-906). New York NY USA: Association for Computing Machinery (ACM). https://doi.org/10.1145/2897845.2897921
    Sun, Shi Feng ; Gu, Dawu ; Liu, Joseph K. ; Parampalli, Udaya ; Yuen, Tsz Hon. / Efficient construction of completely non-malleable CCA secure public key encryption. ASIA CCS 2016 - Proceedings of the 11th ACM Asia Conference on Computer and Communications Security. editor / XiaoFeng Wang ; Xinyi Huang. New York NY USA : Association for Computing Machinery (ACM), 2016. pp. 901-906
    @inproceedings{22eebd8ce7fa44079dedd6b9e0b0b404,
    title = "Efficient construction of completely non-malleable CCA secure public key encryption",
    abstract = "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.",
    keywords = "Chosen-ciphertext attack, Complete non-malleability, Public Key encryption, Standard model",
    author = "Sun, {Shi Feng} and Dawu Gu and Liu, {Joseph K.} and Udaya Parampalli and Yuen, {Tsz Hon}",
    year = "2016",
    month = "5",
    day = "30",
    doi = "10.1145/2897845.2897921",
    language = "English",
    isbn = "9781450342339",
    pages = "901--906",
    editor = "XiaoFeng Wang and Xinyi Huang",
    booktitle = "ASIA CCS 2016 - Proceedings of the 11th ACM Asia Conference on Computer and Communications Security",
    publisher = "Association for Computing Machinery (ACM)",
    address = "United States of America",

    }

    Sun, SF, Gu, D, Liu, JK, Parampalli, U & Yuen, TH 2016, Efficient construction of completely non-malleable CCA secure public key encryption. in X Wang & X Huang (eds), ASIA CCS 2016 - Proceedings of the 11th ACM Asia Conference on Computer and Communications Security. Association for Computing Machinery (ACM), New York NY USA, pp. 901-906, ACM Symposium on Information, Computer and Communications Security 2016, Xi'an, China, 30/05/16. https://doi.org/10.1145/2897845.2897921

    Efficient construction of completely non-malleable CCA secure public key encryption. / Sun, Shi Feng; Gu, Dawu; Liu, Joseph K.; Parampalli, Udaya; Yuen, Tsz Hon.

    ASIA CCS 2016 - Proceedings of the 11th ACM Asia Conference on Computer and Communications Security. ed. / XiaoFeng Wang; Xinyi Huang. New York NY USA : Association for Computing Machinery (ACM), 2016. p. 901-906.

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

    TY - GEN

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

    AU - Sun, Shi Feng

    AU - Gu, Dawu

    AU - Liu, Joseph K.

    AU - Parampalli, Udaya

    AU - Yuen, Tsz Hon

    PY - 2016/5/30

    Y1 - 2016/5/30

    N2 - 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.

    AB - 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.

    KW - Chosen-ciphertext attack

    KW - Complete non-malleability

    KW - Public Key encryption

    KW - Standard model

    UR - http://www.scopus.com/inward/record.url?scp=84979695258&partnerID=8YFLogxK

    U2 - 10.1145/2897845.2897921

    DO - 10.1145/2897845.2897921

    M3 - Conference Paper

    SN - 9781450342339

    SP - 901

    EP - 906

    BT - ASIA CCS 2016 - Proceedings of the 11th ACM Asia Conference on Computer and Communications Security

    A2 - Wang, XiaoFeng

    A2 - Huang, Xinyi

    PB - Association for Computing Machinery (ACM)

    CY - New York NY USA

    ER -

    Sun SF, Gu D, Liu JK, Parampalli U, Yuen TH. Efficient construction of completely non-malleable CCA secure public key encryption. In Wang X, Huang X, editors, ASIA CCS 2016 - Proceedings of the 11th ACM Asia Conference on Computer and Communications Security. New York NY USA: Association for Computing Machinery (ACM). 2016. p. 901-906 https://doi.org/10.1145/2897845.2897921