A secure function evaluation problem and an alternative of 1 out of n oblivious transfer?

Question

I am considering a "secure function evaluation" problem:

Consider two parties: A and B. A has a one-to-one mapping function $f(x)=k$. Basically, the function $f(x)$ can be regarded as a table of two columns. The first column is the domain of $x$ denoted as $D$. The second column is the range $K$. The party B has a secret input $x_i\in D$. B sends its input $x_i$ to A and A will return the corresponding $k_i$ to B.

The requirement is that A will learn nothing about the input $x_i$ and the output $k_i$. B will learn nothing about the function $f(x)$.

1. For the above problem, a possible solution is the 1-out-of-n oblivious transfer. However, when the size of the domain (or the table) is large. Using oblivious transfer will introduce both heavy computational and communication overhead.

2. Another possible solution I can think about is to model the function as a circuit. And then some techniques such as Garbled circuit may be utilized.

I think the above problem as been considered for a long time in the cryptography community. Any related works or thoughts on this problem will be helpful. Especially, is there an alternative of the 1-out-of n oblivious transfer to increase its efficiency?

Answer 1

The problem is known in the literature as private function evaluation (PFE). A sender has input (a function) $f$; a receiver has input $x$, and only the receiver learns $f(x)$.

• If you are willing to leak the topology of a circuit that computes $f$ (but not the identity of the gates), then using classical garbled circuits / Yao's protocol will work. These garbled circuit constructions are known to hide the gate functionality. You just can't use the latest optimizations in garbled circuits (starting from free-XOR) since they leak which gates compute XOR and which don't.

• If you are willing to leak (an upper bound on) the # of gates in a circuit that computes $f$, then you can do standard SFE of a universal circuit. A universal circuit $U$ takes as input the description of a circuit $C$, and an input $x$, and outputs $U(C,x) = C(x)$. To allow $C$ to have $n$ gates, the size of $U$ must be at least $\Omega(n \log n)$. A construction achieving that size was described by Valiant, but it is apparently a very complicated construction. There is a simpler construction of size $O(n \log^2 n)$ with quite small constants by Kolesnikov & Schneider.

Leslie Valiant: Universal circuits (preliminary report), STOC 1976

Vlad Kolesnikov & Thomas Schneider: A Practical Universal Circuit Construction and Secure Evaluation of Private Functions, Financial Cryptography 2008

• There are some more recent approaches for PFE by Mohassel and Sadeghian that avoid universal circuits and have linear cost $O(n)$. As above, the protocol leaks the number of gates in the circuit computing $f$. I don't know about how these protocols stack up against universal-circuit protocols in practice. Besides the one below, there is also a followup work that achieve active security.

Payman Mohassel & Saaed Sadeghian: How to Hide Circuits in MPC: An Efficient Framework for Private Function Evaluation, Eurocrypt 2013.

• If you are willing to leak the fact that $f$ has some other special algebraic structure (e.g., it is a linear function) then there are certainly ways to exploit the structure for a more efficient solution.

Otherwise, if you are not willing to leak anything about $f$ then there is really nothing you can do better than 1-out-of-$n$ OT. If $f$ can be a totally random mapping, then there is no representation of $f$ that is significantly more concise than its truth table.