Public-key encryption resilient to linear related-key attacks

Hui Cui, Yi Mu, Man Ho Allen Au

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

5 Citations (Scopus)


In this paper, we consider the security of public-key encryption schemes under linear related-key attacks, where an adversary is allowed to tamper the private key stored in a hardware device, and subsequently observe the outcome of a public-key encryption system under this modified private key. Following the existing work done in recent years, we define the security model for related-key attack (RKA) secure public-key encryption schemes as chosen-ciphertext and related-key attack (CC-RKA) security, in which we allow an adversary to issue queries to the decryption oracle on the linear shifts of the private keys. On the basis of the adaptive trapdoor relations via the one-time signature schemes, Wee (PKC’12) proposed a generic construction of public-key encryption schemes in the setting of related-key attacks, and some instantiations from Factoring, BDDH with CC-RKA security, and DDH but with a weaker CC-RKA security. These schemes are efficient, but one-time signatures still have their price such that in some cases they are not very efficient compared to those without one-time signatures. Bellare, Paterson and Thomson (ASIACRYPT’12) put forward a generic method to build RKA secure public-key encryption schemes, which is transformed from the identity-based encryption schemes. However, so far, the efficient identity-based encryption schemes are generally based on parings. To generate a specific construction of public-key encryption schemes against related-key attacks without pairings, after analyzing the related-key attack on the Cramer-Shoup basic public-key encryption scheme, we present an efficient public-key encryption scheme resilient against related-key attacks without using one-time signature schemes from DDH. Finally, we prove the CC-RKA security of our scheme without random oracles.
Original languageEnglish
Title of host publicationSecurity and Privacy in Communication Networks - 9th International ICST Conference, SecureComm 2013, Revised Selected Papers
PublisherSpringer Verlag
Number of pages15
ISBN (Print)9783319042824
Publication statusPublished - 1 Jan 2013
Externally publishedYes
Event9th International Conference on Security and Privacy in Communication Networks, SecureComm 2013 - Sydney, Australia
Duration: 25 Sept 201328 Sept 2013

Publication series

NameLecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST
Volume127 LNICST
ISSN (Print)1867-8211


Conference9th International Conference on Security and Privacy in Communication Networks, SecureComm 2013


  • CC-RKA security
  • Public-key encryption
  • Related-key attack

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Public-key encryption resilient to linear related-key attacks'. Together they form a unique fingerprint.

Cite this