Paper 2026/2082

Incremental Keyword Private Information Retrieval from d-ary Segmented Cuckoo Filters

Abstract

We introduce RisePIR, the first preprocessing keyword private information retrieval (PIR) scheme that absorbs insert, update, and delete on its key-value store at a cost proportional to the number of mutations alone. Where the static state-of-the-art schemes ChalametPIR and $\mathsf{KPIR}^{\mathsf{index}}$ re-run their preprocessing from scratch on every change, RisePIR patches its preprocessing in place and stays as practical as both in the online phase. We give a generic construction of incremental preprocessing keyword PIR from any updatable preprocessing index PIR, an index PIR that efficiently supports in-place update. The construction rests on our $d$-ary Segmented Cuckoo Filter, a cuckoo filter that confines the $j$-th candidate bucket of every key to the $j$-th of $d$ segments and stays dynamic under partial-key cuckoo hashing. Instantiating the construction over FrodoPIR and SimplePIR, each equipped with the entry-level hint patch of iSimplePIR, gives RisePIR-F and RisePIR-S, both secure under decisional LWE. On a store of about one million keys, both variants patch their hint in place in 0.06–4.7 ms per mutation, five to six orders of magnitude faster than the 56–686 s full re-run of the preprocessing phase. Their online phase stays competitive with ChalametPIR and $\mathsf{KPIR}^{\mathsf{index}}$ in both asymptotic and concrete cost. We deploy RisePIR-S as a privacy-preserving eth_getBalance service over the $2.05 \times 10^{8}$ accounts of Ethereum mainnet, so that a wallet reads a balance without revealing to its RPC provider which account it holds. The running service answers a private query in 0.69 s and absorbs each block's changes in 5.6 ms, well inside the 12 s block interval. The filter and RisePIR ship as an open-source Rust implementation, together with the benchmark harness behind every number in this paper.

Note: Full version of the paper accepted at CANS 2026.