There Is Always an Exception: Controlling Partial Information Leakage in Secure Computation

Private Function Evaluation (PFE) enables two parties to jointly execute a computation such that one of them provides the input while the other chooses the function to compute. According to the traditional security requirements, a PFE protocol should leak no more information, neither about the function nor the input, than what is revealed by the output of the computation. Existing PFE protocols inherently restrict the scope of computable functions to a certain function class with given output size, thus ruling out the direct evaluation of such problematic functions as the identity map, which would entirely undermine the input privacy requirement. We observe that when not only the input x is confidential but certain partial information g(x) of it as well, standard PFE fails to provide meaningful input privacy if g and the function f to be computed fall into the same function class.

Our work investigates the question whether it is possible to achieve a reasonable level of input and function privacy simultaneously even in the above cases. We propose the notion of Controlled PFE (CPFE) with different flavours of security and answer the question affirmatively by showing simple, generic realizations of the new notions. Our main construction, based on functional encryption (FE), also enjoys strong reusability properties enabling, e.g. fast computation of the same function on different inputs. To demonstrate the applicability of our approach, we show a concrete instantiation of the FE-based protocol for inner product computation that enables secure statistical analysis (and more) under the standard Decisional Diffie–Hellman assumption.

1. 1.

   E.g. multiplying the data vector with a position vector (that is non-zero in all positions representing locations close to the user – possibly containing weights depending on the distance – and zero otherwise) can give useful information.

2. 2.

   In FE schemes, the control over the computable functions is in the hand of the master secret key holder, so this is not an issue unlike in PFE.

3. 3.

   Depending on \(\mathcal {F}\) and the sampling of the dummy functions, communication cost of transferring the function descriptions can be reduced. In [14] we describe such optimizations for the inner product function class.

4. 4.

   We note that while our implementation is only a proof of concept without any code level optimization, ABY has a very efficient and parallelizable implementation.

5. 5.

   It means that (3)–(4) of Step II., and Step III. are repeated until the input data changes at the end of the period.

Authors and Affiliations

1. Laboratory of Cryptography and Systems Security (CrySyS), Department of Networked Systems and Services, Budapest University of Technology and Economics, Budapest, Hungary

   Máté Horváth, Levente Buttyán, Gábor Székely & Dóra Neubrandt

Corresponding author

Correspondence to Máté Horváth .

Editors and Affiliations

1. Hanyang University, Seoul, Korea (Republic of)

   Jae Hong Seo

Appendix

1.1 A Simulation Security of Functional Encryption

For completeness we recall the simulation security of FE as defined in [13].

Definition 3

(q-NA-SIM and q-AD-SIM Security of FE). Let \(\mathcal {FE}\) be a functional encryption scheme for a circuit family \(\mathcal {C} = \{\mathcal {C}_{\nu } : \mathcal {X}_{\nu } \rightarrow \mathcal {Y}_{\nu }\}_{\nu \in \mathbb {N}}\). For every PPT adversary and a PPT simulator \(\mathcal {S}= (\mathcal {S}_1, \mathcal {S}_2) \) consider the following two experiments:

We distinguish between two cases of the above experiment:

1. 1.

   The adaptive case, where:

   • the oracle \(O(\mathsf {msk_{FE}}, \cdot ) = \mathsf {FE.KeyGen}(\mathsf {msk_{FE}},\cdot )\) and

   • the oracle \(O'(\mathsf {msk_{FE}}, \mathsf {st}', \cdot )\) is the second stage of the simulator, namely \(\mathcal {S}_2^{U_x(\cdot )}(\mathsf {msk_{FE}}, \mathsf {st}', \cdot )\) where \(U_x(C) = C(x)\) for any \(C \in \mathcal {C}_\nu \).

   The simulator algorithm \(\mathcal {S}_2\) is stateful in that after each invocation, it updates the state \(\mathsf {st}'\) which is carried over to its next invocation. We call a simulator algorithm \(\mathcal {S}= (\mathcal {S}_1, \mathcal {S}_2)\) admissible if, on each input C, \(\mathcal {S}_2\) just makes a single query to its oracle \(U_x(\cdot )\) on C itself. The functional encryption scheme \(\mathcal {FE}\) is then said to be q-query-simulation-secure for one message against adaptive adversaries (q-AD-SIM secure for short) if there is an admissible PPT simulator \(\mathcal {S}= (\mathcal {S}_1, \mathcal {S}_2)\) such that for every PPT adversary that makes at most q queries, the following two distributions are computationally indistinguishable:

   
2. 2.

   The non-adaptive case, where the oracles \(O(\mathsf {msk_{FE}},\cdot )\) and \(O'(\mathsf {msk_{FE}},\mathsf {st},\cdot )\) are both the “empty oracles” that return nothing: the functional encryption scheme \(\mathcal {FE}\) is then said to be q-query-simulation-secure for one message against non-adaptive adversaries (q-NA-SIM secure, for short) if there is a PPT simulator \(\mathcal {S}= (\mathcal {S}_1, \bot )\) such that for every PPT adversary that makes at most q queries, the two distributions above are computationally indistinguishable.

As shown by [13, Theorem A.1.], in the non-adaptive setting (that we also use), q-NA-SIM security for one message is equivalent to q-NA-SIM security for many messages.

1.2 B Proof of Theorem 2

We prove Theorem 2, by showing that the protocol of Fig. 5 fulfils the requirements of Definition 2 with the assumption that the underlying FE and OT are SIM secure against semi-honest adversaries. As correctness directly follows from the correctness of the underlying FE and OT, we turn our attention towards the security requirements. We argue input and weak relaxed function privacy by showing that the view of both parties can be simulated (without having access to the inputs of the other party) using the simulators guaranteed by the SIM security of FE and OT.

Corrupted \(P_1\) : Weak Relaxed Function Privacy. Besides its input and output, the view of \(P_1\) consists of the received OT messages and the function query \(\mathcal {F}_{R}\). Simulation becomes trivial because of the fact that the output of \(P_1\) also contains \(\mathcal {F}_{R}\). Thus \(\mathcal {S}_{P_1}((x_1,\ldots ,x_d), \mathcal {F}_{R})\) can return \(\mathcal {F}_{R}\) and the output of the sender’s simulator \(\mathcal {S}^{\mathcal {S}}_{OT}\) guaranteed by the SIM security of OT. The simulated view is clearly indistinguishable from the real one.

Corrupted \(P_2\) : Input Privacy. The following simulator \(\mathcal {S}_{P_2}\) simulates the view of a corrupt \(P_2\), that consists of its input \((f_1, \ldots , f_k)\), output \(\lbrace y'^*_{i,j}=f'_i(x_j) \rbrace _{i\in [k],j\in [d]}\), the used randomness and the incoming messages. \(\mathcal {S}_{P_2}\) first determines the index set \(I^*=\lbrace i \mid \exists j: y'_{i,j} \ne \bot \rbrace \subseteq [k]\). Next, it sets up the parameters of the ideal experiment according to Definition 3. To do so, it samples and then for all \({i\in I^*}\) generates keys . For the simulation of the FE ciphertexts (corresponding to unknown messages), we can use the FE simulator \(\mathcal {S}_{FE}\) for many messages (implied by one-message q-NA-SIM security [13]). Thus \(\mathcal {S}_{FE}(\mathsf {pp_{FE}}^*, \lbrace y_{i,j}=f_i(x_j), f_i, \mathsf {fsk}_{f_{i}}^* \rbrace _{i\in I^*,j\in [d]}, \lambda ) = (\mathsf {ct}_1^*, \ldots , \mathsf {ct}_d^*)\) can be appended to the simulated view together with \(\mathsf {pp_{FE}}^*\). The incoming messages of Step III. are simulated using the OT simulator \(\mathcal {S}_{OT}^{\mathcal {R}}\) for the receiver. Finally the output of \(\mathcal {S}_{OT}^{\mathcal {R}}(\lambda , \lbrace \mathsf {fsk}_{f_{i}}^* \rbrace _{i\in I^*}\cup \lbrace \bot _i \rbrace _{i\in [k]\setminus I^*})\) is appended to the simulated view.

Now we show the indistinguishability of the real and simulated views. As the inputs and outputs are the same in both cases, we have to compare the randomness and the incoming messages. First notice that \(\mathsf {pp_{FE}}\) and \(\mathsf {pp_{FE}}^*\) are generated with different random choices. At the same time, these cannot be told apart as otherwise the choices were not random. The rest of the incoming messages depend on these parameters. Observe that \(I^* = I \cap [k]\). The security of the used FE scheme guarantees that \((\mathsf {ct}_1^*,\ldots ,\mathsf {ct}_d^*)\) even together with functional keys \(\lbrace \mathsf {fsk}_{f_{i}}^* \rbrace _{i\in I^*}\) are indistinguishable from \((\mathsf {ct}_1,\ldots ,\mathsf {ct}_d)\) with \(\lbrace \mathsf {fsk}_{f_{i}} \rbrace _{i\in I \cap [k]}\). Finally, the security of the OT simulation guarantees that \((\mathsf {msg_{1}^{OT}},\ldots ,\mathsf {msg_{\kappa }^{OT}})\) and \((\mathsf {msg_{1}^{OT}}^*,\ldots ,\mathsf {msg_{\kappa }^{OT}}^*)\) are indistinguishable. This also implies that functional keys for the same functions (with respect to either \(\mathsf {pp_{FE}}\) or \(\mathsf {pp_{FE}}^*\)) can be obtained both from the real and simulated OT messages. In other words, FE ciphertexts and functional keys are consistent in both cases (i.e. they allow one to obtain the same decryption outputs) due to the correctness of the FE simulation, which concludes our proof.    \(\square \)

Reprints and permissions

© 2020 Springer Nature Switzerland AG

Policies and ethics