Public-Key Encryption with Delegated Search

L. Ibraimi, S.I. Nikova, Pieter H. Hartel, Willem Jonker

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

48 Citations (Scopus)
250 Downloads (Pure)


In a public key setting, Alice encrypts an email with the public key of Bob, so that only Bob will be able to learn the contents of the email. Consider a scenario where the computer of Alice is infected and unbeknown to Alice it also embeds a malware into the message. Bob’s company, Carol, cannot scan his email for malicious content as it is encrypted so the burden is on Bob to do the scan. This is not efficient. We construct a mechanism that enables Bob to provide trapdoors to Carol such that Carol, given an encrypted data and a malware signature, is able to check whether the encrypted data contains the malware signature, without decrypting it. We refer to this mechanism as public − key encryption with delegated search. We formalize and give a construction based on ElGamal public-key encryption. The proposed scheme has ciphertexts which are both searchable and decryptable. This property of the scheme is crucial since an entity can search the entire content of the message, in contrast to existing searchable public-key encryption schemes where the search is done only in the metadata part. We prove in the standard model that the scheme is ciphertext indistinguishable and trapdoor indistinguishable under the Symmetric External Diffie-Hellman (SXDH) assumption. We prove also the ciphertext one − wayness of the scheme under the modified Computational Diffie-Hellman (mCDH) assumption. We show that our scheme can be used in different applications such as detecting encrypted malware and forwarding encrypted email.
Original languageUndefined
Title of host publicationProceedings of the 9th International Conference on Applied Cryptography and Network Security (ACNS)
EditorsL. Javier, G. Tsudik
Place of PublicationBerlin
Number of pages18
ISBN (Print)978-3-642-21553-7
Publication statusPublished - Jun 2011
Event9th International Conference on Applied Cryptography and Network Security, ACNS 2011 - Nerja, Malaga, Spain
Duration: 7 Jun 201110 Jun 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag


Conference9th International Conference on Applied Cryptography and Network Security, ACNS 2011
OtherJune 7-10, 2011


  • IR-76610
  • EWI-20287
  • SCS-Cybersecurity
  • METIS-277695

Cite this