View all Seminars  |  Download ICal for this event

Cryptographic Schemes for Predicate Evaluation and Search on Outsourced Data

Series: Ph.D. Thesis Defense

Speaker: Mr. Sayantan Mukherjee Ph.D student Dept. of CSA

Date/Time: Feb 04 14:30:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Faculty Advisor: Prof. Sanjit Chatterjee

Recent improvements in architecture and networking are fueling ever growing interest in outsourcing data as well as computation over that data. However, this comes at the cost of trusting the service provider with user data as well as computation which often is violated without the user's knowledge. In this work, we propose a few cryptosystems that address various aspects of cryptographic security of outsourced data. Evaluating a predicate function of interest in the encrypted domain is currently one of the challenging questions in this domain. Our first two works in this thesis focus on evaluation of such predicate functions in the encrypted domain. Then we move to the question of performing search on the outsourced cloud data. The question of searching over outsourced data comes in both theoretical and practical flavors. We have pursued both the directions and have come up with solutions for a few selected problems. The first work deals with a simple access control mechanism where a message is encrypted with respect to a set S. A ciphertext can be decrypted with a secret key associated with a set T if and only if T is a subset of S. Such a scheme is called subset predicate encryption (SPE) and can be used as a building block for constructing wildcard IBE (WIBE), wicked IBE (WKD-IBE) as well as CP-ABE for DNF formula evaluation etc. We propose two constructions of SPE in the large-universe setting with constant-size keys. Our first SPE scheme achieves constant-size ciphertext while the second scheme achieves better security assurance namely, adaptive security in the standard model. Chosen Ciphertext Security (CCA) is the strongest notion of security that is often mandatory in practical scenario. As the adversary in this model is active, devising a CCA-secure encryption scheme is often hard. There are a few techniques that convert CPA-secure predicate encryptions (PE) to CCA-security generically but at a non-trivial cost which is typically proportional to the ciphertext size of the underlying CPA-secure scheme. We devise two generic constructions of CCA-secure PEs from CPA-secure pair encoding-based PEs incurring only a small constant amount of additional cost. Our first work on searching in the encrypted domain deals with two related problems of access control-based search. The first problem is to perform keyword search restricted within a privileged set. Available solutions of this problem achieve selective security under parameterized non-standard assumptions. We propose a solution to the so-called Broadcast Encryption with Keyword Search (BEKS) which is efficient and adaptive secure under a standard static assumption. The second problem takes motivation from encrypted email service where a client might search if the newly received mail contains any of the “specified” keywords. We propose a solution to this problem called Key-Aggregate Searchable Encryption (KASE) that allows searching without leaking any new information to the server. As the name suggests, our KASE construction enjoys constant-size secret keys and is proved adaptive secure under a standard static assumption. On the more applied aspects, our next work presents a searchable encryption framework that can support a number of predicate functions simultaneously. To design the framework, we define a few encodings on top of well-studied Hidden Vector Encryption (HVE). Our novelty lies in the optimization of encodings which result in better search complexity for a few queries and at the same time support new types of queries than the state-of-the-art. This framework can be used to compute statistics on encrypted tabular data like relational database management systems. A problem of recent interest is to perform wildcard search in the encrypted domain in the symmetric key setting. Precisely, the search should find the list of keywords w that match with the wildcard queryword w’ where the match denotes wildcard pattern matching. Non-triviality of this problem follows from the unrestricted nature of the wildcards allowed in a queryword. We reduce the problem of wildcard search to that of secure Boolean formula evaluation in the encrypted domain. This results in a protocol called HAWcS, a provably secure construction of wildcard search in the three party setting. HAWcS performs orders of magnitude better than the state-of-the-art as both our theoretical analysis and prototype implementation suggest. The final work improves upon an existing technique of authenticated email search. In this problem, the cloud service provider who stores the outsourced data has to return an efficiently verifiable proof of the search result. The requirement from this protocol is that a thin client should be able to verify the correctness of the search it has requested the server to perform. We propose a more comprehensive solution of authenticated e-mail search in the two party setting. Our prototype implementation gives evidence to the practicability of our proposal.

Speaker Bio:

Host Faculty: