Multi-client searchable symmetric encryption (SSE) allows multiple third-party clients to execute fast encrypted search queries over a symmetrically encrypted database created by a data owner and held by an (untrusted) data server. Although SSE is ostensibly a symmetric-key cryptoprimitive, existing multi-client SSE schemes that support conjunctive and general Boolean queries rely crucially on the classical hardness of the discrete log problem over cyclic groups, and are completely broken by quantum attacks. This leaves open the question of designing multi-client conjunctive (and more expressive) SSE schemes from plausibly quantum-safe assumptions. In this paper, we present the first plausibly quantum-safe multi-client SSE scheme supporting conjunctive keyword queries while relying on the hardness of certain isogeny-based assumptions (such as CSIDH and CSI-FiSh) that can be modeled using cryptographic group actions. As a core technical contribution, we present a novel adaptation of the widely studied but quantum-broken Oblivious Cross-Tags ( \(\textsf{OXT}\) ) protocol (Cash et al., Crypto 2013) to the setting of cryptographic group actions. This scheme, which we call \(\textsf{GXT}\) , supports conjunctive keyword queries in the single-client setting. We then present \(\mathsf {MC\text {-}GXT}\) – an extension of \(\textsf{GXT}\) to the multi-client setting. Our constructions match the asymptotic efficiency guarantees of the original \(\textsf{OXT}\) scheme in terms of storage requirements and conjunctive query complexity, while additionally providing data and query privacy guarantees based on well-studied and plausibly quantum-safe isogeny-based hardness assumptions.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Post-quantum Multi-client Conjunctive Searchable Symmetric Encryption from Isogenies

  • Sikhar Patranabis

摘要

Multi-client searchable symmetric encryption (SSE) allows multiple third-party clients to execute fast encrypted search queries over a symmetrically encrypted database created by a data owner and held by an (untrusted) data server. Although SSE is ostensibly a symmetric-key cryptoprimitive, existing multi-client SSE schemes that support conjunctive and general Boolean queries rely crucially on the classical hardness of the discrete log problem over cyclic groups, and are completely broken by quantum attacks. This leaves open the question of designing multi-client conjunctive (and more expressive) SSE schemes from plausibly quantum-safe assumptions. In this paper, we present the first plausibly quantum-safe multi-client SSE scheme supporting conjunctive keyword queries while relying on the hardness of certain isogeny-based assumptions (such as CSIDH and CSI-FiSh) that can be modeled using cryptographic group actions. As a core technical contribution, we present a novel adaptation of the widely studied but quantum-broken Oblivious Cross-Tags ( \(\textsf{OXT}\) ) protocol (Cash et al., Crypto 2013) to the setting of cryptographic group actions. This scheme, which we call \(\textsf{GXT}\) , supports conjunctive keyword queries in the single-client setting. We then present \(\mathsf {MC\text {-}GXT}\) – an extension of \(\textsf{GXT}\) to the multi-client setting. Our constructions match the asymptotic efficiency guarantees of the original \(\textsf{OXT}\) scheme in terms of storage requirements and conjunctive query complexity, while additionally providing data and query privacy guarantees based on well-studied and plausibly quantum-safe isogeny-based hardness assumptions.