Organization of a secure query to a database in the cloud
https://doi.org/10.15514/ISPRAS-2022-34(3)-12
Abstract
The development of cloud computing, including the storage and processing of confidential user data on servers that can be attacked, puts forward new requirements for information protection. The article explores the problem of obtaining information from the database by the client in such a way that no one except the client himself get any information about the information the client is interested in (PIR - Private Information Retrieval). The problem was introduced in 1995 by Chor, Goldreich, Kushilevitz and Sudan in the information-theoretic setting. A model of cloud computing is proposed. It includes a cloud, a user, clients, a trusted dealer, a passive adversary in the cloud. Also, the attacking side has the ability to create fake clients to generate an unlimited number of requests. An algorithm for the organization and database distribution on the cloud and an algorithm for obtaining the required bit were proposed. Communication complexity of the algorithm was estimated. The probability of revealing required bit's number in the case when fake clients perform unlimited requests was estimated too.
Supporting agencies: The work was supported by the Ministry of Science and Higher Education of the Russian Federation (grant 075-15-2020) and ISP RAS. The authors are especially grateful to D.O. Lazarev for valuable comments during the work on the article
About the Authors
Sergey Anatolievich MARTISHIN
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
PhD, researcher of the Department of Theoretical Computer Science
Marina Valerievna KHRAPCHENKO
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
Researcher of the Department of Theoretical Computer Science
Alexander Vladimirovich SHOKUROV
Ivannikov Institute for System Programming of the Russian Academy of Sciences,
Moscow Institute of Physics and Technology
Russian Federation
Russian Federation
PhD of Physical and Mathematical Sciences, Professor, Head of the Department of Theoretical Computer Science
References
1. Chor B., Goldreich O. et al. Private Information Retrieval. In Proc. of the IEEE Annual Symposium on Foundations of Computer Science, 1995, pp. 41-50.
2. Chor B., Goldreich O. et al. Private Information Retrieval. Journal of the ACM, vol. 45, no. 6, 1998, pp. 965-982.
3. Gasarch W. A survey on private information retrieval. Bulletin of the EATCS, 2004, pp. 72-107
4. Yekhanin S. Locally Decodable Codes and Private Information Retrieval Schemes. Springer-Verlag Berlin Heidelberg, 2010, 82 p.
5. Kushilevitz E., Ostrovsky R. Replication is not needed: Single database, computationally-private information retrieval (extended abstract). In Proc. of the 38th Annual Symposium on Foundations of Computer Science, 1997, pp. 364-373.
6. Kushilevitz E., Ostrovsky R. One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval. Lecture Notes in Computer Science, vol. 1807, 2000, pp. 104-121.
7. Ostrovsky R., Skeith III W. E. A Survey of Single-Database Private Information Retrieval: Techniques and Applications. Lecture Notes in Computer Science, vol. 4450, 2007, pp. 393-411.
8. Aguilar-Melchor C., Barrier J., Fousse L. XPIR: Private Information Retrieval for Everyone, Proceedings on Privacy Enhancing Technologies Symposium, 2016, issue 2, pp. 155-174.
9. Варновский Н.П., Нестеренко Ю.В., Ященко В.В. Введение в криптографию. Из-во МЦНМО, 2012, 348 стр. / Varnovsky N.P., Nesterenko Yu.V., Yashchenko V.V. Introduction to cryptography. MCCME, 2012, 348 p. (in Russian).
10. Demmler D., Herzberg A., Schneider T. RAID-PIR: Practical multi-server PIR. In Proc. of the 6th edition of the ACM Workshop on Cloud Computing Security, 2014, pp. 45-56.
11. Angel S., Chen H. et al. PIR with compressed queries and amortized computation. In Proc. of the IEEE Symposium on Security and Privacy, 2018, pp. 1-18.
12. "MuchPIR Demo". URL: https://github.com/ReverseControl/MuchPIR, accessed 22.08.2022.
13. Wahid M.N.A., Ali A. et al. A Comparison of Cryptographic Algorithms: DES, 3DES, AES, RSA and Blowfish for Guessing Attacks Prevention. Journal of Computer Science Applications and Information Technology, vol. 3, no. 2, 2018, pp. 1-7.
Review
For citations:
MARTISHIN S.A., KHRAPCHENKO M.V., SHOKUROV A.V. Organization of a secure query to a database in the cloud. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2022;34(3):173-188. (In Russ.) https://doi.org/10.15514/ISPRAS-2022-34(3)-12
Email this article 