Оптимизация конфиденциальных запросов к базе данных на облаке

Авторами рассматривается задача PIR (Private Information Retrieval) обеспечения безопасных запросов к базе данных, размещенной на облаке при наличии активного противника, который не вмешивается в выполнение протокола, но может производить атаку с известными открытыми запросами. Для представления номера бита i в виде числа, все цифры которого различны, в предложенных алгоритмах применяется система счисления по основанию l с числом разрядов d. Использование перестановок цифр номера запрашиваемого бита в качестве секретных ключей шифрования уменьшает вероятность угадывания номера бита. Хранящиеся на облаке биты исходной базы данных группируются в виде массивов, что позволяет снизить коммуникационную сложность. Используется датчик псевдослучайных чисел для замены значения бита в зависимости от запрашиваемого клиентом номера бита i. Это позволяет в случае сговора пассивного противника, находящегося на облаке, и активного противника вне облака, затруднить сопоставление значения бита конкретному номеру. Приведены оценки коммуникационной сложности, вероятности угадывания номера бита при однократной атаке с известным открытым запросом номера бита i и при атаке с неограниченным числом известных открытых запросов.

1. Мартишин С.А., Храпченко М.В., Шокуров А.В. Организация безопасного запроса к базе данных на облаке. Труды Института системного программирования РАН. Том 34, № 3, 2022г., с. 173-188, ISSN 2079-8156 (Print), ISSN 2220-6426 (Online).

2. Варновский Н.П., Мартишин С.А., Храпченко М.В., Шокуров А.В. Организация конфиденциальных запросов к облаку. Труды Института системного программирования РАН. Том 35, выпуск 5, 2023, с. 37-54, ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

3. Chor B., Goldreich O., Kushilevitz E., Sudan M. Private Information Retrieval, in IEEE Annual Symposium on Foundations of Computer Science, 1995, pp. 41–50.

4. Chor B., Goldreich O., Kushilevitz E., Sudan M. Private Information Retrieval, Journal of the ACM, Vol. 45, No. 6, November 1998, pp. 965–982.

5. Gasarch W. A survey on private information retrieval, Bulletin of the EATCS, 2004 pp. 72-107

6. Yekhanin S. Locally Decodable Codes and Private Information Retrieval Schemes, Springer Heidelberg Dordrecht London New York, ISSN 1619-7100, ISBN 978-3-642-14357-1 e-ISBN 978-3-642-14358-8, DOI 10.1007/978-3-642-14358-8 2010, p.82

7. Kushilevitz E., Ostrovsky R. Replication is not needed: Single database, computationally-private information retrieval (extended abstract). In Proc. of the 38st IEEE Sym. on Found. of Comp. Sci., pages 364 373, 1997.

8. Kushilevitz E., Ostrovsky R. One-way trapdoor permutations are su cient for non-trivial single-server private information retrieval. In EUROCRYPT00, 2000.

9. Ostrovsky R., Skeith III W. E. A Survey of Single-Database Private Information Retrieval: Techniques and Applications". Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography. Springer-Verlag. pp. 393–411.

10. Aguilar-Melchor C., Barrier J., Fousse L. XPIR: Private Information Retrieval for Everyone, Proceedings on Privacy Enhancing Technologies 2016(2), pp. 155-174, DOI:10.1515/popets-2016-0010.

11. Demmler D., Herzberg A., Schneider T. RAID-PIR: Practical multi-server PIR CCSW '14: Proceedings of the 6th edition of the ACM Workshop on Cloud Computing Security, November 2014 Pages 45–56б https://doi.org/10.1145/2664168.2664181, DOI:10.1145/2664168.2664181.

12. Angel S., Chen H., Laine K., Setty S. PIR with compressed queries and amortized computation IEEE Symposium on Security and Privacy, S&P (Oakland) 2018, pp. 1-18.

13. "MuchPIR Demo". 14 September 2021. URL: https://github.com/ReverseControl/MuchPIR (дата обращения: 22.08.2022).

14. Zhou M., Park A., Shi E., Zheng W., Piano: Extremely Simple, Single-Server PIR with Sublinear Server Computation 2024 IEEE Symposium on Security and Privacy (SP) 2024, рр. 4296-4314 DOI Bookmark: 10.1109/SP54263.2024.00055