Cryptographic encoding scheme that enables counting

31 Views Asked by At

Suppose there are $n$ players. Each player has a $k$-length bit vector. Is there an efficient way of encoding the $k$ length bit vectors, such that after receiving the $n$ encoded outputs, one can only infer the counts of $1$'s at each of the $k$ positions but not the $n$ original bits. That is after receiving the $n$ encoded vectors, one can infer how many players had $1$s in the $i$th bit $\forall i$.

1

There are 1 best solutions below

3
On BEST ANSWER

You might as well let $k=1$ and encode the separate bits in each vector in parallel. In that case each party has a bit and you wish to hide each party's bit but reveal the sum. You can do that using a standard multi-party computation algorithm on an arithmetic circuit consisting of just addition gates like BGW.