Efficient completely non-malleable and RKA secure public key encryptions

Shi-Feng Sun, Udaya Parampalli, Tsz Hon Yuen, Yu Yu, Dawu Gu

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

1 Citation (Scopus)


Motivated by tampering attacks in practice, two different but related security notions, termed complete non-malleability and relatedkey attack security, have been proposed recently. In this work, we study their relations and present the first public key encryption scheme that is secure in both notions under standard assumptions. Moreover, by exploiting the technique for achieving complete non-malleability, we give a practical scheme for the related-key attack security. Precisely, the scheme is proven secure against polynomial functions of bounded degree d under a newly introduced hardness assumption called dmodified extended decisional bilinear Diffie-Hellman assumption. Since the schemes are constructed in a direct way instead of relying on the noninteractive zero knowledge proof or signature techniques, they not only achieve the strong security notions but also have better performances.

Original languageEnglish
Title of host publicationInformation Security and Privacy
Subtitle of host publication21st Australasian Conference, ACISP 2016, Melbourne, VIC, Australia, July 4-6, 2016, Proceedings, Part II
EditorsJoseph K. Liu, Ron Steinfeld
Place of PublicationSwitzerland
Number of pages17
ISBN (Electronic)9783319403670
ISBN (Print)9783319403663
Publication statusPublished - 2016
Externally publishedYes
EventAustralasian Conference on Information Security and Privacy 2016 - Melbourne, Australia
Duration: 4 Jul 20166 Jul 2016
Conference number: 21st
https://link.springer.com/book/10.1007/978-3-319-40253-6 (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceAustralasian Conference on Information Security and Privacy 2016
Abbreviated titleACISP 2016
Internet address


  • Chosen-ciphertext attack
  • Complete non-malleability
  • Public key encryption
  • Related-key attack

Cite this