1
$\begingroup$

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

|improve this question
$\endgroup$
  • 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 '13 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 '13 at 18:44
3
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\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 '13 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 '13 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 '13 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 '13 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.