私有信息檢索

密碼學私有信息檢索(英語:Private information retrieval,PIR)協議令用戶可以在不披露下載項目的同時,從持有數據庫的伺服器下載項目。 PIR亦可視為一種弱化的n選1不經意傳輸(OT),但有區別,在於OT亦要求用戶不得獲得其他數據項目的信息。

一種平凡但效率奇低的PIR可以通過讓伺服器複製整個數據庫,然後傳送給用戶實現。實際上,單伺服器(不論是經典或量子)設定下,這是唯一能信息學安全地保護用戶查詢的方案。有兩種方式應對這個問題:要麼假設伺服器計算能力有限英語Computationally bounded adversary,要麼假設有若干個相互不串通的伺服器,而各伺服器持有一份數據庫的備份。

該問題的信息論版本於1995年由本尼·楚爾奧德·戈德里克埃亞爾·庫希列維茲邁度·蘇丹引入[1]計算版本則於1997年由埃亞爾·庫希列維茲拉斐爾·奧斯特洛夫斯基提出[2]。之後又有研究者提出了理論上非常高效的方案。單伺服器(計算安全)PIR只須(均攤)常數通信 ,而k—伺服器(信息學安全)PIR則可用 通訊完成(但下界仍然是近乎線性的量級[3])。

參考資料

編輯
  1. ^ Chor, Benny; Kushilevitz, Eyal; Goldreich, Oded; Sudan, Madhu. Private information retrieval (PDF). Journal of the ACM. 1 November 1998, 45 (6): 965–981 [2021-08-13]. doi:10.1145/293347.293350. (原始內容 (PDF)存檔於2021-11-11). 
  2. ^ Kushilevitz, Eyal; Ostrovsky, Rafail. Replication is not needed: single database, computationally-private information retrieval. Proceedings of the 38th Annual Symposium on Foundations of Computer Science. Miami Beach, Florida, USA: IEEE Computer Society. 1997: 364–373. ISBN 978-0-8186-8197-4. doi:10.1109/SFCS.1997.646125. 
  3. ^ Vaikuntanathan, Vinod. Some Open Problems in Information-Theoretic Cryptography. 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik: 5:1––5:7. 2018. ISBN 978-3-95977-055-2. doi:10.4230/LIPIcs.FSTTCS.2017.5.