Output details

Graph Coloring Applied to Secure Computation in Non-Abelian Groups

<18> Barrington (1986) states that if securely computing over the symmetric group S5 could be done, then any computable functionality F could be securely evaluated. When combining our result with Barrington’s, our work leads to a generic solution for any multiparty functionality F. This work overcomes the main issue of existing generic solutions as the complexity of our protocols is independent from the size of the Boolean circuit used for F. The idea of reducing the original multiparty computation problem to an existential colouring question over planar graphs opens new research directions to design efficient security algorithms.