Date:  14:0014:40, Monday, March 23, 2009 
Venue:  FIT Building 1315, Tsinghua University 
Title:  Graph Colorings and Secure Computation over NonAbelian Groups.

Speaker:  Christophe Tartary 
Biography: 
Christophe Tartary got his PhD in Computer Science in 2007 from Macquarie University (Australia). His thesis was about the design of provably secure cryptographic protocols for multicast authentication. From August 2007 to February 2009, he held a joint research fellowship between the Division of Mathematical Science at Nanyang Technological University (Singapore) and ITCS where he studied protocols for secure multiparty computation. Since February 2009, he is a postdoctoral researcher at ITCS. His main research interests are multiparty computation, multicast authentication and theoretical computer science.

Abstract: 
We study the problem of computing the nproduct function fG(x1, . . . , xn) = x1 •x2 • x3 • • • xn in an arbitrary finite group (G, •) in the passive and information theoretically securemodel where the input of party Pi is xi ∈ G for i = 1, . . . , n. We are interested in protocols for fG which require only blackbox access to the group G (i.e. the only computations performed by the n players during the execution of the protocol are a group operation, a group inverse, or sampling a uniformly random group element). First, we show that if (G, •) is nonAbelian and n ≥ 4, then no ⌈n2 ⌉private protocol for computing fG exists. Second, we present two deterministic tsecure protocols for computing fG. The first construction is optimal (i.e. it works for any t ≤ ⌈n2 ⌉−1) but its communication cost is exponential in t. The second scheme requires polynomial communication cost provided that t ∈ O(n1−ǫ) for any positive constant value ǫ. Third, we show that one can design a probabilistic tsecure protocol to compute fG having polynomial communication cost provided that t ≤ n2+ǫ (for any positive constant ǫ).
This presentation resumes an ongoing work with Yvo Desmedt, Josef Pieprzyk, Ron Steinfeld, Xiaoming Sun, Huaxiong Wang and Andrew ChiChih Yao. The related publications appeared at Crypto’07 (Y. Desmedt, J. Pieprzyk, R. Steinfeld and H. Wang: On Secure MultiParty Computation in Blackbox Groups) and Asiacrypt’08 (X. Sun, A. C.C. Yao and C. Tartary: Graph Design for Secure Multiparty Computation over NonAbelian Groups).
