Is the following scheme private? By private i mean an untrusted aggregator (UA) cannot reveal anything other then an aggregate function output on plaintext data

Each party holds a secret key $k_i$ and data $d_i$. It sends to the aggregator $d_i H(r)^{k_i}$. $H$ is a hash function that maps elements to a group $N$ in which $H(r)^S \equiv 1 mod {N}$ Lets say a trusted dealer(TD) for two parties sends to the untrusted aggregator $H(r)^{S-k_1}$ and $H(r)^{S-k_2}$ and UA wants to learn the multiplication of the data of those parties. Then UA computes

$$d_1 H(r)^{k_1}d_2 H(r)^{k_2}H(r)^{S-k_1}H(r)^{S-k_2} =d_1d_2H(r)^{2S}=d_1d_2H(r)^{S^2}=d_1d_2$$

  • 1
    $\begingroup$ As far as I can see, from your setup UA computes $d_1H(r)^{k_1}H(r)^{S-k_1}=d_1$, which would mean that the UA learns both values. $\endgroup$
    – DrLecter
    Nov 19, 2013 at 16:54
  • $\begingroup$ There's a formal error in the last formula: $H(r)^{2S}=(H(r)^S)^2$. But $H(r)^{S^2}$ means something else (The expression would be wrong with most other values) $\endgroup$
    – tylo
    Nov 19, 2013 at 18:44

1 Answer 1


Well, it has the obvious problem that if the UA has both $d_1H(r)^{k_1}$ (from the party) and $H(r)^{S-k_1}$ (from the UA), it can compute $d_1$ directly.

  • $\begingroup$ If somehow the UA never gets encrypted data per single user but always in a pair manner?I.e: Data are first sent to the TD and then it sends to the UA $d_1 H(r)^{k_1}d_2 H(r)^{k_2}$ but this sounds stupid...since now the TD can decrypt but we make the assumption that is trusted $\endgroup$
    – curious
    Nov 19, 2013 at 17:05
  • 2
    $\begingroup$ @curious: In schemes like this, we assume that the dealer gets involved up front, but doesn't actually get involved with any specific aggregation. If we don't make that assumption, the problem is trivially solved by both parties sending their data securely to the TD, which computes the aggregation and publishes it. $\endgroup$
    – poncho
    Nov 19, 2013 at 17:35
  • $\begingroup$ If you send $H(r)^{S-k_1-k_2}$ to the UA, it cant compute $d_1$ and $d_2$ directly. $\endgroup$
    – tylo
    Nov 19, 2013 at 18:38
  • $\begingroup$ @tylo: actually, if $S << N$, then it's likely that someone could recover $d_1$, $d_2$ directly from $d_1H(r)^{k_1}$, $d_2H(r)^{k_2}$ $\endgroup$
    – poncho
    Nov 21, 2013 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.