Conjunctive Dynamic SSE Schemes Under Scrutiny: Exposing Privacy Issues in SDSSE-CQ-S and VCDSSE
摘要
Designing an efficient conjunctive dynamic searchable symmetric encryption (DSSE) scheme with forward and backward privacy is a crucial and rapidly growing area of research. Recently, Zuo et al., in PETs’25, proposed two state-of-the-art forward and backward private conjunctive dynamic SSE schemes, namely SDSSE-CQ and SDSSE-CQ-S. SDSSE-CQ is an efficient construction with minimal communication and computation overhead, but could achieve only a weaker notion of backward privacy. On the contrary, SDSSE-CQ-S surpasses SDSSE-CQ by offering a stronger backward privacy guarantee, however, at the cost of additional communication and computation overhead. Further to address the challenge in a potentially malicious server setting, Lu et al., in TCJ’22, proposed the first verifiable conjunctive dynamic SSE scheme, dubbed VCDSSE, offering forward and backward security along with verifiable search results. This paper revisits the state-of-the-art constructions, SDSSE-CQ-S and VCDSSE, and reports fatal privacy issues. First, we have attacked SDSSE-CQ-S and disproved its stronger privacy claim, reducing its privacy guarantee to an unarguably weaker level. The novelty of our attack lies in its simplicity; it relies only on tricky but elementary algebraic calculations, yet remains highly effective. Next, we have attacked VCDSSE and shown that VCDSSE fails to provide forward privacy. We have also identified the flaw in the design of VCDSSE, causing the privacy loss, and argued that there is no immediate solution. We have explained both the issues through respective prototype examples. We strongly believe that our attacks will inspire researchers to design efficient dynamic conjunctive SSE schemes that provide proper strong privacy guarantees.