Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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!
In the way you setup the problem the answer is No.
As Charlie can perform $C(A(1),B(b))$.
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.
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:
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.
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$.
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....
