2022/05/11 by Dau, Son Hoang, Cao, Quang, Gagiano, Rinaldo +9
#05C05 #05C15 #05C85 #05C90 #Combinatorics (math.CO) #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #E.1 #F.2.0 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2205.05211
A Batch Private Information Retrieval (batch-PIR) scheme allows a client to retrieve multiple data items from a database without revealing them to the storage server(s). Most existing approaches for batch-PIR are based on batch codes, in particular, probabilistic batch codes (PBC) (Angel et al. S&P'18), which incur large storage overheads. In this work, we show that zero storage overhead is achievable for tree-shaped databases. In particular, we develop TreePIR, a novel approach tailored made for private retrieval of the set of nodes along an arbitrary root-to-leaf path in a Merkle tree with no storage redundancy. This type of trees has been widely implemented in many real-world systems such as Amazon DynamoDB, Google's Certificate Transparency, and blockchains. Tree nodes along a root-to-leaf path forms the well-known Merkle proof. TreePIR, which employs a novel tree coloring, outperforms PBC, a fundamental component in state-of-the-art batch-PIR schemes (Angel et al. S&P'18, Mughees-Ren S&P'23, Liu et al. S&P'24), in all metrics, achieving 3× lower total storage and 1.5-2× lower computation and communication costs. Most notably, TreePIR has 8-160× lower setup time and its polylog-complexity indexing algorithm is 19-160× faster than PBC for trees of 210-224 leaves.