10.14489/vkit.2017.06.pp.050-056

DOI: 10.14489/vkit.2017.06.pp.050-056

Казарин О. В.
МНОГОСТОРОННИЕ КОНФИДЕНЦИАЛЬНЫЕ ВЫЧИСЛЕНИЯ В ЗАДАЧЕ О ПРЕДОТВРАЩЕНИИ СТОЛКНОВЕНИЙ
(c. 50-56)

Аннотация. Рассмотрены протоколы многосторонних конфиденциальных вычислений, которые позволяют скрывать координаты движущихся объектов в некоторой локальной зоне управления движением, для защиты участников данного движения от злоумышленников, осуществляющих различные стратегии своего поведения. Представлен случай со многими объектами-данными и одним объектом-запросом в модели со статическим получестным противником, контролирующим некоторых из участников взаимодействия. Показано, что такой контроль устанавливается в начале вычислений, далее участники точно следуют транскрипции протокола, за некоторым исключением – получестный участник протокола может записывать и сохранять информацию на всех промежуточных этапах вычислений и попытаться что-либо узнать о конфиденциальных параметрах честных участников из нее, хотя в случае честного поведения, он должен стирать такую информацию.

Ключевые слова: конфиденциальные вычисления; конфиденциальное вычисление функции; многосторонние и двухсторонние протоколы взаимодействия; системы предотвращения столкновений.

Kazarin О. V.
MULTI-PARTY SECURE COMPUTATION IN THE PROBLEM OF COLLISIONS PREVENTION
(pp. 50-56)

Abstract. The multi-party protocols of the secure computation considered in the article allow to hide the coordinates of the moving objects in some local traffic control zone in order to protect the traffic participants from an adversary who can adopt different behavior strategies.For instance, having taken control of one or several objects, an adversary may disclose movement coordinates of fair traffic participants, thus violating privacy policy of objects’ coordinates, if there is one instituted. Then, knowing such coordinates, an adversary may affect the speed of movement of controlled objects in order to create conditions for their collision with fair traffic participants. Protocols of the secure computation must withstand both first and second type of adversaries also in situations of multiparty interaction with a large number of traffic participants and high traffic intensity and with an established threshold on the number of traffic participants under control of the adversary. This paper discusses the case with many data entities and single query entity in the model with a static semi-honest adversary. This adversary controls some participants of interaction and such control is assumed at the beginning of computation and then participants follow the exact transcription of the protocol with some exceptions – a semi-honest participant of a protocol can record and store information on all intermediate stages of computation and use it to try to learn something about confidential parameters of fair participants. Although in case of fair behavior, he must erase such information.

Keywords: Secure computation; Secure function evaluation; Multi-party and two-party protocols of the interaction; Systems of the prevention of the collisions.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

О. В. Казарин (Московский государственный университет им. М. В. Ломоносова, Москва, Россия; Российский государственный гуманитарный университет, Москва, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

О. V. Kazarin (Lomonosov Moscow State University, Moscow, Russia; Russian State University for the Humanities, Moscow, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Скиба Е. А. Логарифмическое решение задачи об опасной близости // Интеллектуальные системы. 2007. Т. 11, вып. 1 – 4. С. 693 – 719.
2. Снегова А. Е. Критерий сводимости задачи об опасной близости к одномерному интервальному поиску // Дискретная математика. 2011. Т. 23, вып. 3. С. 138 – 159. doi: https:// doi.org/10.4213/dm1157
3. Снегова Е. А. Сложность задачи о предотвращении столкновений: автореф. дис. … канд. физ.-мат. наук [Электронный ресурс]. М.: Изд-во МГУ им. М. В. Ломоносова, 2012. 20 c. URL: http://mech.math.msu.su/~snark/ files/vak/arzg0.pdf (дата обращения: 10.05.2017).
4. Goldreich O. Foundations of Cryptography. V. 2. Basic Applications. Cambridge University Press, 2004. 449 p.
5. Yao A. C. Protocols for Secure Computations (Extended Abstract) // Proc. of 23rd IEEE Symp. on Foundations of Computer Science. 1982. P. 160 – 164.
6. Kumar A., Gupta A. Some Efficient Solutions to Yao’s Millionaire Problem [Электронный ресурс]. URL: http://arxiv.org/ pdf/1310.8063v1.pdf (дата обращения: 10.05.2017).
7. Ioannidis I., Grama A. An Efficient Protocol for Yao’s Millionaires’ Problem [Электронный ресурс]. URL: http: // www. cerias.purdue.edu / assets /pdf/ bibtex_archive/2003-39.pdf (дата обращения: 10.05.2017).
8. Kolesnikov V., Sadeghi A.-R., Schneider T. Improved Garbled Circuit Building Blocks and Applications to Auctions and Computing Minima [Электронный ресурс]. URL: http:// eprint.iacr.org/2009/411.pdf (дата обращения: 10.05.2017).
9. Grigoriev D., Shpilrain V. Secrecy Without One-Way Function [Электронный ресурс]. URL: http://eprint.iacr.org/ 2013/055.pdf (дата обращения: 10.05.2017).
10. Варновский Н. П., Шокуров А. В. Гомоморфное шифрование // Тр. Института системного программирования РАН. 2007. Т. 12. С. 27 – 36.
11. Варновский Н. П. Стойкость электронной подписи в модели с защищенным модулем // Дискретная математика. 2008. Т. 20, вып. 3. С. 147 – 159. doi: https://doi.org/10.4213/ dm1021
12. Дорджиев С. О., Казарин О. В. Криптографические примитивы: вложения, примеры и открытые проблемы // Безопасность информационных технологий. 2014. № 1. С. 14 – 21.
13. Казарин О. В. Методология защиты программного обеспечения. М.: МЦНМО, 2009. 464 с.

Eng

1. Skiba E. A. (2007). Logarithmic solution of the problem of dangerous proximity. Intellektual'nye sistemy, 11(1 – 4), pp. 693-719. [in Russian language]
2. Snegova E. A. (2011). A criterion for reducibility of the problem on dangerous closeness to one-dimensional interval search. Diskretnaia matematika, 23(3), pp. 138-159. doi: https:// doi.org/10.4213/dm1157 [in Russian language]
3. Snegova E. A. (2012). Complexity of the problem of collision avoidance. PhD thesis. Moscow: Izdatel'stvo MGU im. M. V. Lomonosova. Available at: http://mech.math.msu.su/~snark/ files/vak/arzg0.pdf (Accessed: 10.05.2017). [in Russian language]
4. Goldreich O. (2004). Foundations of cryptography. Vol. 2. Basic Applications. Cambridge University Press.
5. Yao A. C. (1982). Protocols for secure computations (Extended Abstract). Proc. of 23rd IEEE Symp. on Foundations of Computer Science. (pp. 160-164).
6. Kumar A., Gupta A. Some efficient solutions to Yao’s Millionaire problem. Available at: http://arxiv.org/ pdf/1310.8063v1.pdf (Accessed: 10.05.2017).
7. Ioannidis I., Grama A. (2003). An efficient protocol for Yao’s Millionaires’ problem. Available at: http: // www. cerias.purdue.edu / assets /pdf/ bibtex_archive/2003-39.pdf (Accessed: 10.05.2017).
8. Kolesnikov V., Sadeghi A.-R., Schneider T. (2009). Improved garbled circuit building blocks and applications to auctions and computing minima. Available at: http://eprint.iacr.org/2009/ 411.pdf (Accessed: 10.05.2017).
9. Grigoriev D., Shpilrain V. (2013). Secrecy without one-way function. Available at: http://eprint.iacr.org/2013/055.pdf (Accessed: 10.05.2017).
10. Varnovskii N. P., Shokurov A. V. (2017). Homomorphic encryption. Proceedings of the Institute for System Programming of the Russian Academy of Sciences, Vol. 12, pp. 27-36. [in Russian language]
11. Varnovskii N. P. (2008). Durability of electronic signatures in the model with protected module. Diskretnaia matematika, 20(3), pp. 147-159. doi: https://doi.org/10.4213/ dm1021 [in Russian language]
12. Dordzhiev S. O., Kazarin O. V. (2014). Cryptographic primitives: attachments, examples and open problems. Bezopasnost' informatsionnykh tekhnologii, (1), pp. 14-21. [in Russian language]
13. Kazarin O. V. (2009). Methodology of software protection. Moscow: MTsNMO. [in Russian language]

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2017.06.pp.050-056

и заполните ФОРМУ

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

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2017.06.pp.050-056

and fill out the FORM