[Busec] PhD Defense of Dimitris Papadopoulos, tomorrow!

Sharon Goldberg goldbe at cs.bu.edu
Thu Jul 21 13:27:59 EDT 2016


FYI!

---------- Forwarded message ----------
From: Streubel, Jennifer <jenn4 at bu.edu>
Date: Thu, Jul 21, 2016 at 12:10 PM
Subject: Dimitrios Papadopoulos, Friday, July 22, 2016 at 9:00am in Hariri
Institute for Computing Seminar Room


*PhD Thesis Defense*

*Function-specific Schemes for Verifiable Computation*

*Dimitrios Papadopoulos, BU*

*Friday, July 22, 2016 at 9:00am in **Hariri Institute for Computing
Seminar Room*



*Abstract.* An integral component of modern computing is the ability to
outsource data and computation to powerful remote servers, for instance, in
the context of cloud computing or remote file storage. While participants
can benefit from this interaction, a fundamental security issue that arises
is that of integrity of computation: How can the end-user be certain that
the result of a computation over the outsourced data has not been tampered
with (not even by a compromised or adversarial server)?

Cryptographic schemes for verifiable computation address this problem by
accompanying each result with a proof that can be used to check the
correctness of the performed computation. Recent advances in the field have
led to the first implementations of schemes that can verify arbitrary
computations. However, in practice the overhead of these general-purpose
constructions remains prohibitive for most applications, with proof
computation times (at the server) in the order of minutes or even hours for
real-world problem instances. A different approach for designing such
schemes targets specific types of computation and builds custom-made
protocols, sacrificing generality for efficiency. An important
representative of this function-specific approach is an authenticated data
structure (ADS), where a specialized protocol is designed that supports
query types associated with a particular outsourced dataset.

This thesis presents three novel ADS constructions for the important query
types of set operations, multi-dimensional range search, and pattern
matching, and proves their security under cryptographic assumptions over
bilinear groups. The scheme for set operations can support nested queries
(e.g., two unions followed by an intersection of the results), extending
previous works that only accommodate a single operation. The range search
ADS provides an exponential (in the number of attributes in the dataset)
asymptotic improvement from previous schemes for storage and computation
costs. Finally, the pattern matching ADS supports text pattern and XML path
queries with minimal cost, e.g., the overhead at the server is less than 4%
compared to simply computing the result, for all tested settings. The
experimental evaluation of all three constructions shows significant
improvements in proof-computation time over general-purpose schemes.

*Committee.* Nikos Triandopoulos, Sharon Goldberg, Ran Canetti, Charalampos
Papamanthou, Leonid Reyzin (chair).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20160721/9abe03d1/attachment.html>


More information about the Busec mailing list