# [Busec] BUsec seminars: Justin Thaler (Tmw 3PM) Mohammad Mahmoody (Wed 10AM)

Sharon Goldberg goldbe at cs.bu.edu
Thu Nov 8 16:23:57 EST 2012

Hi all,

It's a busy few weeks.

At our seminar tomorrow (Friday) at 3PM in MCS148, Justin Thaler from
Harvard will tell us about his work on verifiable computation.

Sunday and Monday is the Turing 100 celebration, including speakers
like Leonid Levin, Marvin Minsky, Silvio Micali, and Ron Rivest:

http://www.bu.edu/hic/turing100/

Finally, on Wednesday at 10AM next week (note new date, due to the
Turing 100) Mohammad Mahmoody from Cornell will be discussing tamper
resilient crypto.

Abstracts below.  See you tomorrow!

Sharon

BUsec Mailing list:  http://cs-mailman.bu.edu/mailman/listinfo/busec

****
Title: Practical Verified Computation with Streaming Interactive Proofs
Speaker: Justin Thaler, Harvard
Fri Nov 9, 2012, 3:00pm – 4:30pm
MCS148

A potential problem in outsourcing work to commercial cloud computing
services is trust. If we store a large data set with a service
provider, and ask them to perform a computation on that data set --
for example, to compute the eigenvalues of a large graph, or to
compute a linear program on a large matrix derived from a database --
how can we know the computation was performed correctly? Obviously we
don't want to compute the result ourselves, and we might not even be
able to store all the data locally. This leads to new problems in the
streaming paradigm: we consider a streaming algorithm (modeling a user
with limited memory and computational resources) that can be assisted
by a powerful helper (the service provider). The goal of the service
provider is to not only provide the user with answer, but to convince
the user the answer is correct.

In this talk, I will describe a recent line of work exploring the
application of proof systems to problems that are streaming in nature.
The protocols I will discuss utilize and extend powerful ideas from
communication complexity and the theory of interactive proofs, and I
will argue that many are highly practical, achieving millions of
updates per second and requiring little space and communication.

Joint work with Amit Chakrabarti, Graham Cormode, Andrew McGregor,
Michael Mitzenmacher, and Ke Yi

****

On the (Im)Possibility of Tamper-Resilient Cryptography
Using Fourier Analysis in Computer Viruses
Wed Nov 14, 2012 10AM
MCS137

We initiate a study of the security of cryptographic primitives in the
presence of efficient tampering attacks to the randomness of honest
parties. More precisely, we consider p-tampering attackers that may
tamper with each bit of the honest parties' random tape with
probability p, but have to do so in an "online" fashion. We present
both positive and negative results:

* Any secure encryption scheme, bit commitment scheme, or zero-
knowledge protocol can be “broken” with probability p by a p-tampering
attacker.
The core of this result is a new Fourier analytic technique for
biasing the output of bounded-value functions, which may be of
independent interest (and provides an alternative, and in our eyes
simpler, proof of the classic Santha-Vazirani theorem).

* Assuming the existence of one-way functions, cryptographic
primitives such as signatures, identification protocols can be made
resilient to p-tampering attacks for any p = 1/n^{\alpha}, where
\alpha > 0 and n is the security parameter.

Joint work with Per Austrin, Kai-Min Chung, Rafael Pass, and Karn Seth