DIMACS Summer 2014

General Information

Student: W.B. Drazen
Office: CoRE 446
School: The City College of New York
E-mail: whitneyd [at] reu dot dimacs dot rutgers
Project: Extension of Remote Verifiable Keyword Search

Project Description

Remote Verifiable Keyword Search allows a client to store an encrypted file with a server and have the server perform search functions on it without access to the plain text file. This is an important capability when the file is too large for the client device to store or search it efficiently. What makes Remote Verifiable keyword search different from other protocols and that it allows us in some sense to verify the search results. Our goal is to extend the protocol so that we can handle multiple files and perhaps a more robust set of queries.

Weekly Log

Week 1:
Review of Remote Verifiable Keyword Search BVG algorithm. Literature review on Searchable Symmetric Encyrption
Week 2:
Further literature review and scoping of research project. Obtained a result with advisor to verify queries in a multi-document setting. We obtained more papers with different protocols for the unverified multi-document case and we will be looking into whether we can also extend these protocols with to include verification.
Week 3:
Met with Professor David Cash from the Rutgers University Computer Science Department. Reviewed a paper titled "Outsourced Symmetric Private Information Retrieval", which deals with delegating the ability to make authorized queries on a database to clients who are not permitted to access all of the data. This includes a variant, where the database owner is not allowed to know the complete query, but authorizes based on combinations of attributes. We examined ways we can apply verification from Professor Gennaro's paper in order extend these protocols to verifiable ones. We also reviewed zero-knowledge proofs.
Week 4:
Met with professors Cash and Gennaro to further discuss how to apply verification to a multi-client protocols. Briefly examined how lattice problems can be applied to create cryptographic systems. Worked further on the verifiable multi-client protocol and examined the leakage of the protocol. We determined that although the leakage is greater in the protocol we developed, it could be a reasonable trade-off in certain circumstances. Began to examine the a paper on extending protocols to a dynamic database.
Week 5:
Met with professor Cash to finalize the specification for the verifiable multiclient protocol. Began typesetting basic protocols and our extensions for review by professors Gennaro and Cash.
Week 6:
Typesetting of protocol in Latex. Review of security analysis and computational complexity of our newly developed protocol.
Week 7:
Discussed new protocol with Professor Gennaro via email. Prepared and gave presentation to DIMACS REU group with E. Ekwedike.
Week 8:
Met with Professor Gennaro about the final spec of the protocol and discussed the version, which we will use in our write-up for submission. Reviewed a paper on Verifiable Attribute-Based Keyword Search. This protocol allows more flexible access to the data, however there is a chance of unauthorized access. The protocol relies on Bloom Filters, which involve hash functions with collisions. Thus if there are too many collisions, there may be a query, which should not be authorized based on the permissions, but is anyway. The protocol also makes use of a structure called an access tree, which determines which data a client with a set of permissiosn should be able to view.


Additional Information