1
$\begingroup$

Let's say that I have a plain computational process that consists of several divisions and I do not want to do it with non-interactive homomorphic encryption.

I would like to ask how can I call this process: Until a division, I do the computations non-interactively. When I face with division operation, here comes interactivity. I should send encrypted numerator and denominator to a party and get the division result back. This second party should not learn the contents of numerator and denominator.

Since I cannot call the process, I cannot find papers to read. I want to use this kind of solution, but I am new to homomorphic encryption. I have experience with non-interactive homomorphic encryption. But I would like to get experience on this interactive one.

I have no idea which scheme I can use and how to implement this. Do I need garbled circuits for this?

Improve this question
$\endgroup$
8
  • $\begingroup$ How is what you want different from Secure multi-party computation? $\endgroup$
    – abacabadabacaba
    Commented Nov 17, 2018 at 22:09
  • $\begingroup$ In my case, both parties do not have input. Party A, when it gets stuck with a computation just sends it to Party B. And, Party B sends the result of this particular computation to Party A. $\endgroup$
    – dilot
    Commented Nov 18, 2018 at 15:03
  • 1
    $\begingroup$ Why can't Party A perform the computation by itself? If this is because Party B knows something that Party A doesn't, why can't Party B share this information with Party A? $\endgroup$
    – abacabadabacaba
    Commented Nov 18, 2018 at 16:00
  • 1
    $\begingroup$ I think the term you're looking for is "reactive functionality". Multiparty computation is often framed as parties having decided the function in advance and with all of their inputs ready at the start of the protocol... but some MPC protocols are reactive, meaning parties may choose step-by-step which inputs to share and which functions to perform. $\endgroup$
    – kiwidrew
    Commented Nov 18, 2018 at 16:32
  • $\begingroup$ No no. Let's say that Party A has c1 and c2 and wants to compute (c1+c2)/(c1*c2). Addition and multiplication are easy with homomorphic encryption schemes. But for division, I would use approximation function and this means lots of multiplications. So, requires lots of time. For this reason, I want to send (c1+c2) and (c1*c2) to Party B. I may use blinding. Then, Party B decrypts these two inputs, performs the division and sends the result back after encrypting. Party B learns anything, Party A gets the division result pretty fast. $\endgroup$
    – dilot
    Commented Nov 18, 2018 at 16:33

1 Answer 1

Reset to default
1
$\begingroup$

This can be seen as a particular case of secure two-party computation, where one party has the (encrypted) inputs, and the other has the decryption key. There is no specific name for the functionality you are looking for, as it is just a particular functionality that one can want to realize in the framework of two-party computation.

So, I think you're looking for a two-party computation protocol realizing the following functionality:

Alice has input $E(a),E(b)$, where $E$ is some encryption scheme (I guess that in the scenario you have in mind, it's an FHE), and Bob has the decryption key of this FHE scheme. You want to realize the functionality that returns $E(a/b)$ to Alice, and nothing to Bob.

(note that even a perfectly secure realization of this functionality will at least leak whether $b = 0$, so you have to make sure this is not an issue for you in the larger protocol you want to use this subprotocol in).

As for how to implement it: if you're using an FHE scheme and just want to avoid doing the expensive division, it's super easy. Just let Alice homomorphically multiply $b$ by some $r$, and randomize the ciphertext: she gets $E(rb)$ and sends that to Bob. Bob decrypts, gets $rb$, computes $(rb)^{-1}$, encrypts, sends back. Alice gets $E((rb)^{-1})$, and homomorphically multiplies with $r$ and $E(a)$ to get $E(a\cdot b^{-1})$.

I suspect from your comments, however, that you are interested in approximate division of floats, and not just computation of $E(a\cdot b^{-1})$. Is it the case? If so, you will likely need a much more complex and interactive protocol.

Improve this answer
$\endgroup$
0

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.