Score:0

Concrete attacks on Private Information Retrieval (PIR)

cn flag

Private Information Retrieval (PIR) protocols have been studied for years. The following question only regards to the single server scenario.

Assume there are $N$ items in total on the server side, according to the security definition, it seems that all $N$ items should be "touched" (either in terms of communication or computation) for security reasons. But since $N$ is usually large, someone may ask what kind of CONCRETE ATTACKs exist when only "touching" a smaller $n\ll N$.

For example, let the server uses a hash function $h$ on each item $x$, and only use the first $\alpha$ bits of $h(x)$ to identify $n$ items with the same $\alpha$-bit prefix to filtering $n$ data items out. Then, perform PIR on these $n$ items instead of all $N$ items on the server.

PS: I know the above method is theoretically incorrect (cheating), but I cannot come up with a very good explanation or strong counter-example to illustrate there would exist severe security flaws for those who are not experts in security and cryptography.

kelalaka avatar
in flag
This FHE circuit is a binary tree and optimal. [Bandwidth Efficient PIR from NTRU](https://pdfs.semanticscholar.org/bfde/352ba1bdb70bf850b18a08c9da092489b698.pdf)
cn flag
Thanks for your answer, but actually my biggest question is the “attack” part
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.