Nothing is for Free: Security in Searching Shared & Encrypted Data

Most existing symmetric searchable encryption
schemes aim at allowing a user to outsource her encrypted
data to a cloud server and delegate the latter to search on her
behalf. These schemes do not qualify as a secure and scalable
solution for the multi-party setting, where users outsource
their encrypted data to a cloud server and selectively authorize
each other to search. Due to the possibility that the cloud
server may collude with some malicious users, it is a challenge
to have a secure and scalable multi-party searchable
encryption (MPSE) scheme. This is shown by our analysis
on the Popa-Zeldovich scheme, which says that an honest
user may leak all her search patterns even if she shares only
one of her documents with another malicious user. Based on
our analysis, we present a new security model for MPSE
by considering the worst-case and average-case scenarios,
which capture different server-user collusion possibilities.
We then propose a MPSE scheme by employing the bilinear
property of Type-3 pairings, and prove its security based on
the Bilinear Diffie-Hellman Variant (BDHV) and Symmetric
eXternal Diffie-Hellman (SXDH) assumptions in the random
oracle model.