Skip navigation

A verifiable symmetric searchable encryption scheme based on the AVL tree

A verifiable symmetric searchable encryption scheme based on the AVL tree

Wang, Qing, Zhang, Xi, Qin, Jing, Ma, Jixin and Huang, Xinyi (2021) A verifiable symmetric searchable encryption scheme based on the AVL tree. The Computer Journal:bxab152. pp. 1-10. ISSN 0010-4620 (Print), 1460-2067 (Online) (doi:https://doi.org/10.1093/comjnl/bxab152)

[img] PDF (AAM)
36268_MA_A_verifiable_symmetric_searchable_encryption.pdf - Accepted Version
Restricted to Repository staff only until 9 October 2022.

Download (980kB) | Request a copy

Abstract

Verifiable symmetric searchable encryption is a keyword search technology that supports verification of search results. Many schemes improve search performance by dividing each keyword label into segments and storing them in a Trie-tree at the expense of high storage. And the index will degenerate into a linear linked list when all keyword labels have the same prefix except for the last segment. But it will greatly affect the search efficiency. In this paper, we propose a verifiable symmetric searchable encryption scheme based on the AVL Tree (abbreviated as VSSE-AVL), which uses complete keyword labels to build the index. Compared with the Trie-tree index, VSSE-AVL not only balances storage and search performance, but also avoids degradation. To verify the correctness and completeness of empty search results, we store path information in each leaf node and node with only one child node. Considering the substitution attack, we bind the file identifier and the file so that the client will find out once the server returns inconsistent search results. Rigorous security analysis shows VSSE-AVL satisfies privacy and verifiability. Compared with the verifiable SSE-2 with the same security, the experimental evaluation shows that our proposed scheme performs better on storage, search and verification.

Item Type: Article
Uncontrolled Keywords: keyword search; data verifiability; AVL tree
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Faculty / School / Research Centre / Research Group: Faculty of Engineering & Science
Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS)
Last Modified: 19 May 2022 15:05
URI: http://gala.gre.ac.uk/id/eprint/36268

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics