non-interactive secure computation with a twist?

Jonas Metzger

10/23/22, 4:31 AM

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?

1 + 2

multiparty-computation

zero-knowledge-proofs

Mikero

10/23/22, 6:38 AM

Are you asking for Alice to send a single message, so that Bob learns $f(x,y)$ without sending anything himself?

Jonas Metzger

10/28/22, 2:49 PM

Yes! Sorry for not being clear right away

Score:3

Crypto

Mikero

10/28/22, 3:50 PM

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.

0 + 3

Jonas Metzger

10/29/22, 6:41 PM

Thank you, that's very helpful! I think you mixed up x and y relative to my original post, right?

Jonas Metzger

10/29/22, 6:56 PM

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)

Jonas Metzger

10/29/22, 9:37 PM

The paper you suggested is great and on point, I have to mark this as the accepted answer. Thanks!