DEKS: A Secure Cloud-Based Searchable Service Can Make Attackers Pay

Yubo Zheng, Peng Xu*, Wei Wang, Tianyang Chen, Willy Susilo, Kaitai Liang, Hai Jin

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review


Many practical secure systems have been designed to prevent real-world attacks via maximizing the attacking cost so as to reduce attack intentions. Inspired by this philosophy, we propose a new concept named delay encryption with keyword search (DEKS) to resist the notorious keyword guessing attack (KGA), in the context of secure cloud-based searchable services. Avoiding the use of complex (and unreasonable) assumptions, as compared to existing works, DEKS optionally leverages a catalyst that enables one (e.g., a valid data user) to easily execute encryption; without the catalyst, any unauthenticated system insiders and outsiders take severe time consumption on encryption. By this, DEKS can overwhelm a KGA attacker in the encryption stage before it obtains any advantage. We leverage the repeated squaring function, which is the core building block of our design, to construct the first DEKS instance. The experimental results show that DEKS is practical in thwarting KGA for both small and large-scale datasets. For example, in the Wikipedia, a KGA attacker averagely takes 7.23 years to break DEKS when the delay parameter T= 2 24. The parameter T can be flexibly adjusted based on practical needs, and theoretically, its upper bound is infinite.

Original languageEnglish
Title of host publicationComputer Security – ESORICS 2022 - 27th European Symposium on Research in Computer Security, Proceedings
EditorsVijayalakshmi Atluri, Roberto Di Pietro, Christian D. Jensen, Weizhi Meng
Number of pages19
ISBN (Print)9783031171451
Publication statusPublished - 2022
Event27th European Symposium on Research in Computer Security, ESORICS 2022 - Virtual, Online
Duration: 26 Sep 202230 Sep 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13555 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th European Symposium on Research in Computer Security, ESORICS 2022
CityVirtual, Online

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.


  • Delay encryption with keyword search
  • Keyword guessing attack
  • Privacy
  • Security


Dive into the research topics of 'DEKS: A Secure Cloud-Based Searchable Service Can Make Attackers Pay'. Together they form a unique fingerprint.

Cite this