Authenticated Private Information Retrieval for Range Queries
TL;DR
This work presents an Authenticated Private Information Retrieval protocol for range queries with guarantees of soundness and completeness, and introduces the APIR-tree, a novel authenticated data structure that embeds values at every node, enabling nodes to serve as VOs for their ancestors and eliminating redundancy.
Abstract
: We study the problem of enabling users to perform range queries over a cloud-managed database without revealing which records are retrieved, while also allowing users to verify the correctness of the returned results. Existing approaches support either query privacy through Private Information Retrieval (PIR) or query result authentication through Authenticated Data Structures (ADSs), but not both simultaneously for range queries. To address this problem, we present an Authenticated Private Information Retrieval (APIR) protocol for range queries with guarantees of soundness and completeness. We first propose a baseline scheme that combines PIR with Merkle Hash Trees (MH-trees), achieving authenticated query processing but incurring high communication and storage overhead due to redundant verification objects (VOs). To improve efficiency, we further introduce the APIR-tree , a novel authenticated data structure that embeds values at every node, enabling nodes to serve as VOs for their ancestors and eliminating redundancy. Simulation results show that the APIR-tree reduces storage overhead by up to 25 × and communication costs by an order of magnitude while preserving strong privacy and authenticity guarantees.