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

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?

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.

• I think you should explain that these constructions are only secure in the "honest-but-curious" model, which is an odd kind of threat model where we are worried about a malicious adversary but we somehow don't believe the adversary will do anything too malicious. Needless to say this often doesn't match up to what adversaries can actually do in the real world, so we often need something that's secure in "the malicious model".
– D.W.
Commented Sep 15, 2015 at 9:31
• The classical garbled circuits approach does not extend readily to malicious security. The universal circuits approach does easily. The PFE protocols of Mohassel/Sadeghian include a malicious-secure one. The algebraic approaches are not specific enough to say for sure! Commented Sep 15, 2015 at 15:35