Secure Multi-party Computation for Non-abelian Group

Since quantum computing seems to be powerful for cryptosystems based on abelian groups, Desmedt et al. considered the secure multi-party computation on non-abelian groups. In this talk we first briefly look at the authors' reduction from a secure computation problem to a graph coloring problem. Then we adapt the authors' analysis method of the graph coloring problem to a different setting and get a result that saves 1/3 communication complexity. We also give a lower bound for this method. Finally we will have a look at a new analysis method that achieves optimal result.