Revealing Additional Information in Two-Party Computations

Andreas Jakoby

Abstract. A two-argument function is computed privately by two parties if after the computation, no party should know anything about the other inputs except for what he is able to deduce from his own input and the function value. In [1] Bar-Yehuda, Chor, Kushilevitz, and Orlitsky give a complete characterisation of two-argument functions which can be computed privately (in the information-theoretical sense) in the Honest-But-Curious model and study protocols for “non-private ” functions revealing as little information about the inputs as possible. The authors define a measure which determines for any function f the additional information E(f) required for computing f and claim that f is privately-computable if and only if E(f) = 0. In our paper we show that the characterisation is false: we give a privately-computable function f with E(f) = 0 and another function g with E(g) =0thatisnot privately-computable. Moreover, we show some rather unexpected and strange properties of the measure for additional information given by Bar-Yehuda et al. and we introduce an alternative measure. We show that for this new measure the minimal leakage of information of randomized and deterministic protocols are equal. Finally, we present some general relations between the information gain of an optimal protocol and the communication complexity of a function. 1

Stanisław Jarecki

Patrick J. Coles, Li Yu, Vlad Gheorghiu +1 more

Wilko Henecka, Stefan K ögl, Ahmad‐Reza Sadeghi +2 more

Secure two-party computation allows two untrusting parties to jointly compute an arbitrary function on their respective private inputs while revealing no information beyond the outcome. Existing cryptographic compilers can automatically generate secure computation protocols from high-level specifications, but are often limited in their use and efficiency of generated protocols as they are based on either garbled circuits or (additively) homomorphic encryption only.

Dominique Unruh

Reuven Bar-Yehuda, Benny Chor, Eyal Kushilevitz Z +1 more

Two parties, each holding one input of a two-variable function, communicate in order to determine the value of the function. Each party wants to expose as little of its input as possible to the other party. The authors prove tight bounds on the minimum amount of information about the individual inputs that must be revealed in the computation of most functions and of some specific ones. They also show that a computation that reveals little information about the individual inputs may require many more message exchanges than a more revealing computation.>