2
$\begingroup$

non-interactive secure computation (NISC) (introduced by this paper, followed by others) is a variant of secure 2PC/MPC defined as the following setting:

Alice publishes an encrypted version of f(*, y), such that Bob or anyone else who knows some x can construct a message m that reveals f(x, y) to Alice (without requiring any other interaction with Alice).

However, in the current proposals Bob would not be able to learn f(x, y) without the help of Alice, if I understand correctly. But that's exactly what I want. In contrast to the NISC literature, neither Bob's privacy of x nor that of f(x, y) is important to me. Just the privacy of y is important. Does anyone know if this is possible/already proposed somewhere?

$\endgroup$
2
  • $\begingroup$ Are you asking for Alice to send a single message, so that Bob learns $f(x,y)$ without sending anything himself? $\endgroup$
    – Mikero
    Jun 23, 2021 at 6:38
  • $\begingroup$ Yes! Sorry for not being clear right away $\endgroup$ Jun 28, 2021 at 14:49

1 Answer 1

3
$\begingroup$

If Alice is the only person to speak, but Bob can learn output, then the protocol must leak more than just $f(x,y)$. See:

Halevi, Lindell, Pinkas: Secure Computation on the Web: Computing without Simultaneous Interaction

Essentially, Bob can choose many different $y_i$ values and re-run the protocol to learn many different $f(x,y_i)$ outputs. Since Bob never speaks in the protocol, he can do all this "in his head", without Alice's involvement. So the best you can hope for is that the protocol leaks no more to Bob than an oracle for the residual function $f(x,\cdot)$.

For some functions $f$, achieving this "best possible" leakage is impossible. Theorem 2.3 of the paper has an example (in which $f$ is a pseudorandom function and $x$ is its seed). For other functions, "best possible" leakage is equivalent to just giving out $x$ in the clear. So it's not always clear what you can get from this limited-interaction model.

$\endgroup$
3
  • $\begingroup$ Thank you, that's very helpful! I think you mixed up x and y relative to my original post, right? $\endgroup$ Jun 29, 2021 at 18:41
  • $\begingroup$ My setting (using my original notation): x is a message, y is a symmetric encryption key, and f(x,y) is the symmetrically encrypted message. Alice publishes f(.,y). It's fine that Bob can encrypt multiple different x_i. It's also fine is this eventually leaks y, as long as it would take more than say 1h for the public to find y given f(.,y). (I want to retrofit a protocol on top of TLS - akin to TLSNotary - in which Bob can prove to the public that he received a symmetrically encypted message from the server before knowing y. this wouldn't yet solve my problem, but be a big step towards it) $\endgroup$ Jun 29, 2021 at 18:56
  • $\begingroup$ The paper you suggested is great and on point, I have to mark this as the accepted answer. Thanks! $\endgroup$ Jun 29, 2021 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.