Designing Quantum-Safe Conjunctive SSE: How Fast Can You Go?

Designing quantum-safe SSE schemes that efficiently support conjunctive queries while maintaining only a linear storage overhead relative to the database size is an important research area with growing demand. In this direction, Talapatra et al. introduced OQXT [EUROS& P’23], the first quantum-safe conjunctive SSE scheme based on hard lattice assumptions. More recently, Talapatra et al. proposed a scalable extension, NTRU-OQXT [CiC’25], built upon a scalable alternative to OQXT. To the best of our knowledge, NTRU-OQXT is the most efficient quantum-safe SSE scheme that can handle conjunctive queries. In this paper, we first discuss some security vulnerabilities in NTRU-OQXT and argue that trivial fixes would incur additional efficiency costs. To this end, we propose a variant of NTRU-OQXT, dubbed NTRU-OQXT+, that not only addresses the security vulnerabilities of NTRU-OQXT but also provides much improved performance.