2
$\begingroup$

For example, Alice and Bob have two numbers $a$ and $b$, respectively. They want to calculate the multiplication $a\cdot b$ without Alice knowing $b$ or Bob knowing $a$ and send this multiplication $a\cdot b$ to Carol. Carol will use this $a\cdot b$ to do further application. Carol will not collude with Alice or Bob. Are there any ways and libraries/tools in Golang to achieve this? Thank you!

$\endgroup$

2 Answers 2

1
$\begingroup$

A solution without assuming that $a$ and $b$ are nonzero, and without having to compute multiplicative inverses, which also involves no communication between Alice and Bob, beyond having a prior agreement on a common random string (this is known as the "private simultaneous message" model):

Alice and Bob agree on $r,s,t$ (three random numbers). Alice sends $c = a+r, c' = c\cdot s + t$ to Carol, and Bob sends $d = b+s, d' = b\cdot r - t$ to Carol. Carol computes $c\cdot d - (c' + d')$.

Here, the sum can be done modulo $n$, where $n$ is a public upper bound on $a$ and $b$, and "random" means a uniformly random element of $\mathbb{Z}/n\mathbb{Z}$.

Note: the key point in your question is the assumption that Carol will not collude with Alice and Bob. It is a classical result that secure computation does not require any cryptography or computational assumptions as soon as the number of parties that can collude is strictly below half of the total number, which is the case here. Hence, you won't be needing special libraries/tools in Golang, beyond basic arithmetic.

$\endgroup$
4
  • $\begingroup$ You're right, I should have checked what I wrote before sending. I removed the first solution and replaced it with the second. Thanks! $\endgroup$ Apr 30, 2022 at 11:39
  • $\begingroup$ Btw are you saying that the same $(r,s,t)$ trio can be re-used without compromising the security of the scheme? This looks like a really useful technique - are variants of it used in any practical applications you're aware of? $\endgroup$
    – knaccc
    Apr 30, 2022 at 12:01
  • $\begingroup$ No, $r,s,t$ cannot be reused: for example, if $r$ is reused with a new $a'$, Carol would learn $a-a'$. However, the common approach here is is to use pseudorandomness: Alice and Bob only agree on a short seed, and expand it into an arbitrary amount of triples $(r_i,s_i,t_i)$ upon need, on the fly, without using further interaction (e.g. using a pseudorandom function) $\endgroup$ Apr 30, 2022 at 13:27
  • 1
    $\begingroup$ The scheme I described is in essence a randomized encoding for the product function. Randomized encodings have many powerful applications in cryptography (see this paper and its many follow ups). The technique is fairly practical and could easily be used in real-world applications, though I'm not aware of any concrete practical application using them (if I had to bet, I would still bet that some practical applications use this technique). $\endgroup$ Apr 30, 2022 at 13:30
1
$\begingroup$

I'm assuming that your numbers are integers greater than zero and less than $n$.

Alice picks a uniformly random blinding factor $k$ where $0<k<n$, and sends $k\cdot a$ to Bob and $k$ to Carol. Bob sends $k\cdot a\cdot b$ to Carol. Carol calculates $a\cdot b=k^{-1}\cdot k\cdot a\cdot b$.

All operations need to be done $mod\ n$. The product $a\cdot b$ must be less than $n$, unless you are dealing with scalars/private keys, where it does not matter if Carol derives the product $mod\ n$.

$k^{-1}$ means the modular multiplicative inverse of $k$. Therefore you should ensure your choice of $n$ is prime.

Depending on your application, you may be using these numbers as private keys, in which case you should pick $n$ such that it is the prime group order of your generator. E.g. for Curve25519 or Ed25519 use the order specified in rfc 7748, or use the $q$ value stated for a MODP group in rfc 5114.

$\endgroup$

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.