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:


The "authority" should not receive the "original information" or be
able to infer the "original information", but it should receive
"derived information".
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".
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.
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$

As for your requirements:

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...