We study the problem of computing the n-product 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 black-box 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 non-Abelian and n ≥ 4, then no ⌈n2 ⌉-private protocol for computing fG exists. Second, we present two deterministic t-secure 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 t-secure 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 Chi-Chih Yao. The related publications appeared at Crypto’07 (Y. Desmedt, J. Pieprzyk, R. Steinfeld and H. Wang: On Secure Multi-Party Computation in Black-box Groups) and Asiacrypt’08 (X. Sun, A. C.-C. Yao and C. Tartary: Graph Design for Secure Multiparty Computation over Non-Abelian Groups).

Date:	14:00-14:40, Monday, March 23, 2009

Venue:	FIT Building 1-315, Tsinghua University

Title:	Graph Colorings and Secure Computation over Non-Abelian 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 n-product 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 black-box 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 non-Abelian and n ≥ 4, then no ⌈n2 ⌉-private protocol for computing fG exists. Second, we present two deterministic t-secure 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 t-secure 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 Chi-Chih Yao. The related publications appeared at Crypto’07 (Y. Desmedt, J. Pieprzyk, R. Steinfeld and H. Wang: On Secure Multi-Party Computation in Black-box Groups) and Asiacrypt’08 (X. Sun, A. C.-C. Yao and C. Tartary: Graph Design for Secure Multiparty Computation over Non-Abelian Groups).