[Busec] busec this week: Pavel Hubacek (Wed 10AM)

Sharon Goldberg goldbe at cs.bu.edu
Tue Oct 22 21:40:11 EDT 2013

This week (tomorrow) our seminar speaker is Pavel Hubacek from Aarhus.
He'll tell us about new results on cryptography against rational
adversaries. The talk will be at the usual time: Wednesday 10am in MCS137
with lunch provided.

Next week, Monday Oct 28, we'll have a talk on digital forensics by Simson
Garfinkel, who is a professor at the Naval Postgraduate School.


 BUsec Calendar:  http://www.bu.edu/cs/busec/
 BUsec Mailing list:  http://cs-mailman.bu.edu/mailman/listinfo/busec
 How to get to BU from MIT:  Try the CT2 bus or MIT's "Boston Daytime
 Shuttle" http://web.mit.edu/facilities/transportation/shuttles/

Rational Arguments: Single Round Delegation with Sublinear Verification
Speaker: Pavel Hubacek. Aarhus & Northeastern.
Wed Oct 23, 10AM


Rational proofs, recently introduced by Azar and Micali (STOC 2012), are a
variant of interactive proofs in which the prover is neither honest nor
malicious, but rather rational. The advantage of rational proofs over their
classical counterparts is that they allow for extremely low communication
and verification time. Azar and Micali demonstrated their potential by
giving a one message rational proof for #P, in which the verifier runs in
time O(n), where n denotes the instance size. In a follow-up work (EC
2013), Azar and Micali proposed „super-efficient“ and interactive versions
of rational proofs and argued that they capture precisely the class TC0 of
constant-depth, polynomial-size circuits with threshold gates.

In this work, we show that by considering rational arguments, in which the
prover is additionally restricted to be computationally bounded, the class
NC1, of search problems computable by log-space uniform circuits of O(log
n)-depth, admits rational protocols that are simultaneously one-round and
polylog(n) time verifiable. This demonstrates the potential of rational
arguments as a way to extend the notion of „super-efficient“ rational
proofs beyond the class TC0.

The low interaction nature of our protocols, along with their sub-linear
verification time, make them well suited for delegation of computation.
While they provide a weaker (yet arguably meaningful) guarantee of
soundness, they compare favorably with each of the known delegation schemes
in at least one aspect. They are simple, rely on standard complexity
hardness assumptions, provide a correctness guarantee for all instances,
and do not require preprocessing.

Our rational arguments are constructed in two steps. We first design a
multi-round rational proof and then collapse it into a single round
argument. In doing so, we identify the gap between the reward given to a
truthful prover in the proof and the one given to a dishonest one as a key
parameter in the quality of the resulting argument. We leave it as an
intriguing open problem to determine whether one could „scale up“ the
underlying proofs to classes beyond NC1, and potentially even beyond P
(thus bypassing known impossibility results), and point out some
limitations in doing so for non-trivial languages.

This is a joint work with Siyao Guo, Alon Rosen and Margarita Vald.

Finding privacy leaks and stolen data with bulk data analysis and
optimistic decoding
Speaker: Simson L. Garfinkel, Associate Professor, Naval Postgraduate School
October 28, 2013, 11AM - 12

Modern digital forensics tools are largely based on the recovery and
analysis of files. This talk explores how identity information such as
email addresses, credit card numbers, and other of information can be more
efficiently found using bulk data analysis, and how results are
significantly improved through the use of optimistic decompression.
Together, these techniques can find important information on computer media
that are ignored by the majority of today's digital forensics tools.

This talk presents the results of a study of roughly 5000 hard drives
purchased on the secondary market and shows how different kinds of data
formats can be traced to different kinds of privacy leaks and coding
errors. It show how the results were generated using bulk_extarctor, an
easy-to-use open source digital forensics tool. Finally, it shows how
bulk_extractor was extended to detect data obscured with a simple
steganographic technique (XOR 255), and how a subsequence re-analysis of
the research corpus found significant use of the technique in commercial
software, malware, and by at least one computer criminal.

Simson L. Garfinkel is an Associate Professor at the Naval Postgraduate
School. Based in Arlington VA, Garfinkel's research interests include
digital forensics, usable security, data fusion, information policy and
terrorism. He holds six US patents for his computer-related research and
has published dozens of research articles on security and digital forensics.

Garfinkel is the author or co-author of fourteen books on computing. He is
perhaps best known for his book Database Nation: The Death of Privacy in
the 21st Century. Garfinkel's most successful book, Practical UNIX and
Internet Security (co-authored with Gene Spafford), has sold more than
250,000 copies and been translated into more than a dozen languages since
the first edition was published in 1991.

Garfinkel received three Bachelor of Science degrees from MIT in 1987, a
Master's of Science in Journalism from Columbia University in 1988, and a
Ph.D. in Computer Science from MIT in 2005.

Sharon Goldberg
Computer Science, Boston University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20131022/63cd2693/attachment.html>

More information about the Busec mailing list