FPTD: Super Fast Privacy-Preserving and Reliable Truth Discovery for Crowdsensing

Crowdsensing has gained widespread attention due to its efficient and low cost data collection mode that leverages a large number of intelligent mobile devices. Privacy and data quality are two key concerns in crowdsensing. Recently, extensive efforts have been devoted to privacy-preserving truth discovery (PPTD), which aims to protect sensitive data while improving data quality. However, existing PPTD schemes suffer from either low reliability—especially under collusion attacks and server dropout—or low communication efficiency. As a result, they fail to meet the practical requirements of real-time processing with high reliability. To address the problems, we propose FPTD, a super fast PPTD scheme for crowdsensing that provides <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula>-out-of-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$N$</tex-math></inline-formula> threshold reliability, with a focus on boosting online efficiency. Our scheme employs edge nodes as servers in a multi-server architecture, resisting up to (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T-1$</tex-math></inline-formula>) colluding servers and (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$N-T$</tex-math></inline-formula>) server dropouts. We construct novel protocols for PPTD, including secure division and negative of approximate logarithms. We further significantly improve communication efficiency by designing protocols <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">multiply-then-divide</i>, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">dot-product-then-divide</i>, and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">filter-then-dot-product-then-divide</i>, all of which require only a single element per party in online communication. Our tradeoff is a need for a circuit-dependent offline phase, which is independent of the parties' inputs. Compared to the state-of-the-art scheme, we are 13<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\sim 217\times$</tex-math></inline-formula> faster (LAN) and 17<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\sim 190 \times$</tex-math></inline-formula> faster (WAN) in online execution time.