TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909216095076352 |
|---|---|
| author | Dau, Son Hoang Cao, Quang Gagiano, Rinaldo Huynh, Duy Yi, Xun Le, Phuc Lu Luu, Quang-Hung Viterbo, Emanuele Huang, Yu-Chih Zhu, Jingge Jalalzai, Mohammad M. Feng, Chen |
| author_facet | Dau, Son Hoang Cao, Quang Gagiano, Rinaldo Huynh, Duy Yi, Xun Le, Phuc Lu Luu, Quang-Hung Viterbo, Emanuele Huang, Yu-Chih Zhu, Jingge Jalalzai, Mohammad M. Feng, Chen |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_05211 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead Dau, Son Hoang Cao, Quang Gagiano, Rinaldo Huynh, Duy Yi, Xun Le, Phuc Lu Luu, Quang-Hung Viterbo, Emanuele Huang, Yu-Chih Zhu, Jingge Jalalzai, Mohammad M. Feng, Chen Data Structures and Algorithms Cryptography and Security Combinatorics 05C05, 05C15, 05C85, 05C90, G.2.2; F.2.0; E.1 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. |
| title | TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead |
| topic | Data Structures and Algorithms Cryptography and Security Combinatorics 05C05, 05C15, 05C85, 05C90, G.2.2; F.2.0; E.1 |
| url | https://arxiv.org/abs/2205.05211 |