A Stateless PIR Protocol for Root-Aligned Wildcard Prefix-Set Retrieval Based on Compact Trie and Homomorphic Encryption

Private information retrieval (PIR) enables a client to retrieve records from a server-hosted database without revealing the requested item. Most high-performance single-server PIR systems are optimized for exact index or keyword lookup, whereas controlled-vocabulary and structured-identifier applications may require a partially specified root-aligned prefix with per-position wildcards. This paper presents a stateless protocol for that restricted but practically relevant retrieval model. The construction combines a compact trie with leveled Brakerski–Gentry–Vaikuntanathan (BGV) homomorphic encryption, ciphertext–plaintext equality testing, single-instruction multiple-data (SIMD) packing, compressed-edge batching, and power-of-two slot rotations. The client stores no database-dependent hint, and the server stores no persistent client-specific evaluation material; all the query ciphertexts and required evaluation keys are uploaded in the online phase. We explicitly position the construction as a protocol-level integration for richer private retrieval semantics rather than as a new foundational PIR or homomorphic-encryption primitive. Security is formulated for an honest-but-curious single-query adversary under an explicit public leakage function covering trie topology, compressed-edge lengths, payload layout, query-upload shape, and the fixed response schedule. We further analyze broad wildcard queries: the match cardinality can reach the number of indexed keys, while the number of response ciphertexts is determined by public output capacity rather than by the private query. Experiments on three controlled synthetic datasets and one anonymized enterprise dataset show that compact trie compression and packed edge evaluation reduce server-side online latency relative to uncompressed and serial homomorphic baselines, with the largest gains on high-prefix-sharing workloads. The implementation achieves exact set-level agreement with a plaintext oracle at two wildcard densities while exposing an explicit trade-off among richer query semantics, stateless deployment, public structural leakage, and communication overhead.