Secure Multiparty Computation without One-way Functions.

We describe protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. One of the new inputs that we offer here is that, in contrast with other proposals, we conceal intermediate results of a computation. For example, when we compute the sum of k numbers, only the final result is known to the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. We also give a protocol, without using a one-way function, for the so-called “mental poker”, i.e., a fair card dealing (and playing) over distance. Finally, we describe a secret sharing scheme where an advantage over Shamir’s and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares (of the secret) owned by any particular player. It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer. In memory of Grigori Mints Part of this research was presented by the first author at the conference “Philosophy, Mathematics, Linguistics: Aspects of Interaction 2012” (PhML-2012), held on May 22–25, 2012 at the Euler International Mathematical Institute. ∗ Research was supported by the RSF grant 16-11-10075. † Research was partially supported by the NSF grant CNS-1117675 and by the ONR (Office of Naval Research) grant N000141512164.

Authors

• Dima Grigoriev
• Vladimir Shpilrain

Keywords

No keywords are indexed for this paper.