Youming Qiao and Christophe Tartary
Abstract
In their Crypto'07 paper, Desmedt, Pieprzyk, Steinfeld and Wang studied the problem of achieving secure 
-party computation over non-Abelian groups. The function to be computed is 
where each participant 
holds an input 
from the non-commutative group 
. The settings of their study are the passive adversary model, information-theoretic security and black-box group operations over .
They presented three results. The first one is that honest majority is needed to ensure security when computing 
. Second, when the number of adversary 
, they reduced building such a secure protocol to a graph coloring problem and they showed that there exists a deterministic secure protocol computing using exponential communication complexity. Finally, Desmedt et al. turned to analyze random coloring of a graph to show the existence of a probabilistic protocol with polynomial complexity when 
, in which 
is a constant less than 2.948.
We call their analysis method of random coloring the counting method as it is based on the counting of the number of a specific type of random walks. This method is inspiring because, as far as we know, it is the first instance in which the theory of self-avoiding walk appears in multiparty computation.
In this paper, we first give an altered exposition of their proof. This modification will allow us to adapt this method to a different lattice and reduce the communication complexity by 1/3, which is an important saving for practical implementations of the protocols. We also show the limitation of the counting method by presenting a lower bound for this technique. In particular, we will deduce that this approach would not achieve the optimal collusion resistance 
.
Publication Details: In Proceedings of CANS 2008. Lecture Notes in Computer Science, vol. 5339, pp 162 - 177, Springer - Verlag.
Download: pdf
Back to the list of publications (research area).