University of Twente Student Theses


Secure searching through encrypted data - Creating an efficient Hidden Vector Encryption construction using Inner Product Encryption

Veen, Dirk van (2011) Secure searching through encrypted data - Creating an efficient Hidden Vector Encryption construction using Inner Product Encryption.

[img] PDF
Abstract:In this thesis, the problem of hosting a database with sensitive information on an honest but curious server is explored. Simply stated, the problem is the following: how can we store information and perform queries in such a way that the server cannot learn the contents of the information or the queries. Although in an ideal situation the stored information would be a relational database, the scope of this thesis is limited to the storage and querying of metadata. Two of the general approaches to solving this problem are Hidden Vector Encryption (HVE) and Inner Product Encryption (IPE). The former allows for conjunctions of a wide variety of queries in a relatively efficient manner, but has some innate problems regarding the confidentiality of search queries; the latter allows for disjunctions of an even wider variety of queries and can prove confidentiality of search queries, but suffers some efficiency problems. In this master thesis, a solution is constructed that incorporates both the efficiency of HVE and the security of IPE. In order to do this, current HVE and IPE implementations and the intuitions behind these implementations are studied to retrieve their innate strengths and weaknesses and to understand their interrelations. This creates a context, within which a main intuition is designed. This intuition involves employing the main ideas behind Seghi’s HVE construction to give IPE’s shorter input vectors. This would make the computational cost of performing a query on a ciphertext linear to the maximum number of wildcards in a query instead of linear in twice the total number of elements in a query. Especially in HVE schemes that allow a relatively low number of wildcards, this would be a great improvement. The intuition had one problem, however, as it was not fully compatible with existing IPE constructions. Two attempts were made at creating a construction that compensates for this incompatibility. The first attempt revolved around extending an existing IPE scheme, but was ultimately proven insecure. The second attempt uses one insight from the first attempt to amend the main intuition in such a way that the incompatibility is removed. This results in our main construction. Additionally, the same technique that is used in the second attempt is used to create an alternative construction that is more efficient than the main construction in two specific situations.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Computer Science MSc (60300)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page