Practical and Secure Searchable Symmetric Encryption Constructions

Searchable symmetric encryption (SSE) enables secure searching of encrypted databases (i.e., a set of documents) outsourced to an untrusted server. Dynamic SSE (DSSE) extends this to allow secure updates to the encrypted database. However, SSE constructions have a trade-off between security, performance, and query expressiveness. The thesis enhances this trade-off through innovative designs and provides some new insights. Our first two contributions focus on DSSE working in the malicious model (known as verifiable DSSE (VDSSE)) and mainly concern single-keyword searches. The first contribution identifies a neglected issue whereby incorrect updates by the client can cause serious vulnerabilities for most VDSSE schemes.We propose a generic and efficient solution that can make any single-keyword DSSE scheme verifiable and tolerate incorrect updates from the client. The second contribution points out that the existing sound methods for verifying the integrity of document contents depend on expensive public-key techniques and proposes an efficient approach that only relies on lightweight symmetric techniques to verify document contents. We then consider Boolean searches that return documents satisfying a Boolean formula over multiple keywords. We focus on a leakage profile called the keyword pair result pattern (KPRP), which refers to the intersection of documents matched by any two keywords involved in a search. Attackers can leverage KPRP to recover searched keywords; hence KPRP should be hidden. However, existing KPRP-hiding solutions either incur overhead linear to the database size or have severe limitations, such as bringing false positive results, suffering from high round complexity, or failing to support dynamic databases. To address these issues, the thesis proposes new cryptographic primitives in its third and fourth contributions. The third contribution designs a primitive called Result-hiding Filter (RH-Filter) and uses it to achieve a Boolean SSE scheme (named HBS). HBS supports a rich class of Boolean queries, providing accurate search results while only requiring single-round interaction. The fourth contribution proposes a scheme named HDXT, which uses a new primitive called Attribute-updatable Hidden Map Encryption (AUHME) to ensure KPRP-hiding in the dynamic setting while demonstrating excellent search efficiency.

Name thesis:degree_name

PhD

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

ResearchSpace@Auckland

Year dc:date.issued

2023

Author dc:creator

• Yuan, Dandan

Advisors dc:contributor.advisor

• Russello, Giovanni
• Galbraith, Steven

Statement dc:rights

• Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Licence dc:rights.uri

• https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm

Handle dc:identifier.uri

https://hdl.handle.net/2292/67840

OAI identifier oai:identifier

oai:researchspace.auckland.ac.nz:2292/67840