Applying Recreational Mathematics to Secure Multiparty Computation

[Hal Finney]

Saqib Ali writes:
> This is interesting:
> http://tinyurl.com/2zko7n
>
> Abstract
> The problem of a mice traveling through a maze is well known....
>
> The problem finds its origin in the problem of secure multiparty computation....

This was presented at Crypto this year. It was interesting that they were
able to reduce this secure MPC problem to a very concrete graph coloring
question. However they did not include the motivating example about the
doctor visit, and just presented it in terms of MPC over non-abelian
groups. I had the impression at the time that it was a pretty abstract
problem. It's not clear to me how the doctor problem can be expressed
as a non-abelian group operation.

The one thing I understood from the talk is that the abelian group case
(commutative and associative) is trivial. You want to do Z = X op Y, so
you break X up into shares such that X = X1 op X2 op ... Xn and the same
for Y1..Yn. Then the first guy does Z1 = X1 op Y1, and so on, and they
all combine their results: Z = Z1 op Z2 op ... Zn. This trivially gets
the right answer, but it doesn't work with non-abelian groups because
you can't rearrange the terms. So they build a graph that shows how
shares get joined, and that eventually leads to their coloring problem.

Hal Finney

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com