GTACS @ IDC (January 2017)

 

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!

 

 

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

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

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 AC⁰. 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.