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 majordomometzdowd.com
about | contact Other archives ( Real Estate discussion Medical topics )
Mailing lists
Newsgroups
RFC archive
metzdowd.com