Report
Optimizing Leaky Private Information Retrieval Codes to Achieve ${O}(\log K)$ Leakage Ratio Exponent
| العنوان: | Optimizing Leaky Private Information Retrieval Codes to Achieve ${O}(\log K)$ Leakage Ratio Exponent |
|---|---|
| المؤلفون: | Zhao, Wenyuan, Huang, Yu-Shin, Tian, Chao, Sprintson, Alex |
| سنة النشر: | 2025 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Information Retrieval, Computer Science - Information Theory |
| الوصف: | We study the problem of leaky private information retrieval (L-PIR), where the amount of privacy leakage is measured by the pure differential privacy parameter, referred to as the leakage ratio exponent. Unlike the previous L-PIR scheme proposed by Samy et al., which only adjusted the probability allocation to the clean (low-cost) retrieval pattern, we optimize the probabilities assigned to all the retrieval patterns jointly. It is demonstrated that the optimal retrieval pattern probability distribution is quite sophisticated and has a layered structure: the retrieval patterns associated with the random key values of lower Hamming weights should be assigned higher probabilities. This new scheme provides a significant improvement, leading to an ${O}(\log K)$ leakage ratio exponent with fixed download cost $D$ and number of servers $N$, in contrast to the previous art that only achieves a $\Theta(K)$ exponent, where $K$ is the number of messages. Comment: Long version of the paper submitted to ISIT 2025. 8 pages, 2 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2501.12310 |
| رقم الانضمام: | edsarx.2501.12310 |
| قاعدة البيانات: | arXiv |
| ResultId |
1 |
|---|---|
| Header |
edsarx arXiv edsarx.2501.12310 1147 3 Report report 1146.55249023438 |
| PLink |
https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsarx&AN=edsarx.2501.12310&custid=s6537998&authtype=sso |
| FullText |
Array
(
[Availability] => 0
)
Array ( [0] => Array ( [Url] => http://arxiv.org/abs/2501.12310 [Name] => EDS - Arxiv [Category] => fullText [Text] => View record in Arxiv [MouseOverText] => View record in Arxiv ) ) |
| Items |
Array
(
[Name] => Title
[Label] => Title
[Group] => Ti
[Data] => Optimizing Leaky Private Information Retrieval Codes to Achieve ${O}(\log K)$ Leakage Ratio Exponent
)
Array ( [Name] => Author [Label] => Authors [Group] => Au [Data] => <searchLink fieldCode="AR" term="%22Zhao%2C+Wenyuan%22">Zhao, Wenyuan</searchLink><br /><searchLink fieldCode="AR" term="%22Huang%2C+Yu-Shin%22">Huang, Yu-Shin</searchLink><br /><searchLink fieldCode="AR" term="%22Tian%2C+Chao%22">Tian, Chao</searchLink><br /><searchLink fieldCode="AR" term="%22Sprintson%2C+Alex%22">Sprintson, Alex</searchLink> ) Array ( [Name] => DatePubCY [Label] => Publication Year [Group] => Date [Data] => 2025 ) Array ( [Name] => Subset [Label] => Collection [Group] => HoldingsInfo [Data] => Computer Science<br />Mathematics ) Array ( [Name] => Subject [Label] => Subject Terms [Group] => Su [Data] => <searchLink fieldCode="DE" term="%22Computer+Science+-+Information+Retrieval%22">Computer Science - Information Retrieval</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Information+Theory%22">Computer Science - Information Theory</searchLink> ) Array ( [Name] => Abstract [Label] => Description [Group] => Ab [Data] => We study the problem of leaky private information retrieval (L-PIR), where the amount of privacy leakage is measured by the pure differential privacy parameter, referred to as the leakage ratio exponent. Unlike the previous L-PIR scheme proposed by Samy et al., which only adjusted the probability allocation to the clean (low-cost) retrieval pattern, we optimize the probabilities assigned to all the retrieval patterns jointly. It is demonstrated that the optimal retrieval pattern probability distribution is quite sophisticated and has a layered structure: the retrieval patterns associated with the random key values of lower Hamming weights should be assigned higher probabilities. This new scheme provides a significant improvement, leading to an ${O}(\log K)$ leakage ratio exponent with fixed download cost $D$ and number of servers $N$, in contrast to the previous art that only achieves a $\Theta(K)$ exponent, where $K$ is the number of messages.<br />Comment: Long version of the paper submitted to ISIT 2025. 8 pages, 2 figures ) Array ( [Name] => TypeDocument [Label] => Document Type [Group] => TypDoc [Data] => Working Paper ) Array ( [Name] => URL [Label] => Access URL [Group] => URL [Data] => <link linkTarget="URL" linkTerm="http://arxiv.org/abs/2501.12310" linkWindow="_blank">http://arxiv.org/abs/2501.12310</link> ) Array ( [Name] => AN [Label] => Accession Number [Group] => ID [Data] => edsarx.2501.12310 ) |
| RecordInfo |
Array
(
[BibEntity] => Array
(
[Subjects] => Array
(
[0] => Array
(
[SubjectFull] => Computer Science - Information Retrieval
[Type] => general
)
[1] => Array
(
[SubjectFull] => Computer Science - Information Theory
[Type] => general
)
)
[Titles] => Array
(
[0] => Array
(
[TitleFull] => Optimizing Leaky Private Information Retrieval Codes to Achieve ${O}(\log K)$ Leakage Ratio Exponent
[Type] => main
)
)
)
[BibRelationships] => Array
(
[HasContributorRelationships] => Array
(
[0] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Zhao, Wenyuan
)
)
)
[1] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Huang, Yu-Shin
)
)
)
[2] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Tian, Chao
)
)
)
[3] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Sprintson, Alex
)
)
)
)
[IsPartOfRelationships] => Array
(
[0] => Array
(
[BibEntity] => Array
(
[Dates] => Array
(
[0] => Array
(
[D] => 21
[M] => 01
[Type] => published
[Y] => 2025
)
)
)
)
)
)
)
|
| IllustrationInfo |