Review for RTPT'19

[RTPT'19] - RTPT

RTPT: A Framework for Real-Time Privacy-Preserving Truth Discovery on Crowdsensed Data Streams

(Computer Networks)

"Our design is based on the incremental conflict resolution on heterogeneous data, which is very efficient in processing data streams ."

---

Introduction

Two limitations:

• dropouts are common for mobile devices
• all prior works are based on traditional truth discovery methods (conduct inefficient iterative procedures)

there is no existing PPTD work that can eliminate these two shortcomings simultaneously.

Goal:

• explore a robust and scalable PPTD architecture for real-time MCS applications

... we build our security design on incremental conflict resolution on heterogeneous data (ICRH) for its state-of-the-art efficiency performance in our target MCS scenario.

ICRH:

• obtain the truth for sensed objects in the current time period based on the worker's weights learned from historical data

The proposed scheme:

• for real-time PPTD on crowdsensed data streams
• design a new secure summation aggregation protocol
• a constant number of rounds, low communication overhead, fully robustness to clients' dropping out at any point
• only one server

Symbols:

Suppose there are $|I|$ sensing workers and $|M|$ sensed objects. In the $t$-th time period, the worker $i$ with the weight $w_i^t$ generate a sensing data $x_{mi}^t$ of the object $m$ with her mobile devices.

Threat model:

• honest-but-curious
• protocols under the semi-honest model would present much more efficient implementation than protocols under the malicious adversary model
• the most common malicious attack is that workders maliciously manipulate their sensing data

Preliminaries

Truth discovery:

• identify the true information of the same object from noisy data provided by sensing workers with different reliability
• CRH is widely used, but is mostly designed to run on static data sets

ICRH

Loss Function:

$$d(x_{mi}^t, X_m^t) = d(x_{mi}^t - X_m^t)^2$$

TruthUpdate:

$$X_m^t = \frac{\sum_{i=1}^{|\mathcal{I}|}w_i^{t-1}x_{mi}^t}{\sum_{i}^{|\mathcal{I}|}w_i^{t-1}}$$

WeightUpdate:

$$w_i^t = \log\big(\frac{\sum_{i=1}^{|\mathcal{I}|}d_i^t}{d_i^t}\big)$$

and

$$d_i^t = d_i^{t-1} \times \alpha + \sum_{m=1}^{|\mathcal{M}|}d(x_{mi}^t , X_m^t)$$

where decay rate $\alpha$ is introduced to accumulate the worker's loss.

Note

ICRH 的设计初衷是为了能处理流数据，在这种情况下用户可以随时加入和退出。值得注意的是，如果当前有用户加入时，该用户提供的数值不计入真值更新 （因为此时新用户没有权重，如果采用初始权重会导致结果不够精确），而是在权重更新是计算出该用户的权重。

Question

如果一个用户只在 $t$ 时刻提交了真值，然后 $t+1$ 时刻退出，那么该用户在整个真值计算中没有发挥任何作用。

Key agreement

Three algorithms:

• $\mbox{KA.param}(k) \to (\mathbb{G}, g, q)$
• $\mbox{KA.gen}(\mathbb{G}, g, q) \to (s^{SK}, s^{PK})$
• $\mbox{KA.agree}(s_i^{SK}, s_j^{PK}) \to s_{ij}$

Secret sharing

$\mathcal{T}$-out-of-$\mathcal{N}$ secret sharing:

• $\mbox{SS.share}(ss_i, \mathcal{T}, \mathcal{I}) \to \{j, ss_{ij}\}_{j\in\mathcal{I}\backslash\{i\}}$
• $\mbox{SS.recon}((j,ss_{ij})_{j\in\mathcal{I}'}, \mathcal{T}) \to ss_i$

Authenticated encryption

• $\mbox{AE.enc}(s, m)\to (c, \mathsf{tag})$
• $\mbox{AE.dec}(s, c, \mathsf{tag}) \to m$

---

The proposed framework design

Secure summation aggregation

Assume public parameters $k$ and threshold value $\mathcal{T}$ of secret sharing

• $\mbox{KA.param}(k) \to (\mathcal{G}, g, q)$
• $\mbox{KA.gen} \to (s_i^{SK}, s_i^{PK})$
• $\mbox{KA.gen} \to (c_i^{SK}, c_i^{PK})$
• send $(s_i^{PK} || c_i^{PK})$ to the server

Sharing keys and random seeds:

server:

• collect at lease $\mathcal{T}$ messages
• broadcast the received list $\{(i, s_i^{PK}, c_i^{PK})\}_{i\in\mathcal{I}_1}$

client $i$:

• sample an additional random $r_i^t\in_r Z_q$
• share $\mbox{SS.share}(r_i^t, \mathcal{T}, \mathcal{I}_1)\to (j, r_{ij}^t)_{j\in\mathcal{I}_1}$
• and $\mbox{SS.share}(s_i^{SK},\mathcal{T},\mathcal{I}_1)\to (j,s_{ij}^{SK})_{j\in\mathcal{I}_1}$
• encrypt them $e_{ij}^t \gets \mbox{AE.enc}(\mbox{KA.agree}(c_i^{SK}, c_j^{PK}), i||j, s_{ij}^{SK}||r_{ij}^t)$ for each other $j\in \mathcal{I}_1 \backslash \{i\}$
• send $\{(i, j ,e_{ij}^t)\}_{j\in\mathcal{I}_1\backslash \{i\}}$ to the server

server:

• gather lists of encrypted shares from at least $\mathcal{T}$ clients, i.e., $\mathcal{I}_2$
• send to each client $i\in\mathcal{I}_2$ all the encrypted shares $\{j,i,e_{ji}^t\}_{j\in\mathcal{I}_2\backslash\{i\}}$ and an random integer $f_t\in_r Z_q$

Note

用户 $i$ 生成的密文 $e_{ij}$ 的数量为 $|\mathcal{I}_1| - 1$

Masked inputs collection:

client $i$:

• receive $\{e_{ij}\}_{j\in\mathcal{I}_2}$
• copmute $s_{ij}\gets \mbox{KA.agree}(s_i^{SK}, s_j^{PK})$ for each other client $j\in\mathcal{I}_2$
• at each time period $t$

Note

先搁到这，不太靠谱，暂时不看了