8
$\begingroup$

I'm doing a thought experiment:

Alice chooses a number $a$ and Bob $b$. They send $A(a)$ and $B(b)$ to Charlie. He performs $C(A(a), B(b))$ and gets $ab$.

Do there exist not easily reversible functions $A, B, C$ for which the above is true?

I'm a beginner so I'd be all the more grateful if somebody knows :)

Thank you!

$\endgroup$
  • $\begingroup$ I think you are looking for what is called secure multi-party computation in general. I have no idea about whether anything like this has been done before for this particular case. $\endgroup$ – SEJPM Jan 30 '18 at 17:08
  • $\begingroup$ Can you please specify more clearly who is allowed to learn what? Is Charlie only allowed to learn ab? Is Alice only allowed to learn a or can she also learn b? $\endgroup$ – SEJPM Jan 30 '18 at 17:26
  • $\begingroup$ Charlie can only learn ab. What Alice knows doesn't matter, but let's assume she can only know a (and Bob can only know b). $\endgroup$ – Dominik Teiml Jan 30 '18 at 18:05
  • $\begingroup$ Are you specifically restricting communication to one message from Alice and Bob to Charlie each? And do you allow for any previous setup? $\endgroup$ – Maeher Jan 30 '18 at 18:50
  • 1
    $\begingroup$ Ok, I made a mistake then. A and B should not be known (I guess a temporary " random" salt could be used so Charlie doesn't know them) $\endgroup$ – Dominik Teiml Jan 30 '18 at 20:59
7
$\begingroup$

In the way you setup the problem the answer is No.

As Charlie can perform $C(A(1),B(b))$.

| improve this answer | |
$\endgroup$
  • 6
    $\begingroup$ As I read the question, it's not necessary for Charlie to be able to compute the functions A or B. Thus, the generic attack you describe may not work. $\endgroup$ – Ilmari Karonen Jan 30 '18 at 19:02
  • 1
    $\begingroup$ Following kerchoff principal that would require some secret key hidden from Charlie. Probably shared by Alice and Bod. If Alice and Bob share an RSA private key(or negotiate one) the can do unpadded RSA. $\endgroup$ – Meir Maor Jan 30 '18 at 19:14
  • 1
    $\begingroup$ Indeed, if Alice and Bob have no shared secret, then Charlie can simulate Alice and choose a = 1, and your attack will work. So the shared secret is essential. $\endgroup$ – Ilmari Karonen Jan 30 '18 at 19:26
  • $\begingroup$ If I understood @DominikTeiml correctly, he confirmed in the comments that this is indeed the scenario: Communication is restricted to one message from Bob and Alice to Charlie each (So no 2PC) and the functions A and B are publicly known. So the answer seems to be correct. $\endgroup$ – Maeher Jan 30 '18 at 20:15
  • $\begingroup$ @Maeher I guess I described the problem incorrectly than (I was looking for a solution like Daniel's rather than this). I'll think about it tmrw, or somebody can edit the q to make it right (if you know what I mean) $\endgroup$ – Dominik Teiml Jan 30 '18 at 20:39
5
$\begingroup$

That's an interesting question! Something that might be close to what you're looking for is homomorphic encryption. Intuitivelly:

A public key encryption scheme is (fully) homomorphic if, on top of the usual key generation, encryption and decryption algorithms, we can obtain (without knowledge of the private key) an encryption of $f(m_1,\ldots,m_k)$ from encryptions of $m_1,\ldots, m_k$.

Therefore, if Charlie has keys $(pk, sk)$ of a FHE scheme and Alice and Bob know the public key $pk$, then Alice and Bob can compute $c_1 = \mathsf{Enc}_{pk}(a)$ and $c_2 = \mathsf{Enc}_{pk}(b)$ respectively, then they compute an encryption of $a\cdot b$ using the homomorphic property and send this to Charlie. He can then decrypt this value to obtain $a\cdot b$.

Notice that in your particular application you only need one multiplication, which is much easier to handle than the case of any general function. In fact, there is the concept of Somewhat Homomorphic Encryption (SHE), which is pretty much like the concept explained above but the function is restricted to have certain multiplicative depth. This is useful as (1) SHE schemes do exist, based on different problems like approximate GCD or LWE, and (2) there is a technique called bootstrapping that can take you from a SHE with certain properties to a FHE.

This solution may not fullfil your requirement, as it's not like Alice and Bob are sending values to Charlie separately.

As pointed in the comments by SEJPM, another tool can be Secure Multiparty Computation. In this setting, the parties are involved in a protocol where A and B input $a$ and $b$, and C gets $c = ab$. In general, this doesn't have to have the syntax you specify in the question, but it's easy to come up with a protocol that has some resemblance with it.

Alice and Bob cooperate to sample a common random value $r$, unknown to Charlie. Alice then lets $A(a) = a\cdot r$ and Bob sets $B(b) = b\cdot r^{-1}$. These two values are sent to charlie, who simply multiplies them to get $(ar)(br^{-1}) = ab$. We can show that even if C is corrupt, he doesn't learn anything about $a$ and $b$, besides the fact that their product is what he just learned. In some sense, this means that "$A$ and $B$ are not invertible". The intuition is that we can simulate what Charlie sees during the execution of the protocol based only on the value of $a\cdot b$, and Charlie cannot tell the difference, therefore, he doesn't get any information about $a$ and $b$. Of course, this assumes we have some sort of field structure.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This doesn't seem to solve the problem as stated, since Charlie can simply decrypt the individual ciphertexts. $\endgroup$ – Maeher Jan 30 '18 at 17:23
  • $\begingroup$ @Maeher yes! Perhaps you're right. This has an easy fix (and in fact, this is the whole point of homomorphic encryption): Alice and Bob can compute the encryption of $a\cdot b$ themselves, and send that instead. Thanks! I will edit the answer. The issue now is that the solution does not have the same syntax as required by the OP $\endgroup$ – Daniel Jan 30 '18 at 17:25
  • $\begingroup$ Would there be a way to deterministically choose r beforehand without Alice and Bob communicating? like the hash of their Ab/aB or something. I don't know if that compromises the math later on. $\endgroup$ – jousle Jan 30 '18 at 17:51
  • $\begingroup$ @jousle Not the math. The randomness is used to argue that what Charlie sees does not reveal anything about $a$ nor $b$. It you use any public value that also Charlie can compute then privacy is compromised as Charlie can extract $a$ an $b$ using $r$ and the values he receives (even if this value is uniformly random). $\endgroup$ – Daniel Jan 30 '18 at 17:55
  • $\begingroup$ Your new approach now requires communication between Alice and Bob to homomorphically evaluate the multiplication. I understood the original question to mean that there is to be no communication other than the two messages sent from Alice and Bob to Charlie. $\endgroup$ – Maeher Jan 30 '18 at 18:19
5
$\begingroup$

The other answers already made it clear that it's impossible to solve the problem with this communication pattern if Alice and Bob do not share a secret a priori (and homomorphic encryption does not help for that, nor does MPC). Assume for now that Alice and Bob do share a common random secret $r$. Let us further assume that $r$ is way longer than $a$ and $b$. We first break $r$ into three long enough parts, $r_a,r_b$ and $r'$. Then the problem can be solved as follows:

  • Alice sends $(x_a,y_a) = (a + r_a,ar_b + r_ar_b+r')$ to Charlie
  • Bob sends $(x_b,y_b) = (b + r_b,br_a - r')$ to Charlie
  • Charlie computes $ab = x_ax_b - (y_a+y_b)$

In the above protocol, I assume that additions are performed over an appropriate finite group, and that $r_a,r_b,r'$ are random over this group; alternatively, addition can be over the integers, but then $r_a,r_b$ must be $k$ bits longer than $(a,b)$ ($k$ is a security parameter) and $r'$ must be $k$ bits longer than $r_ar_b$ to ensure statistical security.

Correctness is clear. It can be easily shown that the distribution of $(x_a,x_b,y_a,y_b)$ can be perfectly (or statistically, in the case where addition is over the integers) simulated knowing only $ab$, which proves that this protocol only leaks $ab$, and nothing more.

Compared to Daniel's solution (using $ar$ and $br^{-1}$), this approach assumes far less structure on $a,b$. In particular, $a,b$ need not belong to a multiplicative group. This allows to capture the important case where one of $a,b$ could be $0$, where Daniel's solution would break down. Here, Charlie would only learn that the output is $0$, but not which input is $0$. On the other hand, Daniel's solution requires a shorter common random string, so when $a,b$ are indeed elements of a multiplicative group, it is a better solution.

The protocol I described is information theoretic, but uses a large shared random string. Assuming the existence of a pseudorandom generator (which can be based on any one-way function), there is an obvious way of compressing the size of the shared random string: Alice and Bob only share a short seed for the PRG, and locally generate a long pseudorandom string $(r_a,r_b,r')$ before using the above protocol. Security immediatly reduces to the security of the PRG.

Note: the communication pattern that you specify (using in addition a shared key between Alice and Bob) has been studied in the cryptographic community under the name private simultaneous message (you should find many references by typing that in your favourite browser). It is a particular case of multiparty computation.

| improve this answer | |
$\endgroup$
  • $\begingroup$ But the moment A sends the message, B learns her secret a. $\endgroup$ – pintor Jan 31 '18 at 15:43
  • $\begingroup$ I'm making the usual assumption of private channels here (or equivalently, I only care about security for Charlie). Without this assumption, it is again trivially impossible. $\endgroup$ – Geoffroy Couteau Jan 31 '18 at 15:45
  • $\begingroup$ In a comment, it was specified, that "she (Alice) can only know a (and Bob can only know b)" Why do you think it's impossible? A and B post their public keys in advance. Diffie Hellman key exchange (no interaction, everything you need is already published) -> shared secret -> Daniel's solution $\endgroup$ – pintor Jan 31 '18 at 15:53
  • $\begingroup$ It's obviously possible if you allow preliminary interactions, as the players can then exchange keys, breaking the symmetry of the protocol. Note that in this case, they can simply use this preprocessing phase to set up private channels, then use the solution I described afterward. To me, the comment you mention means that Alice can't use knowledge of $b$ to compute her flow, as she is not supposed to know it. And the impossibility I mention refer to the minimal scenario where Alice and Bob only share a common random string. $\endgroup$ – Geoffroy Couteau Jan 31 '18 at 16:05
  • $\begingroup$ But the moment A sends her message, B can learn a and select b accordingly. Suppose, he wins if the last digit of H(ab) is 0 or something. $\endgroup$ – pintor Jan 31 '18 at 17:11
0
$\begingroup$

Ok, let me try.

C picks random values $r_{CA}$ and $r_{CB}$, defines some function $f$ and ElGamal encryption parameters $(p,g,q,h)$, where $x$ - secret key. C publishes: $(p,g,q,h)$, $g^{r_{CA}}$, $g^{r_{CB}}$, $f$

A picks random values $r_{AC}$ and $r_{AB}$ and publishes $g^{r_{AC}}$, $g^{r_{AB}}$.

B picks random values $r_{BC}$ and $r_{BA}$ and publishes $g^{r_{BC}}$, $g^{r_{BA}}$.

So, public parameters are:

C: $(p,g,q,h)$, $g^{r_{CA}}$, $g^{r_{CB}}$, $f$

A: $g^{r_{AC}}$, $g^{r_{AB}}$.

B: $g^{r_{BC}}$, $g^{r_{BA}}$

To compute product of $a$ and $b$, where $a$ is A's secret and $b$ is B's secret, parties should do the following:

A computes $KEY_{AB} = (g^{r_{BA}})^{r_{AB}}$, $k_{AB} = f(KEY_{AB})$, $KEY_{AC} = (g^{r_{CA}})^{r_{AC}}$, $k_{AC} = f(KEY_{AC})$ and $c_a = a*h^{k_{AB}+k_{AC}}$. A sends $c_a$ to C.

B computes $KEY_{AB} = (g^{r_{AB}})^{r_{BA}}$, $k_{AB} = f(KEY_{AB})$, $KEY_{BC} = (g^{r_{CB}})^{r_{BC}}$, $k_{BC} = f(KEY_{BC})$ and $c_b = b*h^{k_{BC} - k_{AB}}$. A sends $c_b$ to C.

C multiplies $c_a$ and $c_b$ to get $c = c_a*c_b = a*h^{k_{AB}+k_{AC}}*b*h^{k_{BC} - k_{AB}} = ab*h^{k_{AC}+k_{BC}}$. Also C computes $KEY_{BC} = (g^{r_{BC}})^{r_{CB}}$, $k_{BC} = f(KEY_{BC})$ and $KEY_{AC} = (g^{r_{AC}})^{r_{CA}}$, $k_{AC} = f(KEY_{AC})$

Now C has $ab*h^{k_{AC}+k_{BC}}$ and also can compute $g^{k_{AC}+k_{BC}}$, which is ElGamal encryption of ab.

C doesn't know $k_{AB}$, so it can't learn $a$ or $b$ individually. A doesn't know $k_{BC}$ and can't discover B's secret $b$. Similary B can't learn $a$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This basically amounts to saying that Alice and Bob can both encrypt their input with ElGamal and send that; as ElGamal is multiplicatively homomorphic, Charlie can locally compute an encryption of the product from these ciphertexts. That does not help him getting the final result, which is $ab$. $\endgroup$ – Geoffroy Couteau Jan 31 '18 at 14:40
  • $\begingroup$ @GeoffroyCouteau, not exactly. C gets the ElGamal cipher that encrypts ab only when multiplies c_a and c_b together. And also computes k_AC and k_BC. Otherwise, C doesn't know k_AB and can't decrypt. If A and B just encrypt their secrets, C can learn them, since it knows key x. $\endgroup$ – pintor Jan 31 '18 at 15:21
  • $\begingroup$ Ok, I had misunderstood your solution. However, you solve it by allowing an initial round of interaction between Alice, Bob, and Charlie, where they all publish some values. Given this preprocessing phase, yes, it's clearly feasible and quite easy to solve the problem (it's a standard MPC protocol), and I don't see how this fits in OP's question anymore. $\endgroup$ – Geoffroy Couteau Jan 31 '18 at 16:02
  • $\begingroup$ @GeoffroyCouteau, technically setup phase it's not an interaction between parties, but it allows to ensure that A doesn't learn b and B doesn't learn a. Suppose C published the result as F(ab), where F is a one-way function. If B knows a, he can choose b in a way so F(ab) results in something he likes. $\endgroup$ – pintor Jan 31 '18 at 17:09
  • $\begingroup$ I have to disagree, technically a setup phase is an interaction between the parties. $\endgroup$ – Geoffroy Couteau Jan 31 '18 at 17:20
0
$\begingroup$

Fun question:

Suppose that you allow Alice and Bob to interact on startup.

Alice and Bob can (in effect) compute $(Enc(Alice, T), Enc(Bob, V))$ such that $V+T = a*b$ using Oblivious Transfer Multiplication.

Then they simply send each share to Charlie, who sums them to get $a*b$. Each share individually bears no information Charlie could use to derive a or b. If I recall, T is randomly picked by Alice, and V is computed via the OT to be $a*b - T$. Were Alice to pick $T=a$, then information would leak, but no scheme can protect from Alice telling Charlie $a$ anyways....

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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