Private and efficient set intersection protocol for RFID-based food adequacy check

Zakaria Gheid, Yacine Challal, Lin Chen2018 · DOI

TL;DR

This paper introduces a novel RFID-based system called FAC (Food Adequacy Check) for grocery stores, enabling shoppers to privately verify if food items match their dietary preferences. They propose a new, efficient Private Set Intersection (PSI) protocol that uses matrix algebra instead of heavy cryptography, achieving linear complexity and demonstrating significant performance improvements over existing methods.

What Problem Does This Paper Address?

In today's retail landscape, especially with the rise of smart technologies like RFID, there's a growing opportunity to enhance the customer experience. One such area is personalized shopping, particularly for individuals with specific dietary needs (e.g., diabetes, gluten-free diets). While RFID tags can identify products, a significant challenge arises in privately matching these products against a shopper's detailed personal preferences stored on a backend server. Traditional methods for this kind of matching can be computationally expensive and may compromise shopper privacy, especially if the server is "curious" or if the service is paid. This paper tackles the problem of enabling efficient and private food item adequacy checks in a retail setting, ensuring both shopper privacy and system performance.

Methods

The core of the proposed solution is a novel Private Set Intersection (PSI) protocol, dubbed I-FAC. Instead of relying on traditional cryptographic operations like homomorphic encryption or oblivious polynomial evaluation, I-FAC employs a matrix-based approach. The client's set of preferences (X) and the server's set of item profiles (Y) are represented as row matrices. Each party then obfuscates their matrix by multiplying it with a randomly generated invertible matrix. The key innovation lies in how these obfuscated matrices are exchanged and processed. The protocol cleverly uses the non-commutative property of matrix multiplication, requiring parties to interchange the order of multiplication. This allows for the secure computation of the intersection without revealing the underlying sets. The protocol is designed to be secure against both active client corruption and passive server corruption, using a mixed model of adversaries.

Datasets

Not discussed in the paper. The paper focuses on a simulated scenario for evaluating the performance of their proposed protocol.

Key Insights and Ideas

  • Matrix Algebra for Privacy: The most striking insight is the successful application of matrix algebra for achieving private set intersection, bypassing the need for computationally intensive cryptographic primitives. This significantly boosts efficiency.
  • Efficiency Through Simplicity: By avoiding complex cryptographic operations, the protocol achieves a linear asymptotic complexity (O(v + c)), making it highly scalable for large supermarkets with many items and customer profiles.
  • Mixed Adversary Model: The protocol's security proof in the mixed model (active client, passive server) is crucial for real-world deployment, as it accounts for realistic threat scenarios.
  • Practical RFID Application: The paper demonstrates a concrete and valuable application of RFID technology beyond simple inventory management, directly enhancing the consumer experience.

Key Results

The paper presents strong empirical results demonstrating the superiority of the I-FAC protocol over a hash-based PSI solution.

  • Performance: In simulations, I-FAC consistently outperformed the hash-based protocol across various metrics, including usability rate, response time, and queue length.
  • Scalability: For low arrival rates, I-FAC showed very low server utilization and response times. Even at high arrival rates (over 100 requests/min), I-FAC maintained efficiency with a usability rate below 50% and a response time under 4 ms, while the hash-based protocol became overloaded.
  • Complexity: The I-FAC protocol achieves a linear asymptotic complexity of O(v + c) for communications and server-side computations, where 'v' is the number of item profiles and 'c' is the number of shopper profiles.

Limitations and Future Work

  • Security Proof: While the paper provides a standard security proof against active client and passive server corruption, it assumes that if both parties are corrupted, security guarantees are not required.
  • Simulation-Based Evaluation: The performance analysis is based on simulations using a queueing theory model (M/M/1). Real-world deployment might introduce additional complexities.
  • Future Work: The authors suggest that their protocol is well-suited for large-scale supermarkets, implying that further testing and optimization for diverse retail environments could be beneficial. Exploring security against more advanced adversary models could also be a future direction.

Summary updated

Abstract

Radio Frequency Identification (RFID) is a technology for automatic object identification that has been implemented in several real-life applications. In this work, we expand a novel relevant application of RFID tags for grocery stores, which aims to check the adequacy of food items with respect to the shoppers' personal preferences. Unlike similar works, we focus on shoppers' privacy and running time efficiency. For this aim, we propose a novel private set intersection (PSI) protocol to be used in matching the shoppers' personal preferences with the set of each item's adequate profiles that are held by the back-end server of the store. We provide a standard security proof against curious stores and malicious customers. For efficiency concern, we build our protocol without cryptographic operations, and we achieve a linear asymptotic complexity of O (v + c) for communications and store-side computations, where v and c are the numbers of profiles in the store's back-end server and the shopper's list of preferences respectively. Moreover, experimental results and comparisons with state-of-the art solutions reveal the scalability of our novel PSI protocol for big market stores.
BibTeX
@misc{gheid2018private,
  author = {Zakaria Gheid and Yacine Challal and Lin Chen},
  title = {{Private and efficient set intersection protocol for RFID-based food adequacy check}},
  year = {2018},
  doi = {10.1109/wcnc.2018.8377207},
}
Figure