Review for XLX20

[XLX20] - V-PATD

Catch you if you deceive me: Verifiable and privacy-aware truth discovery in crowdsensing systems

(ASIA CCS'20, October 5-9, 2020, Taipei, Taiwan)

"The first verifiable and privacy-aware truth discovery protocol in crowdsensing systems."

Motivation

Two fundamental problems in PPTD:

data privacy protection
verifiability of aggregated results

To address these challenges, we propose V-PATD, the first verifiable and privacy-aware truth discovery protocol in crowdsensing systems.

Two methods (high level):

perturb each user's sensory data independently
design a publicly verifiable approach to enable verifiability

Preliminaries

Three generic entities:

users (mobile devices), honest-but-curious
a task requester
a cloud server, dishonest

Two potential security:

the server and certain users may violate the data privacy of honest users
the server may return incorrect aggregated results to the task requester

Security and privacy requirements:

protect the integrity of aggregated result
privacy protection of user's sensory data

Symbols:

$x_n^m$ : the recorded sensory data of the n-th user for the m-th object
$x_*^m$ : the aggregated result (i.e., ground truth)
$f$ : monotonically decreasing function
$d_{ist}(x_n^m, x_*^m)$ : distance function

Weight Update:

$w_n=f(\sum_{m=1}^{\mathcal{M}}d_{ist}(x_n^m, x_*^m))$

or specifically:

$w_n=log(\frac{\sum_{n'=1}^{\mathcal{N}}\sum_{m=1}^\mathcal{M}d_{ist}(x_{n'}^m, x_*^m)}{\sum_{m=1}^{\mathcal{M}}d_{ist}(x_n^m, x_*^m)})$

Note

A particular user will have higher weight if the data provided by him is closer to the aggregated results.

Truth Update:

$x_*^m=\frac{\sum_{n=1}^{\mathcal{N}}w_n\cdot x_n^m}{\sum_{n=1}^{\mathcal{N}}w_n}$

Note

A particular user's data will be counted more in the aggregation procedure if this user has a higher weight.

The proposed scheme

user:

perturbs its sensory data independently by adding noises
signs its data

server:

executes the privacy-preserving truth discovery algorithm
return the aggregated results along with corresponding proofs

task requester:

choose to accept or reject the results by only checking the proofs

Perturbation Mechanism:

$\hat{x}_n^m=x_n^m+\zeta_n^m$

where the noise $\zeta_n^m$ is selected from $N(0,\gamma_n^2)$

Note

adding larger noise helps provide a higher level of privacy protection, but bounds to impair the accuracy of the aggregated results.

all users select the variance independently from an exponential distribution with hyper parameter $\eta_2$

Verification Mechanism:

Server only need to compute the polynomials and the corresponding proofs, i.e.,

$\sum_{n'=1}^{\mathcal{N}}\sum_{m=1}^{\mathcal{M}}d_{ist}(x_{n'}^m, x_*^m)$
$\sum_{m=1}^{\mathcal{M}}d_{ist}(x_n^m, x_*^m)$
$\sum_{n=1}^{\mathcal{N}}w_n\cdot x_n^m$
$\sum_{n=1}^{\mathcal{N}}w_n$

Publicly verifiable computation

$\mathsf{Setup}(1^\lambda)\to (pp)$

$pp=(e, p, G_1, G_2, g, h, H, H')$ , $e:G_1\times G_1 \to G_2$ , $g,h$ are the generator of the group $G_1$ , $H:\{0,1\}^*\to Z_p$ , $H':\{0,1\}^*\to Z_p$

$\mathsf{GenKey(pp)\to (sk, pk)}$

$sk_n=(\beta_n, \beta'_n, \beta''_n)$

$pk_n=\{(g^{\beta_n}, h^{\beta_n}, h^{\frac{1}{\beta_n}}), (g^{\beta'_n}, h^{\beta'_n}, h^{\frac{1}{\beta'_n}}), (g^{\beta''_n}, h^{\beta''_n}, h^{\frac{1}{\beta''_n}})\}$

$\mathsf{GenSign}(\hat{x}_n, sk_n)\to \rho_{x_n}$

$\varphi_\tau = H(\tau)$ $\digamma_\tau = H'(\tau)$

randomly choose $t_n\in Z_p$ , sets $\mu_n = h^{t_n}$

$v_n^{(1)} = \beta_n(\varphi_\tau + t_n) \mathsf{mod} p$

$v_n^{(2)} = \beta'_n(\digamma_\tau + t_n) \mathsf{mod} p$

$v_n^{(3)} = \beta''_n(\hat{x}_n + t_n) \mathsf{mod} p$

$\rho_{x_n} = (\mu_n, v_n^{(1)}, v_n^{(2)}, v_n^{(3)})$