TL;DR
This paper introduces a novel protocol for securely measuring the similarity between datasets collected in smart environments, ensuring differential privacy for users. It allows multiple similarity queries on the same data without re-executing the entire protocol, addressing a key limitation of prior work.
What Problem Does This Paper Address?
Smart environments, powered by ubiquitous sensors and interconnected devices, collect vast amounts of personal data to enhance user experience. However, this data collection raises significant privacy concerns, as it can contain sensitive information. When multiple "agents" (software entities) in these environments need to compare their collected data to understand patterns or adapt the environment, they face a dilemma: how to perform these comparisons securely without revealing sensitive user data. Existing methods for similarity measurement often lack robust privacy guarantees or require significant modifications for different similarity metrics. This paper tackles the challenge of enabling secure, privacy-preserving similarity measurement between datasets held by different agents, specifically focusing on binary data and using similarity coefficients as the metric.
Methods
The core of the proposed solution is a two-party computation protocol that leverages homomorphic encryption and a semitrusted "anonymizer" agent. The protocol involves several phases:
- Key Generation: The anonymizer generates an ElGamal cryptosystem key pair and shares the public key.
- Data Transformation and Encryption (Alice): The "requestor" (Alice) transforms her binary dataset (X) by replacing '1's with a random prime 't' and '0's with its inverse 't⁻¹'. She then encrypts these transformed values and 't' using the public key and sends the encrypted data and 't' to the "supporter" (Bob) and the anonymizer.
- Data Transformation and Encryption (Bob): The supporter (Bob) transforms his binary dataset (Y) by replacing '1's with 't²' and '0's with 't'. He then encrypts these transformed values.
- Homomorphic Multiplication and Shuffling: Bob uses the homomorphic property of ElGamal encryption to multiply the encrypted transformed values from Alice and Bob element-wise. This effectively computes an encrypted representation of the product of the original binary values (xᵢyᵢ). Bob then shuffles these encrypted products to obscure their original order and sends them to the anonymizer.
- Decryption and Summation: The anonymizer decrypts the shuffled encrypted products and the encrypted 't'. By examining the decrypted values and comparing them to powers of 't', the anonymizer can efficiently compute the summation variables (a, b, c, d) that define the similarity coefficients without learning the original datasets X or Y.
- Similarity Computation and Noise Addition: For any requested similarity coefficient (F_SC), the anonymizer computes the exact value using the derived summation variables. Crucially, it then adds Laplacian noise, scaled by the coefficient's global sensitivity (ΔF_SC) and a privacy parameter (ε), to the result. This noisy result is then sent to the requestor.
A key innovation is that Phase 5, where the similarity is computed and noise is added, can be repeated for different F_SC requests using the same pre-computed encrypted data from Phases 1-4, avoiding redundant computations.
Datasets
The paper does not explicitly mention or use specific real-world datasets for evaluation. The methodology is demonstrated using binary datasets represented as X = {xᵢ | i = 1, 2, ..., n} and Y = {yᵢ | i = 1, 2, ..., n}, where xᵢ, yᵢ ∈ {0, 1}.
Key Insights and Ideas
- Flexible Similarity Queries: The protocol's ability to handle multiple similarity coefficient requests (F_SC) without re-executing the initial data transformation and encryption phases is a significant advantage. This makes it highly practical for scenarios where various similarity metrics might be needed.
- Leveraging Homomorphic Encryption for Privacy: The clever use of ElGamal's multiplicative homomorphic property allows computations on encrypted data, ensuring that neither the supporter nor the anonymizer learns the raw input datasets.
- Differential Privacy as a Strong Guarantee: By adding calibrated Laplacian noise, the protocol achieves differential privacy. This means that the output of the similarity computation is statistically indistinguishable whether a single user's data is included or excluded, providing a robust privacy guarantee against adversaries with auxiliary information.
- Role of the Semitrusted Anonymizer: The anonymizer acts as a crucial intermediary, performing the sensitive decryption and computation while being trusted not to reveal the raw inputs. Its role is essential for enabling secure computation between the two data owners.
Key Results
The paper focuses on the protocol's design and security properties rather than presenting quantitative experimental results on specific datasets. The key results are:
- Correctness: The protocol correctly computes the summation variables (a, b, c, d) and subsequently any similarity coefficient (F_SC) based on these variables, assuming semihonest behavior from all parties.
- Privacy: The protocol ensures differential privacy for the input datasets. The requestor's view is simulated by their input and output, and the supporter's view is simulated by their input and output, demonstrating indistinguishability from real execution under the semihonest model.
- Efficiency: The protocol avoids re-executing the initial phases for subsequent similarity queries, offering a potential efficiency gain over methods that require full re-computation.
Limitations and Future Work
- Semihonest Adversary Model: The current protocol is designed for semihonest adversaries (honest-but-curious). It does not explicitly address the malicious adversary model, where parties might actively deviate from the protocol to gain an advantage.
- Binary Data Focus: The protocol is specifically designed for binary datasets. Extending it to handle non-binary or categorical data would require further research.
- Computational Overhead: While more efficient for multiple queries, homomorphic encryption inherently introduces computational overhead. The paper does not provide detailed performance benchmarks.
- Future Work: The authors suggest that the same solution can be applied to other related areas like pervasive or ubiquitous computing and intelligent environments. Further research could explore extending the protocol to handle malicious adversaries and different data types.
Summary updated