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

Publication Name

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)


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.

Open Access Status

This publication is not available as open access


13555 LNCS

First Page


Last Page


Funding Number


Funding Sponsor

Horizon 2020 Framework Programme



Link to publisher version (DOI)