Is it feasible to design a crypto scheme for centralised reporting of anonymized data?

I would like to find out if it is feasible to design a cryptographic scheme that would allow several "reporting parties" to independently transfer information to the same centralised "authority", under the following constraints:

1. The "authority" should not receive the "original information" or be able to infer the "original information", but it should receive "derived information".

2. Without knowing the "original information", the "authority" should be able to verify that "derived information" from two or more "reporting parties" originates from the same "original information".

3. The number of "reporting parties" should be dynamic. Reporting parties cannot work together and do not know if other "reporting parties" have transmitted the same "original information" in a derived form.

4. BONUS: Two or more "reporting parties" should not be able to verify that "derived information" from two or more "reporting parties" originate from the same "original information".

The "original data" is arbitrarily short (e.g. significantly less than 40 bits).

I have a hunch that the first two constraints would somehow require hashing, random numbers and perhaps public-private keys, while the last constraint would definitely involve public-private keys... but have no idea as to how to design such a scheme or even if it would be feasible, given short data.

I can provide the exact use case if someone's interested; teaser: EU's MiFIR and Investor Privacy :)

Ok, here's what I got:

• Someone selects two large primes $p$ and $q$ such that $n = 2pq + 1$ is prime, and $pq$ is large enough to make factorization infeasible; they select a value $g$ with order $p$ in $Z^*_n$ and a value $h$ with order $q$ in $Z^*_n$ (e.g. select a random $s$ in the range $[2, n-2]$ and set $g = s^{2q} \bmod n$ and $h = s^{2p} \bmod n$ and verify that neither $g$ nor $h$ are 1). Someone (and it need not be the same someone) also selects a symmetric encryption key $k$.

• The authority gets the values $q, n$ (and optionally the values $g, h, p$; the authority doesn't need them, but it wouldn't hurt security), the authority does not get $k$. Each "reporting party" gets the values $g, h, n, k$.

• For a reporting party to convert original information $i$ into derived information, he first deterministically encrypts $i$ with the key $k$ (forming $E_k(i)$), selects a random value $r$, and computes $d = g^{E_k(i)}h^r \bmod n$, which is the derived information, which he can send to the authority.

• For the authority to compare two derived information $d_1, d_2$ to see if they correspond to the same original one, he computes $(d_1 d_2^{-1})^q \bmod n$, if that is 1, then the original information is the same.

This works because $d_1 = g^{E_k(i_1)}h^{r_1}$ and $d_2 = g^{E_k(i_2)}h^{r_2}$, hence $(d_1 d_2^{-1})^q = (g^{E_k(i_1)}h^{r_1} \cdot g^{-E_k(i_2)}h^{-r_2})^q = (g^q)^{E_k(i_1) - E_k(i_2)}$, which is 1 if $E_k(i_1) = E_k(i_2)$, that is, if $i_1 = i_2$

1) The authority does not directly receive original information

2) The authority can compare two different derived information; it cannot otherwise reconstruct the original information; that is because of the symmetric key $k$; given $g^{E_k(i)}$, the attacker might be able to recover $E_k(i)$ (actually, he couldn't, however if the $E$ function was public without a secret $k$, he could, given the short range of possible $i$ values), however because he doesn't know $k$, that's as far as he could go.

3) Reporting parties are dynamic; all reporting parties are given the same information, and so adding more is not an issue; they cannot determine if other parties have contributed the same information; because they don't know the orders of $g$ and $h$, they cannot determine this.

4) Two or more parties cannot collaborate to subvert the system; because all reporting parties get the same information, two parties don't have any more power than one.

Now, a reporting party and the authority could collaborate to recover another reporting party's original information; this is actually inherent in the problem, and so is not an issue (at least as far as I'm concerned; you may consider it a deal-breaker, in which case you need to rethink the problem). You could make it somewhat more difficult by replacing an invertible encryption function $E$ with a keyed hash $H$ (and assume that two different inputs just don't collide); however given the small range of the original information, it won't help that much...

• It's only "inherent in the system" that "a reporting party and the authority could collaborate to" mount a dictionary attack on "another reporting party's original information". ​ Does your scheme allow a significantly easier way for "a reporting party and the authority" to "collaborate to recover another reporting party's original information"? ​ ​ ​ ​ – user991 Feb 19 '17 at 23:55
• Thanks @poncho and Ricky Demer ! Amazingly fast and neat solution. In my specific use case it is indeed inherent that a reporting party and the authority could collaborate to recover other parties original information. However this is actually a non-stated but wanted property of the system, as the anonymity should last only as long as the authority does not use its legal right to "pierce the anonymity vail". What I wanted to know is if it is possible to "shield" this information from a technical point of view; and you offered me a perfect answer. Kudos! – bnqprv Feb 20 '17 at 14:35
• Oops wrote too fast... A problem remains: In your scheme it is necessary to disseminate k to all reporting parties. Originally, this would unfortunately violate the assumption that "reporting parties cannot work together" to set the system up. In my use case it is in fact impossible to know who the other reporting parties are or even if there are other reporting parties with the same "original information". So selecting an disseminating the key k seams infeasible... – bnqprv Feb 20 '17 at 15:24
• ... Unless you add another distinct centralized party (the "anonymizer") who's sole purpose it is to generate and disseminate k to reporting parties, but not to the central authority. But in that case, I would like to ask you: could the same k be used by reporting parties to disseminate different pieces of information in a derived fashion to the authority without one compromise affecting all transmissions? If yes, is it a requirement that g, h and p be generated and disseminated by this additional "anonymizer" or not? Thx for your answer. – bnqprv Feb 20 '17 at 15:31