In this post, I present a high level overview and context for “A Minimal Model for Secure Computation”, a paper on multiparty computation published by Uri Feige, Joe Kilian, and Moni Naor in 1994.
The problem the paper is trying to tackle is secure two-party computation, in which two parties, Alice and Bob, try to compute some function \(f(x, y)\) where Alice provides the input \(x\), and Bob provides the input \(y\). However, they wish to do it in a way where they do not reveal to each other what their respective values are. One of the key developements for this problem is Andrew Yao’s garbled circuit construction, first described in 1986, which gives a computationally secure two-party computation protocol under the assumption that oblivious transfer is possible.
Feige, Kilian, and Naor are interested in understanding secure two-party computation in an information-theoretically secure (as opposed to computationally secure) setting. The paper begins by referring to a 1989 result by Chor and Kushilevitz showing that it is actually impossible to do in an information-theoretically secure way except for Boolean functions of the form \(f(x, y)=f_a(x) \oplus f_b(y)\). Feige, Kilian, and Naor subvert this impossibility result by introducing a “minimal” extension to the setup. They allow for a semi-honest third party, Carol, to participate in the protocol so that Alice and Bob, instead of sending messages to each other, can send messages to Carol and have Carol compute \(f(x,y)\). This all happens without Alice or Bob having to reveal their inputs.
The paper first shows how it is possible to compute any function with information-theoretic security, but with communication cost that is exponential in the size of the inputs to the function.
The paper then goes on to examine how it is possible to compute certain functions with information-theoretic security, with polynomial communication cost. The first case the authors look into is that of group products, where for some finite group \(G\), Alice and Bob each provide \(n\) values \(x=(g_1,\dots,g_n)\) and \(y=(g_{n+1},\dots,g_{2n})\) respectively, and they jointly try to compute \(f(x,y)=g_{k_1}g_{k_2}\dots g_{k_m}\) with each \(k_i \in [1..2n]\). The second case the authors look into is computing functions that can be determined in nondeterministic logspace. The problem of computing such a function can be reduced that of \(st\)-connectivity, through the classical result involving converting the possible Turing machine states into vertices and adding edges based off of legal single Turing machine step transitions. Since the structure of the graph would be dependent on the inputs of Alice and Bob to the function, the authors then show how it is possible to resolve \(st\)-connectivity in the minimal extension setting without giving away the graph’s structure through multiplication of matrices over a finite group, referring back to the first case of group products.
Finally, the authors point out that with a semi-honest third party Carol, computationally secure two-party computation can be done using garbled circuits without oblivious transfer, and give a lower bound result on the communication of any protocol involving the minimal extension. The lower bound result draws heavily from graph theory, surprisingly reducing the security of the protocol to properties of graph embeddings.
Written on September 18th, 2020 by Alex Miao