Decoupling Statistical Trends from Data Volume on LDP-Based Spatio-Temporal Data Collection

Spatio-temporal data is useful for various applications such as urban planning, epidemiology, and natural disasters, but causes exposure of private information, such as home/workplace addresses, because it involves people's trajec-tories. Local Differential Privacy (LDP) based processing is a promising technology for removing sensitive information from spatio-temporal data. A LDP-based processing adds a certain amount of noise to make each piece of data indistinguishable while keeping its intrinsic value. However, LDP is vulnerable to data amplification. When a data store receives data from any device, the data store only appends the received data to existing data. This allows anyone to inject any amount of data into the data and manipulate the trend of the whole data. To tackle this problem, we design a data collection method enabling a data store to collect statistical trends of data from every device irrespective of the data volume. We utilize an Oblivious Transfer (OT) protocol that performs a packet sampling at the reception side, the data store. This sampling enables the collection of statistical trends but requires adjusting LDP processing because the amount of noise is determined by the assumption that the data store receives every piece of LDP-processed data. We then propose an adjustment method for LDP-based process based on the Euclidean algorithm. We conducted qualitative and experimental overhead analysis and showed that the proposed method decouples the relationship between statistical trend and data volume. We also show the processing load can be acceptable on small devices such as smartphones and loT.