[Busec] BUsec this week: Babis Papamanthou (11AM Tues) & Omer Paneth (3PM Friday)
goldbe at cs.bu.edu
Sun Apr 8 11:43:34 EDT 2012
This week, we have Babis Papamanthou from Berkeley speaking at our
usual 11AM on Tuesday seminar, and our own Omer Paneth speaking about
his and Nir Bitansky's TCC best paper at 3PM on Friday at BU's theory
Both talks will be at 111 Cummington St and open to the public, and as
usual, we have lunch on Tuesday.
Publicly Verifiable Delegation of Computation (with I/O Privacy)
Charalampos Papamanthou, UC Berkeley
MCS148, 11AM Tuesday
We study publicly verifiable computation, which generalizes verifiable
computation in the secret key setting and authenticated data
structures. In publicly verifiable computation, a trusted source
outsources an application (algorithm) to an untrusted server. Any
client can ask the server to run the application over some given
inputs, and the server can produce a witness vouching for the
correctness of the outcome.
We propose publicly verifiable computation schemes supporting
expressive manipulations over multivariate polynomials, such as
polynomial evaluation and differentiation. Our scheme allows a client
to verify the outcome in time proportional to the size of the input,
and not depending on the degree and the description of the polynomial,
i.e., in asymptotically less time than performing the computation
locally. Moreover, our scheme allows the source to efficiently update
the polynomial coefficients without performing expensive
recomputations proportional to the size of the polynomial. Finally, we
extend our core scheme to provide input/output privacy (I/O privacy)
on top of verifiability, enabling verifiable data analysis across
clients and in a private way. Applications of verifiable polynomial
operations in finite fields include verifiable statistical
computations and error correcting codes algorithms.
Joint work with Elaine Shi and Roberto Tamassia
Title: From Point Obfuscation To 3-round Zero-Knowledge
Speaker: Omer Paneth, BU
MCS148, 3PM Friday
We construct 3-round proofs and arguments with negligible soundness
error satisfying two relaxed
notions of zero-knowledge: Weak ZK and witness hiding (WH). At the
heart of our constructions
lie new techniques based on point obfuscation with auxiliary input (AIPO).
It is known that such protocols cannot be proven secure using
black-box reductions (or simulation).
Our constructions circumvent these lower bounds, utilizing AIPO (and
extensions) as the
“non-black-box component” in the security reduction. We also
investigate the relation between
AIPO and the assumptions previously used to achieve 3-round ZK.
Joint work with Nir Bitansky.
More information about the Busec