私有信息检索

密码学私有信息检索(英语: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.