Вычислительная геометрия, сохраняющая конфиденциальность

Вычислительная геометрия, сохраняющая конфиденциальность, — это область исследований на пересечении областей безопасных многосторонних вычислений (SMC) и вычислительной геометрии . Классические проблемы вычислительной геометрии, пересмотренные с точки зрения SMC, включают пересечение фигур, проблему включения частной точки, поиск диапазона , выпуклую оболочку , ^[1] и многое другое. ^[2]

Новаторской работой в этой области стала статья Аталлы и Ду, опубликованная в 2001 году. ^[3] безопасной точки при включении многоугольников в котором рассматривались проблемы и проблемы пересечения многоугольников.

Другими проблемами являются вычисление расстояния между двумя частными точками. ^[4] и обеспечьте двустороннюю проблему включения точки и круга. ^[5]

Постановки задач

В задачах используется общепринятая терминология « Алисы и Боба ». Во всех задачах требуемым решением является протокол обмена информацией, в ходе которого не раскрывается никакой дополнительной информации, кроме той, которую можно вывести из ответа на требуемый вопрос.

Точка в многоугольнике: у Алисы есть точка a Боба — многоугольник B. , а у Им нужно определить, ли a внутри B. находится ^[3]
Пересечение пары полигонов: у Алисы есть многоугольник A Боба — многоугольник B. , а у Им нужно определить, пересекает ли A B. ^[3]

Ссылки

^ «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 12 ноября 2013 г. Проверено 12 ноября 2013 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
^ Кайтай ЛЯН, Бо ЯН, Дэйк Х.Е., Мин Чжоу, Проблемы вычислительной геометрии с сохранением конфиденциальности на конических сечениях , Журнал вычислительных информационных систем 7: 6 (2011) 1910–1923
^ Перейти обратно: ^а ^б ^с Аталлах М.Дж. , Дю В. Безопасная многосторонняя вычислительная геометрия . В Proc. Алгоритмы и структуры данных: 7-й международный семинар, WADS 2001, Конспекты лекций по информатике, LNCS 2125, Провиденс, Род-Айленд, США, страницы 165–179, 8–10 августа 2001 г. (цитируется по Liang et al., 2011).
^ Ли С.Д., Дай Ю. К. Безопасная двухсторонняя вычислительная геометрия. Журнал компьютерных наук и технологий, 20 (2): страницы 258–263, 2005 г.
^ Луо Ю.Л., Хуан Л.С., Чжун Х. Проблема безопасного включения двусторонней точки в окружность. Журнал компьютерных наук и технологий, 22 (1): страницы 88–91, 2007 г.

[1] «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 12 ноября 2013 г. Проверено 12 ноября 2013 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[lyhz-2] Кайтай ЛЯН, Бо ЯН, Дэйк Х.Е., Мин Чжоу, Проблемы вычислительной геометрии с сохранением конфиденциальности на конических сечениях , Журнал вычислительных информационных систем 7: 6 (2011) 1910–1923

[ad-3] Перейти обратно: ^а ^б ^с Аталлах М.Дж. , Дю В. Безопасная многосторонняя вычислительная геометрия . В Proc. Алгоритмы и структуры данных: 7-й международный семинар, WADS 2001, Конспекты лекций по информатике, LNCS 2125, Провиденс, Род-Айленд, США, страницы 165–179, 8–10 августа 2001 г. (цитируется по Liang et al., 2011).

[4] Ли С.Д., Дай Ю. К. Безопасная двухсторонняя вычислительная геометрия. Журнал компьютерных наук и технологий, 20 (2): страницы 258–263, 2005 г.

[5] Луо Ю.Л., Хуан Л.С., Чжун Х. Проблема безопасного включения двусторонней точки в окружность. Журнал компьютерных наук и технологий, 22 (1): страницы 88–91, 2007 г.

[1]

[2]

[3]

[4]

[5]