About Cloud Request Protection
Nikolay Pavlovich VARNOVSKIY,
Sergey Anatolievich MARTISHIN,
Marina Valerievna KHRAPCHENKO,
Alexander Vladimirovich SHOKUROV https://doi.org/10.15514/ISPRAS-2022-35(5)-3
Abstract
The article examines the well-known cryptographic problem of obtaining data from a database by a client so that no one with access to the server except the client himself could obtain information about this request. This problem known as PIR (Private Information Retrieval) was formulated in 1995 by Chor, Goldreich, Kushilevitz and Sudan in the information-theoretic setting. A model of cloud computing is proposed. It includes a cloud, an authentication center, a user, clients, trusted dealer, an active adversary executing the protocol in the cloud. 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. An injective transformation of bit numbers represented in the l-ary number system by words of length d into words without repeating digits of the same length with an alphabet of 𝒍̂ digits is used, i.e. a transformation {0, ..., l}d →{0, ..., 𝒍̂}d was constructed. This transformation reduces the probability of disclosure of the requested bit number. The communication complexity and probability of revealing required bit were estimated, taking into account the performed transformation.
Supporting agencies: This work was funded by Russian Federation represented by the Ministry of Science and Higher Education (grant number 075-15-2020-788) and ISP RAS. The authors are especially grateful to D.O. Lazarev for valuable comments during the work on the article.
About the Authors
Nikolay Pavlovich VARNOVSKIY
Information Security Institute of Moscow State Lomonosov University
Russian Federation
Russian Federation
Researcher of Mathematical Studies in Information Security Section of Information Security Institute of Moscow State Lomonosov University. His research interests are mathematics, Information Security and Cryptography, complexity theory.
Sergey Anatolievich MARTISHIN
Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
Cand. Sci. (Phys.-Math.), researcher of the Department of Theoretical Computer Science of Ivannikov Institute for System Programming of the RAS. His research interests include parallel algorithms, databases, cloud computing.
Marina Valerievna KHRAPCHENKO
Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
Researcher of the Department of Theoretical Computer Science of Ivannikov Institute for System Programming of the RAS. Her research interests include parallel algorithms, databases, cloud computing.
Alexander Vladimirovich SHOKUROV
Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
Cand. Sci. (Phys.-Math.), Professor, Head of the Department of Theoretical Computer Science of Ivannikov Institute for System Programming of the RAS since 2019. Research interests: algebraic structures in the Galois fields, modular arithmetic, neurocomputer technologies, Grobner bases, digital signal processing, cryptographic methods for protecting information.
References
1. Chor B., Goldreich O., Kushilevitz E., Sudan M. Private Information Retrieval, in IEEE Annual Symposium on Foundations of Computer Science, 1995, pp. 41–50.
2. Chor B., Goldreich O., Kushilevitz E., Sudan M. Private Information Retrieval, Journal of the ACM, Vol. 45, No. 6, November 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 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
5. 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.
6. Kushilevitz E., Ostrovsky R. One-Way Trapdoor Permutations Are Sufficient for Non-trivial Single-Server Private Information Retrieval. In EUROCRYPT00, 2000.
7. 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.
8. 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.
9. 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.
10. Мартишин С.А., Храпченко М.В., Шокуров А.В. Организация безопасного запроса к базе данных на облаке. Труды Института системного программирования РАН. Том 34, № 3, 2022г., с. 173-188, ISSN 2079-8156 (Print), ISSN 2220-6426 (Online).
11. Wahid M.N.A., Ali A., Esparham B., Marwan M. A Comparison of Cryptographic Algorithms: DES, 3DES, AES, RSA and Blowfish for Guessing Attacks Prevention. Journal of Computer Science Applications and Information Technology, 2018, 3(2); 1-7.
12. Ширяев А. Н. Вероятность – 1, Москва, Из-во МЦНМО, 2021, изд. 7, стереот., 552 с. ISBN 978-5-4439-1557-9.
Review
For citations:
VARNOVSKIY N.P., MARTISHIN S.A., KHRAPCHENKO M.V., SHOKUROV A.V. About Cloud Request Protection. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2023;35(5):37-54. (In Russ.) https://doi.org/10.15514/ISPRAS-2022-35(5)-3
Email this article 