Revisiting Relations of Security Notions in Searchable Encryption
Kazuki Sato, Takumi Amada, Kyoichi Asano, Yohei Watanabe, Mitsugu Iwamoto, Kazuo Ohta · 2025
Searchable symmetric encryption (SSE), which enables us to provide a way to search a large database efficiently for encrypted data, has attracted attention over the past two decades. SSE allows the leakage of insignificant information to achieve practical efficiency. Curtmola et al. (CCS '06) defined the model of SSE and two security notions: semantic security and indistinguishability. They also proved the relationship between these notions under the standard leakage. However, while they only showed that semantic security implies indistinguishability, proving the equivalence of these security notions is an important future work. After Curtmola et al.'s work, numerous SSE schemes with various types of leakage have been proposed for trade-off between efficiency and security. In this paper, we prove the equivalence between indistinguishability and semantic security under more permissive yet reasonable leakage than the standard one. We can also show the implication even when search operations provide no leakage. In addition, we prove that semantic security implies indistinguishability under any leakage, whereas Curtmola et al. gave the proof only for the case of the standard leakage. In that sense, we extend their result and show that the implication holds regardless of the amount of leakage.