Charalampos Papamanthou

Daniel Blackley, Nathaniel Moyer, Charalampos Papamanthou et al.

In this work, we show how knowledge of the query distribution, combined with access-pattern leakage, is sufficient to break multi-dimensional encrypted range queries, with provable guarantees. Prior attacks either recover only data topology without concrete coordinates for plaintexts (and as a result require post-hoc transformations), or assume adversarial control over database content; a strong and unrealistic threat model. Given knowledge of the query distribution, we revisit frequency matching, one of the earliest cryptanalytic ideas in this area, and push it to its limits in the multi-dimensional regime through LAMa ($\underline{L}$eakage-$\underline{A}$buse via $\underline{Ma}$tching). LAMa is a three-component framework that reconstructs plaintext coordinates in arbitrary dimensions without post-hoc transformations or data injection/poisoning. We complement LAMa with the first rigorous guarantees for multi-dimensional frequency-matching cryptanalysis, covering its query complexity, optimal parameterization, and worst-case reconstruction quality. Experiments on real-world data show that LAMa consistently outperforms the state of the art.

Mohammad Etemad, Alptekin Küpçü, Charalampos Papamanthou et al.

Searchable symmetric encryption (SSE) enables a client to perform searches over its outsourced encrypted files while preserving privacy of the files and queries. Dynamic schemes, where files can be added or removed, leak more information than static schemes. For dynamic schemes, forward privacy requires that a newly added file cannot be linked to previous searches. We present a new dynamic SSE scheme that achieves forward privacy by replacing the keys revealed to the server on each search. Our scheme is efficient and parallelizable and outperforms the best previous schemes providing forward privacy, and achieves competitive performance with dynamic schemes without forward privacy. We provide a full security proof in the random oracle model. In our experiments on the Wikipedia archive of about four million pages, the server takes one second to perform a search with 100,000 results.

Prateek Mittal, Charalampos Papamanthou, Dawn Song

A growing body of research leverages social network based trust relationships to improve the functionality of the system. However, these systems expose users' trust relationships, which is considered sensitive information in today's society, to an adversary. In this work, we make the following contributions. First, we propose an algorithm that perturbs the structure of a social graph in order to provide link privacy, at the cost of slight reduction in the utility of the social graph. Second we define general metrics for characterizing the utility and privacy of perturbed graphs. Third, we evaluate the utility and privacy of our proposed algorithm using real world social graphs. Finally, we demonstrate the applicability of our perturbation algorithm on a broad range of secure systems, including Sybil defenses and secure routing.

Michael T. Goodrich, Duy Nguyen, Olga Ohrimenko et al.

Searching accounts for one of the most frequently performed computations over the Internet as well as one of the most important applications of outsourced computing, producing results that critically affect users' decision-making behaviors. As such, verifying the integrity of Internet-based searches over vast amounts of web contents is essential. We provide the first solution to this general security problem. We introduce the concept of an authenticated web crawler and present the design and prototype implementation of this new concept. An authenticated web crawler is a trusted program that computes a special "signature" $s$ of a collection of web contents it visits. Subject to this signature, web searches can be verified to be correct with respect to the integrity of their produced results. This signature also allows the verification of complicated queries on web pages, such as conjunctive keyword searches. In our solution, along with the web pages that satisfy any given search query, the search engine also returns a cryptographic proof. This proof, together with the signature $s$, enables any user to efficiently verify that no legitimate web pages are omitted from the result computed by the search engine, and that no pages that are non-conforming with the query are included in the result. An important property of our solution is that the proof size and the verification time both depend solely on the sizes of the query description and the query result, but not on the number or sizes of the web pages over which the search is performed. Our authentication protocols are based on standard Merkle trees and the more involved bilinear-map accumulators. As we experimentally demonstrate, the prototype implementation of our system gives a low communication overhead between the search engine and the user, and allows for fast verification of the returned results on the user side.