Review for MSJ17

[MSJ17] - L-PPTD

A Lightweight Privacy-Preserving Truth Discovery Framework for Mobile Crowd Sensing Systems

(IEEE INFOCOM'17)

"... is implemented by involving two non-colluding cloud platforms and adopting additively homomorphic cryptosystem."

---

Problem Formulation

two types of parties:

• data requester (an individual or organization)
• participating workers (a group of mobile device users)

assumption:

• semi-honest threat model

symbols:

• objects: $O=\{o_1,o_2,...,o_M\}$
• workers: $U=\{u_1,u_2,...,u_K\}$
• weights: $W=\{w_1,w_2,...,w_K\}$
• $x_m^k$: the sensory data of worker $u_k$ for object $o_m$
• goal: calculate the estimated values $\{x_m\}_{m=1}^M$

Preliminary

truth discovery:

weight estimation:

$$w_k=f(\sum_{m=1}^{M}d(x_m^k, x_m))$$

where $f$ is a monotonically decreasing function, $d(x_m^k, x_m)$ is the distance function

truth discovery method CRH:

$$w_k=log(\frac{\sum_{k'=1}^{K}\sum_{m=1}^{M}d(x_m^{k'}, x_m)}{\sum_{m=1}^M d(x_m^k, x_m)})$$

truth estimation:

$$x_m=\frac{\sum_{k=1}^{K}w_kx_m}{\sum_{k=1}^{K}w_k}$$

additively homomorphic encryption

$$\forall m_1,m_2\in \mathcal{M}, E[m_1+m_2]=E[m_1]\oplus E[m_2]$$

$$\forall m_3\in \mathcal{M}, E[a\cdot m_3] = a\otimes E[m_3]$$

L-PPTD Framework

• $S_A, S_B$: two cloud platforms
• $S_A, S_B$ calculate the summed distances without knowing the raw data of each worker
• each worker will be able to calculate

---

1. $S_B$ generates the public key $pk$ and private key $sk$, $sk$ is only known by $S_B$
2. worker $u_k$ generates random numbers $\{\alpha_m^k\}_{m=1}^M$, $\{\beta_m^k\}_{m=1}^M$, $\gamma_k$, perturbs $x_m^k$ as $\hat{x}_m^k=x_m^k-\alpha_m^k$, uploads $\{\hat{x}_m^k\}_{m=1}^M$ to $S_A$
3. each worker uploads all the random numbers to $S_B$
4. $S_B$ calculates $\{E[\alpha_m^k]\}_{k,m=1}^{K,M}$, $\{\sum_{k=1}^K\beta_m^k\}_{m=1}^M$, $\sum_{k=1}^K\gamma_k$, sends these three to $S_A$

For $S_A$:

calculates ciphertext $C_{conti}=\prod_{k=1}^K\prod_{m=1}^M\{E[(\hat{x}_m^k - x_m)^2]\cdot E[\alpha_m^k]^{2(\hat{x}_m^k - x_m)}\}$, sends to $S_B$

For $S_B$:

decrypt $C_{conti}$ with $sk$, calculates $\sum_{k=1}^K\sum_{m=1}^M(\alpha_{m}^k)^2$, obtains $\sum_{k=1}^k\sum_{m=1}^M(x_m^k-x_m)^2$, sends to $u_k$

For $u_k$:

calculates $\sum_{m=1}^M d(x_m^k, x_m)$ and then estimates $w_k$

sends $w_kx_m^k - \beta_m^k$ and $w_k - \gamma_k$ to $S_A$

For $S_A$:

calculates $\sum_{k=1}^Kw_kx_m^k=\sum_{k=1}^K(w_kx_m^k - \beta_m^k) + \sum_{k=1}^K\beta_m^k$

---

Review

• 如何保证用户隐私： 使用随机数
• $S_B$ 知道所有的随机数，$S_A$ 来更新权重
• $S_A$ 与 $S_B$ 不共谋
• $S_A$ 与 $S_B$ 通过同态加密的方式完成真值的估计
• 用户本地更新权重

问题： 如何保证 user 更新的 $w_k$ 是正确的 （因为 user 是半诚实的？）