EMRQ: An Efficient Multi-keyword Range Query Scheme in Smart Grid Auction Market

Hongwei Li, Yi Yang, Mi Wen, Hongwei Luo, Rongxing Lu

Abstract

In the evolving landscape of smart grids, energy auctions between generators and retailers require robust privacy protections for sensitive trade data, such as pricing strategies and available volumes. Existing searchable encryption schemes often struggle with the flexibility required for real-world trading, such as range queries and ranked searches. This paper presents EMRQ (Efficient Multi-keyword Range Query), a privacy-preserving auction scheme that utilizes homomorphic encryption and super-increasing sequences. EMRQ enables a data center to compare a buyer's requirements against all sellers' offers in a single calculation, significantly reducing computational overhead while maintaining query privacy.

Introduction

Modern smart grids facilitate efficient electricity trading between generators (sellers) and retailers (buyers). However, these transactions involve "trade secrets" that participants are reluctant to disclose to third-party service providers. While searchable encryption offers a path toward privacy, most current implementations are limited to exact-match queries. In practice, buyers need to perform range queries (e.g., "Find energy priced between $10 and $12") and rank results based on personalized priorities like location or volume.

EMRQ addresses these challenges by providing a scheme that supports multi-keyword range queries and ranked searches simultaneously, without exposing the underlying sensitive data to the processing entities.

System Architecture

The EMRQ framework involves four primary entities: Electricity Generators, Retailers, a Data Center, and a Filtering Center. The interaction between these entities ensures that data remains encrypted throughout the auction process.

The EMRQ system model illustrating the flow of tags, trapdoors, and results between generators, retailers, and centers.

As shown in the system model, Electricity Generators send encrypted "Tags" representing their energy offers to the Data Center. Retailers submit "Trapdoors" (encrypted queries) to the Data Center. The Data Center then performs the matching calculations and coordinates with the Filtering Center to identify the "Winner" without either center learning the specific values of the bids or queries.

Methodology

The EMRQ scheme is built upon three mathematical pillars designed to optimize both security and performance:

  1. Paillier Cryptosystem: This homomorphic encryption method allows the Data Center to perform additions on encrypted data without decryption.
  2. Super-increasing Sequences: This is the core innovation of the scheme. Two distinct sequences are used to "pack" multi-dimensional keywords into single values. This allows for the aggregation of a seller's keywords (price, quantity, etc.) and the subsequent aggregation of all sellers' data into a single "summary number."
  3. One-Shot Comparison: By leveraging the properties of super-increasing sequences, the Data Center can compare a buyer’s trapdoor against the entire pool of sellers in one calculation, moving away from traditional $O(N)$ linear comparisons.

To maintain clarity across these complex operations, the paper utilizes a specific set of notations for identities, keywords, and sequences.

Table of notations and meanings used in the EMRQ scheme.

Handling Complex Queries

A common challenge in super-increasing sequence applications is handling negative differences during range queries. EMRQ introduces a specialized algorithm to "split the aggregation," ensuring that negative results from boundary comparisons are handled correctly without compromising the efficiency of the one-shot calculation.

Performance and Key Results

The authors evaluated EMRQ using simulated experimental data implemented with the MIRACL library. The results highlight several key advantages:

  • Functional Superiority: EMRQ is the first scheme to simultaneously support multi-keyword search, range queries, ranked search, and personalized search (via buyer-assigned weights).
  • Computational Efficiency: In simulations with up to 1,000 participants, EMRQ’s computational overhead remained relatively linear and significantly lower than competing schemes like SESA, which showed exponential overhead spikes at scale.
  • Communication Gains: By aggregating tags into a single value, EMRQ reduces the total bits transmitted per auction cycle compared to non-aggregated schemes.

Conclusion

EMRQ provides a highly efficient and functional solution for privacy-preserving auctions in smart grids. By reducing the matching process to a one-shot comparison, it overcomes the scalability issues of previous searchable encryption models. Future research may focus on reducing the reliance on a fully trusted Filtering Center to further harden the system against adversarial environments.

Summary updated

Abstract

KSII Transactions on Internet and Information Systems
BibTeX
@article{li2014emrq,
  author = {Hongwei Li and Yi Yang and Mi Wen and Hongwei Luo and Rongxing Lu},
  title = {{EMRQ: An Efficient Multi-keyword Range Query Scheme in Smart Grid Auction Market}},
  journal = {KSII Trans. Internet Inf. Syst.},
  year = {2014},
  doi = {10.3837/tiis.2014.11.015},
}
Figure