查看“︁私有信息檢索”︁的源代码

在[[密碼學]]，'''私有信息檢索'''（英語：Private information retrieval，PIR）協議令用戶可以在不披露下載項目的同時，從持有[[数据库|數據庫]]的伺服器下載項目。 PIR亦可視為一種弱化的n選1[[不经意传输|不經意傳輸]]（OT），但有區別，在於OT亦要求用户不得獲得其他數據項目的信息。

一種平凡但效率奇低的PIR可以通過讓伺服器複製整個數據庫，然後傳送給用戶實現。實際上，單伺服器（不論是經典或[[量子計算|量子]]）設定下，這是唯一能[[資訊理論安全性|信息學安全]]地保護用戶查詢的方案。有兩種方式應對這個問題：要麼假設伺服器{{Internal link helper/en|計算能力有限|Computationally bounded adversary}}，要麼假設有若干個相互不串通的伺服器，而各伺服器持有一份數據庫的備份。

該問題的信息論版本於1995年由[[Benny Chor|本尼·楚爾]]，[[Oded Goldreich|奧德·戈德里克]]，[[Eyal Kushilevitz|埃亞爾·庫希列維茲]]和[[Madhu Sudan|邁度·蘇丹]]引入<ref name="ChoKusGolSud98">{{cite journal|title=Private information retrieval|url=http://www.tau.ac.il/~bchor/PIR.pdf|last=Chor|first=Benny|date=1 November 1998|journal=Journal of the ACM|issue=6|doi=10.1145/293347.293350|volume=45|pages=965–981|author3=Goldreich, Oded|author4=Sudan, Madhu|author2=Kushilevitz, Eyal|access-date=2021-08-13|archive-date=2021-11-11|archive-url=https://web.archive.org/web/20211111044714/https://www.tau.ac.il/~bchor/PIR.pdf}}</ref>，{{Internal link helper/en|計算|Computationally bounded adversary}}版本則於1997年由[[Eyal Kushilevitz|埃亞爾·庫希列維茲]]和[[Rafail Ostrovsky|拉斐爾·奧斯特洛夫斯基]]提出<ref name="KusOst97">{{cite book|last=Kushilevitz|first=Eyal|title=Proceedings of the 38th Annual Symposium on Foundations of Computer Science|date=1997|publisher=IEEE Computer Society|location=Miami Beach, Florida, USA|isbn=978-0-8186-8197-4|pages=364–373|author2=Ostrovsky, Rafail|chapter=Replication is not needed: single database, computationally-private information retrieval|doi=10.1109/SFCS.1997.646125}}</ref>。之後又有研究者提出了理論上非常高效的方案。單伺服器（計算安全）PIR只須（均攤）常數通信 ，而''k—''伺服器（信息學安全）PIR則可用 <math>n^{O\left(\frac{\log \log k}{k \log k}\right)}</math>通訊完成（但下界仍然是近乎線性的量級<ref>{{cite conference|last=Vaikuntanathan|first=Vinod|title=Some Open Problems in Information-Theoretic Cryptography|date=2018|publisher=Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik|location=Dagstuhl, Germany|isbn=978-3-95977-055-2|pages=5:1--5:7|booktitle=37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)|doi=10.4230/LIPIcs.FSTTCS.2017.5}}</ref>）。

== 参考资料 ==
{{reflist}}

[[Category:密碼原語]]
[[Category:密碼學理論]]