Join Log in
Score:2
Leo avatar Crypto

Secretly compute multiplication of two numbers owned by two people

br flag
Leo

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!

144
0 + 0
Score:1
knaccc avatar Crypto
es flag
knaccc

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.

0 + 0
Score:1
Geoffroy Couteau avatar Crypto
cn flag
Geoffroy Couteau

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.

0 + 0
Geoffroy Couteau avatar
cn flag
Geoffroy Couteau
You're right, I should have checked what I wrote before sending. I removed the first solution and replaced it with the second. Thanks!
0
Reply
knaccc avatar
es flag
knaccc
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?
0
Reply
Geoffroy Couteau avatar
cn flag
Geoffroy Couteau
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)
0
Reply
Geoffroy Couteau avatar
cn flag
Geoffroy Couteau
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](https://ieeexplore.ieee.org/document/892118) 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).
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.