论文标题
treepir：通过快速索引和零存储开销的树色有效地检索默克尔的证明
TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead
论文作者
论文摘要
批处理私有信息检索（批处理PIR）方案允许客户端从数据库中检索多个数据项，而无需向存储服务器揭示它们。大多数现有的批量PIR方法都是基于批处理代码，尤其是概率批处理代码（PBC）（Angel等人S＆p'18），该代码会产生大型存储开销。在这项工作中，我们表明\ textIt {Zero}存储开销是可以实现树状数据库的。特别是，我们开发了Treepir，这是一种量身定制的新型方法，该方法是为沿默克尔树中任意的根到叶子路径的私人检索而制定的，没有存储冗余。这种类型的树已在许多现实世界中广泛实现，例如Amazon DynamoDB，Google的证书透明度和区块链。沿根到叶路径的树节点形成了众所周知的默克尔证明。使用一种新颖的树着色的Treepir优于PBC，这是最先进的批量PIR计划中的基本组成部分（Angel等人S＆P'18，Mughees-ren s＆p'23，Liu等人等级S＆p'24），在所有衡量标准中，总计$ 3 \ $ 3 \ $ $ $ $ $ - $ 1.5 $ 1.5 $ 1.5 $ 1.5 $ 1.5 $ 1.5 $ 1.5 $ 1.5 tiese $ 1.5次。最值得注意的是，Treepir具有$ 8 $ - $ 160 \ times $ $较低的设置时间，其Polylog-complexity索引算法为$ 19 $ - $ 160 \ times \ times $ $ $ $ $ $ $ $ $ $ $ $ 2^{10} $ 2} $ - $ 2^{24} $ sever。
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 \textit{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\times$ lower total storage and $1.5$-$2\times$ lower computation and communication costs. Most notably, TreePIR has $8$-$160\times$ lower setup time and its polylog-complexity indexing algorithm is $19$-$160\times$ faster than PBC for trees of $2^{10}$-$2^{24}$ leaves.
