[Busec] BUsec this week: Huijia Rachel Lin (Monday 10AM)

Sharon Goldberg goldbe at cs.bu.edu
Sun Nov 18 23:27:07 EST 2012


We are back to our regularly scheduled seminars for the next two weeks.

Tomorrow (Monday) 10AM, our own Huijia Rachel Lin will tell us about
constant round concurrent zero knowledge.  The following week, we will
have Aggelos Kiayias, from U Athens, visiting us and speaking at the

See you then,

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


Constant-Round Concurrent Zero Knowledge From Falsifiable Assumptions
Speaker: Huijia Rachel Lin (MIT/BU)
Nov 19, 10-11:30 AM
MCS 137, 111 Cummington St, Boston MA

We present a constant-round concurrent zero-knowledge protocol for
NP. Our protocol is sound against uniform polynomial-time attackers,
and relies on the existence of families of collision-resistant
hash functions, and a new (but in our eyes, natural) falsifiable
intractability assumption: Roughly speaking, that Micali's
non-interactive CS-proofs are sound for languages in P.

Resource-based Corruptions and the Combinatorics of Hidden Diversity
Aggelos Kiayias (U. Athens & U. Connecticut)
Monday Nov 26, 10AM

Abstract. In the setting of cryptographic protocols, the corruption of
a party has traditionally been viewed as a simple, uniform and atomic
operation, where the adversary decides to get control over a party and
this party immediately gets corrupted. In this paper, motivated by the
fact that different players may require different resources to get
corrupted, we put forth the notion of resource-based corruptions,
where the adversary must invest some resources in order to corrupt

If the adversary has full information about the system configuration
then resource-based corruptions would provide no fundamental
difference from the standard corruption model. However, in a resource
“anonymous” setting, in the sense that such configuration is hidden
from the adversary, much is to be gained in terms of efficiency and

We showcase the power of such hidden diversity in the context of
secure multiparty computation (MPC) with resource-based corruptions
and prove that it can effectively be used to circumvent known
impossibility results. Specifically, if OPT is the corruption budget
that violates the completeness of MPC (the case when half or more of
the players are corrupted), we show that if hidden diversity is
available, the completeness of MPC can be made to hold against an
adversary with as much as a B · OPT budget, for any constant B > 1.
This result requires a suitable choice of parameters (in terms of
number of players and their hardness to corrupt), which we provide and
further prove other tight variants of the result when the said choice
is not available. Regarding efficiency gains, we show that hidden
diversity can be used to force the corruption threshold to drop from
1/2 to 1/3, in turn allowing the use of much more efficient
(information-theoretic) MPC protocols.

Among others, the talk will go into details regarding the modeling of
the corruption process, the abstraction of the corruption game as a
combinatorial problem, and the formalization
of the properties of inversion effort preserving functions and
hardness indistinguishability that are needed to model hidden
diversity in the setting of computational corruptions.

Joint work with Juan Garay, David Johnson, Moti Yung.

More information about the Busec mailing list