GTACS @ IDC (January 2017)

Primary tabs

IDC HerzliyaERC Logo

The first GTACS of the new year will be at IDC Herzliya, Tue, Jan 24 at the Efi Arazi School of Computer Science



09:00-09:30      Coffee & Registration

09:30-10:30      Amos BeimelAd Hoc PSM Protocols: Secure Computation without Coordination 

10:30-11:00      Coffee break

11:00-12:00      Chris Williamson, Bounded Indistinguishability and the Complexity of Recovering Secrets

12:00-13:30      Lunch

13:30-14:00      Rant Session

14:00-14:30      Coffee break / reviewer responses

14:30-15:30      Aner Moshe Ben EfraimOptimizing Semi-Honest Secure Multiparty Computation for the Internet





In addition to standard presentations, we will host a rump session with brief announcements of recent and upcoming results. In honor of Eurocrypt notifications, we've given it a more appropriate name...
 - min{3 slides, 5min} per speaker (per result)
 - Precedence given to announcements with humor and/or rants
 - All presentations must include at least one duck
Email Elette by Thurs Jan 19 to submit your rant!

Amos Beimel, Ben-Gurion University

Ad-Hoc PSM Protocols: Secure Computation without Coordination


In ad hoc secure computation there are n parties that may potentially 
participate in a protocol but, at the actual time of execution, only k of them,
whose identity is not known in advance, actually participate. This situation 
is particularly challenging in the PSM setting, where the protocols
are non-interactive (a single message from each participating party to
a special output party) and where the parties rely on pre-distributed,
correlated randomness (that in the ad hoc setting will have to take into
account all possible sets of participants).
We present various constructions of upper bounds, with information-
theoretic security, that show that every function f admits such ad hoc
PSM protocol and that, moreover, for functions f for which standard
PSM constructions are efficient, there also exist corresponding ad hoc
PSM protocols that are efficient (essentially, with a loss of O(n) in
the randomness and the communication complexity, compared to much
larger loss of (n choose k) in naive solutions).
We also consider the case where the actual number of participating parties 
t may be larger than the minimal k for which the protocol is designed
to work. In this case, it is unavoidable that the output party will be able
to compute the output corresponding to each subset of k out of the t
participants. Therefore, a "best possible security" notion, requiring that
this will be the only information that the output party learns, is needed.
We present connections of this notion to the previously studied notion
of t-robust PSM (or NIMPC). In the computational case, we show that
constructions with best possible security for even simple functions (like
AND or threshold) can be translated into construction of obfuscation
primitives (such as point function obfuscation and fuzzy point function
obfuscation). We view these results as a negative indication that protocols 
with "best possible security" may be hard to achieve.
Based on a joint work with Yuval Ishai and Eyal Kushilevitz



Chris Williamson, The Chinese University of Hong Kong

Bounded Indistinguishability and the Complexity of Recovering Secrets:


Motivated by cryptographic applications, we study the notion of bounded indistinguishability, a natural relaxation of the well studied notion of bounded independence.

We say that two distributions μ and ν over Σn are k-wise indistinguishable if their projections to any k symbols are identical. We say that a function f : Σn → {0, 1} is ε-fooled by k-wise indistinguishability if f cannot distinguish with advantage ε between any two k-wise indistinguishable distributions μ and ν over Σn.

We are interested in characterizing the class of functions that are fooled by k-wise indistinguishability. While the case of k-wise independence (corresponding to one of the distributions being uniform) is fairly well understood, the more general case remained unexplored.

When Σ = {0, 1}, we observe that whether f is fooled is closely related to its approximate degree. For larger alphabets Σ, we obtain several positive and negative results. Our results imply the first efficient secret sharing schemes with a high secrecy threshold in which the secret can be reconstructed in AC0. More concretely, we show that for every 0 < σ < ρ ≤ 1 it is possible to share a secret among n parties so that any set of fewer than σn parties can learn nothing about the secret, any set of at least ρn parties can reconstruct the secret, and where both the sharing and the reconstruction are done by constant-depth circuits of size poly(n). We present additional cryptographic applications of our results to low-complexity secret sharing, visual secret sharing, leakage-resilient cryptography, and eliminating “selective failure” attacks. 

Joint work with Andrej Bogdanov, Yuval Ishai, and Emanuele Viola.



Aner Ben-Efraim, Ben-Gurion University

Optimizing Semi-Honest Secure Multiparty Computation for the Internet:


We construct highly efficient constant-round protocols for the setting of multi-party computation for semi-honest adversaries. Our protocols work by constructing a multiparty garbled circuit, as proposed in BMR (Beaver et al., STOC 1990). Our first protocol uses oblivious transfer and constitutes the first concretely-efficient constant-round multiparty protocol for the case of no honest majority. Our second protocol uses BGW, and is significantly more efficient than the FairplayMP protocol (Ben-David et al., CCS 2008) that also uses BGW. We ran extensive experimentation comparing our different protocols with each other and with a highly-optimized implementation of semi-honest GMW.




Date and Time: 
Tuesday, January 24, 2017 - 09:00 to Wednesday, January 25, 2017 - 15:45
IDC, Computer Science Building, M.Sc. Lab