Here’s the new technique to fast-track deployment of searchable encryption

Cloud storage services, such as Google Drive and Dropbox, have made it easier to share documents and files across devices and among several collaborators. While these service providers password protect access to the account, the cloud service itself generally has access to the files, making it easier for users to search, navigate, and edit files. However, in certain cases, users may choose to encrypt files before saving them, making it harder to search and find the documents using the cloud service – if the user makes changes to a document, they must then download all the documents, decrypt them, re-encrypt them with the newly updated document, and finally save them again. With that issue in mind, researchers have been exploring searchable encryption techniques to improve cloud storage security that still enable search. Dr Chiara Marcolla, lead cryptographer at the Technology Innovation Institute’s (TII) Cryptography Research Center, explained, “Searchable encryption tries to find a way to encrypt the data so that when you search for something in the data, you can do it in a way that the cloud service will not know what you searched for and what it gives you back.”

However, each approach comes with some trade-offs between security and speed of search. Dr Marcolla added, “If you leave all the documents in the clear, then the search is super-efficient but insecure. However, if you use normal encryption, it is secure but not searchable.”

Dr Marcolla, alongside a team of researchers at TII, has been working on a new approach called ‘Exipnos’ that promises to improve both the performance and security of searchable encryption, as well as verify that the cloud providers deliver full search results. This aims to help guard against instances where cloud providers might deliver partial results to save processing power or from malicious intent.

How searchable encryption works
Searchable encryption begins by labelling each document with one or more keywords, such as names in a picture or themes in documents. The database, which comprises a table linking the keywords and the documents, and the documents themselves are encrypted. In a static approach, both the document and index are encrypted once, but cannot be changed.
Researchers have been exploring how to enable dynamic encryption to allow both the documents and the index to be incrementally updated without leaking information. However, different kinds of privacy leakages can occur, which could compromise information about or within the document, searches, or interactions. “Dynamic encryption is more useful since you can update both the document and the database, although it leaks more information than techniques that are not dynamic,” Dr Marcolla said.

Forward privacy guarantees that document updates are not linked to previous searches, and helps prevent hackers, and the cloud service itself, from determining which keywords are involved in the keyword/document pairs that are being updated, even if they do not know the keyword itself. On the other hand, backward privacy prevents information leakages from deleted data. There are three types of backward privacy. Type 1 reveals the timestamp of matched inserted files, the total number of updates, and matching¬ documents associated with a search; Type 2 also reveals an update’s timestamp; and Type 3 reveals the type of updates, such as insert or delete operations.

Exipnos supports type 2 data leakage protection, but not Type 1. However, allowing some data leakage is deemed to improve performance and the minimal leakage is not likely to present a significant risk to state-of-the-art attacks, in which Dr Marcolla explained, “If you try to cover too much information, it is less efficient.”

Different approaches
The team carried out a comparison of Exipnos’ performance to 18 prior schemes, such as Sophos and Mitra, and found that Exipnos is the most efficient scheme to achieve forward and type 2 backward privacy through the smallest client requirements. Moreover, it is the first scheme that achieves both forward and backward privacy and is also verifiable in that it can verify that the cloud service delivers the complete list of documents in the results and that the results have not been tampered with. In addition, Exipnos can mathematically verify that the service delivers the full results list, which is useful in protecting against cases when the cloud service might cheat to reduce processing overhead.

Sophos was one of the first searchable encryption algorithms to achieve forward privacy and is among the most efficient existing schemes to achieve forward privacy through the lowest client requirements. When comparing Expinos to Sophos, it was found that Exipnos can search a document 10-20 times faster and also achieves type 2 backward privacy, whereas Sophos can only attain forward privacy, but not backward privacy.

Another alternative to Sophos is Mitra, which can achieve forward and type 2 backward privacy and is significantly faster. When comparing Exipnos to Mitra, it was found that while Expinos is not as fast, it has a constant query size, so the time needed for Expinos to generate a query is much faster than Mitra. In their test, an average search time took 0.3 microseconds for Mitra compared to 0.9 microseconds for Exipnos. However, Mitra’s query length grows with the number of documents – an Exipnos query could be more than 4,500 times faster than Mitra when the number of matching documents is larger than 10,000.

One challenge presented with the new technique is that two new lines are added to the encrypted database table anytime a document is updated due to additions or deletions, which could become an issue if users delete a great quantity of data over time. “The size of the encrypted database is not generally huge, but when you have millions of documents, it could be a problem,” said Dr Marcolla. Future improvements for Exipnos could explore methods for building the database so that it shrinks when a document is deleted.

Looking ahead, this research has the potential to pave the way for searchable encryption in cloud services. “If someone finds a useful searchable encryption scheme, cloud providers could adopt it. In the end, you can have all your data securely stored in the cloud. And if you use searchable encryption, you can safely search inside the documents and update documents so that the cloud providers could not see what is inside and what you are looking for,” added Dr Marcolla.

Read: US firm Resecurity opens new AI-driven R&D centre in Saudi Arabia