Systems and methods for privacy-reserving data hiding
Inventors
Assignees
Universita Della Svizzera Italiana • New Jersey Institute of Technology
Publication Number
US-11652622-B2
Publication Date
2023-05-16
Expiration Date
2041-08-06
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Abstract
Described in detail herein is a method for encrypting or encoding time-stamped location data associated with a computing device. The method converts time and location information associated with the computing device into a vector format. The method generates a code vector based on the converted time and location vector. The method sorts entries in the code vector based at least in part on a predetermined ordering scheme. The method executes a random modification to each of the sorted entries. The method compares the code vector to at least one other code vector associated with another computing device. The method identifies other code vectors within a specified distance of the given code vector. The method concludes that the computing device and the at least one other computing device were in proximity to each other during a time period corresponding to the time information.
Core Innovation
The invention describes methods, systems, and devices for encrypting or encoding time-stamped location data from computing devices into code vectors to hide the original location data while maintaining relative relationships between data points. The process involves converting time and location information of a device into a vector format, generating a code vector using linear or non-linear transformations (such as polynomials over finite fields), sorting entries in this vector according to a pre-set scheme, and then applying random modifications to create non-deterministic encrypted outputs.
A critical part of the innovation is that it enables comparison between code vectors from different devices. By determining the Hamming distance between code vectors, the system can identify whether two devices were within close proximity during specific time periods, supporting privacy-preserving contact tracing. The encryption approach is keyless and designed to make inverting the process computationally infeasible, as recovering the original time and location from the code vector would require an unfeasible amount of computational resources or storage.
The core problem addressed by the invention is privacy concerns in systems that traditionally require recording and handling of users' absolute location histories for purposes such as contact tracing. By obfuscating or hiding the spatio-temporal data, the disclosed invention aims to make large-scale adoption feasible without disclosing individual location history, thereby addressing widespread reluctance based on security and privacy issues.
Claims Coverage
There are three independent claims in the patent, each directed to a method, a system, and a device for encrypting location data into a code vector to hide the data. The inventive features are as follows:
Encrypting location and time data into a code vector using transformation, sorting, and random modification
The claimed method, system, and device convert time and location information into a vector format. A code vector is generated from the converted time and location vector using a linear or non-linear transformation. The entries in the code vector are sorted based at least in part on a predetermined ordering scheme. Each sorted entry then undergoes a random modification. These code vectors are compared to at least one other code vector from another computing device. A distance (such as Hamming Distance) between code vectors is determined, and it is then determined whether devices were in proximity to each other during the corresponding time period.
Separation of client and server functions for privacy-preserving proximity detection
A system is disclosed in which: - The application on a mobile computing device performs conversion of time and location data, vector generation, sorting, random modification, and transmits the resulting code vector to one or more servers. - The server compares received code vectors to those associated with other devices, determines the relevant distance, and decides whether proximity occurred—all without direct access to the original time and location data.
Device implementing encryption and proximity detection with computer-readable instructions
A device includes at least one non-transitory computer-readable medium storing executable instructions. When executed, these instructions cause the processor(s) to perform: - Conversion of location and time information into vector format - Generation of code vector using transformation - Sorting according to a predetermined scheme - Random modification of sorted entries - Comparison with other code vectors - Determination of distance and proximity identification based on that distance
In summary, the inventive features focus on a privacy-preserving method for encoding time and location data, structured processing on both client and server devices, and implementation as a device with instructions for vector transformation, sorting, modification, and matching for proximity detection.
Stated Advantages
The system preserves user privacy by encrypting location data in such a way that the original data cannot be feasibly recovered from the code vector.
Perfect recall is guaranteed for applications like contact tracing, ensuring all individuals potentially exposed are alerted while the probability of false positives (false alarms) is negligible.
The encryption is keyless, requiring no private or public keys, increasing security and simplifying implementation.
The system enables proximity detection between devices without disclosing users' absolute locations, addressing privacy concerns that have limited adoption of previous methods.
The encrypted code vectors appear statistically random, making it very difficult to distinguish or invert them back to the original location and time information.
Documented Applications
Contact tracing to control the spread of infectious diseases, such as COVID-19, by identifying and alerting individuals who have been in proximity to someone reporting an infection.
Any application where data hiding of spatio-temporal or similar sensitive information is required for privacy reasons.
Interested in licensing this patent?