||The City College of New York
||emmanuel.ekwedike [at] rutgers.edu
||Extension of the Verifiable Keyword Encrypted Search
Optimization theory, operations research, security systems and mathematical modeling.
Verifiable search on encrypted files is motivated by the recent surge toward cloud storage. A weak client with storage limitations can delegate the burden of data processing to the cloud. For a secured delegation, a client must have the ability to efficiently verify the results of the server for any arbitrary query.
There are some protocols in the literature dealing with verifiable keyword encrypted search, which can handle verification for a single keyword query. However, these existing protocols do not support expressive queries. On the other hand, there are searchable symmetric encryption (SSE) protocols that do support Boolean queries, but do not have verification component.
The aim of this project is to develop efficient protocols to verifiably perform searches over outsourced encrypted database with full security guarrantee. Specifically, we extend two SSE protocols (OXT and MC-OXT) by adding verification steps. These new verification features would allow a client to efficiently verify whether the server faithfully executed a search operation or not.
This project has real world applications in cybersecurity. For example, ecrypted verifiable search is important during intelligence sharing between two or more disparate groups.
This project is joint work Whitney Drazen .
First week (May 26th - May 30th)
- Orientation and Introduction.
- Background readings on verifiable keyword search.
- Met with Dr. Rosario to discuss our summer team project.
Second week (June 2nd - June 6th)
- More background readings on BVG algorithm.
- In the implimentation of BGV protocol, a client stores a set $S$ with a server along with some authentication
information $Auth_S$. Later the client queries the server for an arbitrary keyword $w$; the server returns the
resulting output in the form ($w \in S$ or $w \notin S$) together with a unique authentication tag $auth_w$.
- Presented our research problem to the DIMACS community.
Third week (June 9th - June 13th)
- I met with Dr. Rosario and we implemented verification on multiple documents using the single keyword solution.
- Read notes on Lattice-based cryptogaphy and searchable symmetric encryption.
- Learned OXT protocol; this protocal supports conjunctive queries and its implementation mostly uses Diffie-Hellman exponentiation.
Fourth week (June 16th - June 20th)
- Attended a talk on combinatorics and discrete mathematics.
- More literature review on searchable symmetric encryption with support to boolean queries.
- Learned interactive proofs and zero knowledge proofs.
Fifth week (June 23th - June 27th)
- Modified OXT by eliminating the Diffie Hellman exponentiation and using fast asymmetric cryptosystem. The resultant protocol leaks the same knowledge as the original OXT protocol and perhaps is more efficient.
- Wrote summary of OXT modification and analyzed the communication complexity of the resultant protocol.
- Obtained more literature resources from Dr. Rosario.
Sixth week (June 30th - July 4th)
- Finalized OXT SSE protocol extension.
- Read OSPIR paper (by S. Jarecki et. al.) with a particular focus on the Multi-client OXT protocol.
- Worked on adding verification to the multi-client setting of OXT protocol.
Seventh week (July 7th - July 11th)
- Visited IBM watson Research Center and met with some scientists.
- Attended lectures and research presentations.
- Consulted literatures on publicly verifiable models for cloud computations.
Eighth week (July 14th - July 18th)
- Attended a talk on the shortest path problem; the talk focuced on the continous case.
- More reading on the publicly verifiable protocols and generalizations.
- Prepared and presented our researh results to the DIMACS community.
Ninth week (July 21th - July 25th)
- Extended MC-OXT to full VKES security using the publicly verifiable solution and zero knowledge proofs.
- Wrote summary of our modification to the MC-OXT protocol.
- Met with my research team and summarized all our research results.
Tenth week (July 28th - August 1st)
- Competed all DHS requriements: research briefing, feedback form, and written report.
- Met with Withney and Dr. Rosario and discussed future work.
- Planned post summer research activities.
- First Presentation - June 6, 2014
- Second Presentation - July 18, 2014
- D. Cash, S. Jarecki, C. Jutla, H. Krawczyk, M. Rosu, M. Steiner. Highly-Scalable Searchable Symmetric Encyption with Support for Boolean Queries CRYPTO 2013
- S. Benabbas, R. Gennaro and Y. Vahlis. Verifiablable Delegation of Computation over Large Datasets CRYPTO 2011
- S. Jarecki, C. Jutla, H. Krawczyk, M. Rosu, M. Steiner. Outsourced Symmetric Private Information Retrieval CCS'13
- C. Papamanthou, E. Shi, R. Tamassia. Signatures of Correct Computation
- B. Parno, M. Raykova, and V. Vaikuntanathan. How to delegate and verify in public: Verifiable
computation from attribute-based encryption TCC 2012
- R. Gennario, et. al. Practical Remote Verifiable Keyword Search On Dynamically Changing Files
Non-Technical Research Report
Efficient Verifiable SSE