Cryptographic scheme where a single message cannot be decrypted but if combined with other it can be

Question

i'm wondering if this type of cryptographic scheme does exists. I know about homomorphic encryption but if one has the private key, he can decrypt every single message.

I would like to know if there is a scheme where each user can encrypt the message with a key (public?). Then, the one who has the decrypiton (private) key cannot decrypt every single message but if the messages are combined together (such as muliplied or summed), he can get the correct result.

For instance: A has a key KA, B has a key KB. A encrypts the value 1 with the key KA and obtains MA. B encrypts the value 2 with KB and obtains MB. MA and MB are published. An element C has a decryption key but he cannot decrypt MA and MB but if they are combined, such as MA+MB, he can decrypt the result and obtain 3 (1+2). I think if this type exists maybe there are several public-private keys related in a certain way...

Answer 1

You could accomplish this using a secret sharing scheme, which doesn't require any public key cryptography. An $(n,k)$ secret sharing scheme allows a secret to be divided up into $n$ shares such that the secret can be recovered from any $k$ shares. However, if you only have $k - 1$ shares you cannot recover any information about the secret.

Here, we will use a simple additive $(3,3)$ secret sharing scheme over a finite field $\mathbb{F}$. Given a secret $s \in \mathbb{F}$, we can split it into three shares:

$$ [s]_1, [s]_2, [s]_3 \in_R \mathbb{F} \mid s = [s]_1 + [s]_2 + [s]_3 $$

Each of the three shares is uniformly distributed at random, so an adversary holding only one or two shares learns nothing about the secret $s$. Recovering the secret from all three shares is simple: just add them all together. A nice property of this scheme is that it's linear, so we can add two secrets together by adding their shares together:

$$ s_a + s_b = ([s_a]_1 + [s_b]_1) + ([s_a]_2 + [s_b]_2) + ([s_a]_3 + [s_b]_3) $$

This means that we can do additions on the secret values while they are secret shared, and thus we can compute simple functions without revealing the secret inputs! In fact, there are even (complicated) protocols for doing other operations on these secret shares, such as multiplication and exponentiation.

The protocol

Alice wants to send her secret $s_a$ and Bob wants to send his secret $s_b$ such that Charlie can only learn the sum $s' = s_a + s_b$ but not the individual values. We assume here that all of the players are connected by secure authenticated channels.

1. Alice shares her secret $s_a$ by:
   • Keeping $[s_a]_A$ for herself
   • Sending $[s_a]_B$ to Bob
   • Sending $[s_a]_C$ to Charlie
2. Bob shares his secret $s_b$ the same way:
   • Sending $[s_b]_A$ to Alice
   • Keeping $[s_b]_B$ for himself
   • Sending $[s_b]_C$ to Charlie
3. Now we want each party to compute $s' = s_a + s_b$ on their local shares:
   • Alice computes $[s']_A = [s_a]_A + [s_b]_A$
   • Bob computes $[s']_B = [s_a]_B + [s_b]_B$
   • Charlie computes $[s']_C = [s_a]_C + [s_b]_C$
4. Finally, Alice and Bob open their result towards Charlie:
   • Alice sends Charlie $[s']_A$
   • Bob sends Charlie $[s']_B$
5. Charlie now has the following information:
   • One share of $s_a$: $[s_a]_C$
   • One share of $s_b$: $[s_b]_C$
   • Three shares of $s'$: $[s']_A, [s']_B, [s']_C$

Charlie doesn't have enough shares to recover $s_a$ or $s_b$, but he can easily recover $s'$ as:

$$ s' = [s']_A + [s']_B + [s']_C $$

Note that this simplistic scheme is not robust, because Alice (or Bob) could lie and provide shares $[s_a]_A + [s_b]_B + [s_b]_C \ne s_a$. To protect against this, you'd want to use a verifiable secret sharing scheme so that the players can detect an inconsistent sharing.

This protocol is interactive, because it requires Alice and Bob to send their $[s_a]_B$ respectively $[s_b]_A$ values to each other. With some minor modifications, it could be made non-interactive.

Answer 2

A solution is proposed in patent application WO 2018091084 A1, which introduces:

an improved method and system for securely aggregating data from a plurality of clients in such a way that the data from an individual client is not revealed and the aggregated data is only revealed to a server.