A Multi-User Forward Secure Dynamic Symmetric Searchable Encryption with Enhanced Security

Dynamic symmetric searchable encryption has been widely used in cloud storage due to its functionality of dynamic encrypted data search. However, recent studies have shown that dynamic searchable encryption is vulnerable to file injection attacks. In order to resist such attacks, several forward secure symmetric searchable encryption schemes have been proposed. Unfortunately, most of the existing forward secure symmetric searchable solutions only work in the single user setting. In NSS 2018, Wang et al. proposed a multi-user forward secure dynamic searchable encryption scheme (MFS), by introducing a semi-honest proxy server that does not collude with the cloud server. However, we found that the forward security of the scheme can be compromised by the adversary who observes the association between the new update and the previous search tokens through eavesdropping attacks or replay attacks. To address this issue, a multi-user forward secure dynamic searchable symmetric encryption scheme EMFS is proposed with enhanced security, by exploiting user authentication mechanism without the need of state information transfer. We also adopt a new index structure to improve the efficiency. Finally, we give formal security proof to show that our scheme can resist the two attacks mentioned above, while maintaining forward security. Compared with Wang et al’s scheme, our construction provides a higher level of practical efficiency by reducing the complexity of deletion from O(n\-w) to O(1), where n\-w denotes the number of matching documents for keyword w.