Безопасные двухсторонние вычисления (2PC) - это подзадача безопасных многосторонних вычислений (MPC), которая привлекла особое внимание исследователей из-за ее тесной связи со многими криптографическими задачами. Цель 2PC - создать общий протокол, который позволяет двум сторонам совместно вычислять произвольную функцию на своих входах, не делясь значениями своих входов с противоположной стороной. Одним из наиболее известных примеров 2PC является проблема миллионера Яо , в которой две стороны, Алиса и Боб, являются миллионерами, которые хотят определить, кто богаче, не раскрывая своего богатства. Формально у Алисы есть богатство, У Боба есть богатство , и они хотят вычислить без раскрытия ценностей или же .
Протокол искаженных схем Яо для двухсторонних вычислений [1] только обеспечивал защиту от пассивных противников. Одно из первых общих решений для обеспечения защиты от активного противника было предложено Голдрайхом, Микали и Вигдерсоном [2] путем применения доказательства с нулевым разглашением [3] для обеспечения получестного поведения. В течение многих лет было известно, что этот подход непрактичен из-за высоких накладных расходов на сложность. Однако были внесены значительные улучшения в применение этого метода в 2PC, и Abascal, Faghihi Sereshgi, Hazay, Ishai и Venkitasubramaniam представили первый эффективный протокол, основанный на этом подходе. [4] Другой тип протоколов 2PC, защищенных от активных противников, был предложен Линделлом и Пинкасом [5] Ишаи, Прабхакараном и Сахаем [6], а также Нильсеном и Орланди. [7] Другое решение этой проблемы, которое явно работает с подтвержденным вводом, было предложено Яреки и Шматиковым. [8]
Безопасность
Безопасность протокола двусторонних вычислений обычно определяется путем сравнения с идеализированным сценарием, который является безопасным по определению. Идеализированный сценарий включает в себя доверенную сторону, которая собирает входные данные двух сторон по защищенным каналам и возвращает результат, если ни одна из сторон не решает прервать выполнение. Протокол криптографических двухсторонних вычислений является безопасным, если он ведет себя не хуже, чем этот идеальный протокол, но без дополнительных предположений о доверии . Обычно это моделируется с помощью симулятора. Задача симулятора - действовать как оболочка вокруг идеализированного протокола, чтобы он выглядел как криптографический протокол. Моделирование считается успешным по отношению к теоретическому информационному или ограниченному в вычислительном отношении противнику, если выходные данные имитатора статистически близки к выходным данным криптографического протокола или , соответственно, неотличимы в вычислительном отношении от выходных данных криптографического протокола. Протокол двусторонних вычислений безопасен, если для всех противников существует успешный симулятор.
Смотрите также
- Важным примитивом в 2PC является передача без внимания .
- Универсальная компоновка
Рекомендации
- Перейти ↑ Yao, AC (1982). «Протоколы для безопасных вычислений». 23-й ежегодный симпозиум по основам информатики (sfcs 1982) . С. 160–164. DOI : 10.1109 / SFCS.1982.38 . S2CID 206558698 .
- ^ Goldreich, O .; Micali, S .; Вигдерсон, А. (01.01.1987). «Как играть в ЛЮБУЮ мысленную игру» . Материалы девятнадцатого ежегодного симпозиума ACM по теории вычислений . СТОК '87. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники: 218–229. DOI : 10.1145 / 28395.28420 . ISBN 978-0-89791-221-1.
- ^ Гольдвассер, S; Micali, S; Рэкофф, К. (1985-12-01). «Сложность знаний интерактивных доказательств-систем» . Материалы семнадцатого ежегодного симпозиума ACM по теории вычислений . СТОК '85. Провиденс, Род-Айленд, США: Ассоциация вычислительной техники: 291–304. DOI : 10.1145 / 22145.22178 . ISBN 978-0-89791-151-1.
- ^ Абаскаль, Джексон; Фагихи Серешги, Мохаммад Хоссейн; Хазай, Кармит; Ишай, Юваль; Венкитасубраманиам, Мутурамакришнан (30.10.2020). «Практична ли классическая парадигма GMW? Случай неинтерактивных и защищенных 2PC» . Материалы конференции ACM SIGSAC 2020 по компьютерной и коммуникационной безопасности . CCS '20. Виртуальное событие, США: Ассоциация вычислительной техники: 1591–1605. DOI : 10.1145 / 3372297.3423366 . ISBN 978-1-4503-7089-9.
- ^ Lindell, Y .; Пинкас, Б. (2007). Достижения в криптологии - EUROCRYPT 2007 . Конспект лекций по информатике. 4515 . С. 52–78. DOI : 10.1007 / 978-3-540-72540-4_4 . ISBN 978-3-540-72539-8.
- ^ Ishai, Y .; Прабхакаран, М .; Сахай, А. (2008). Достижения в криптологии - CRYPTO 2008 . Конспект лекций по информатике. 5157 . С. 572–591. DOI : 10.1007 / 978-3-540-85174-5_32 . ISBN 978-3-540-85173-8.
- ^ Nielsen, JB; Орланди, К. (2009). «LEGO для двусторонних безопасных вычислений». Теория криптографии . Конспект лекций по информатике. 5444 . С. 368–386. CiteSeerX 10.1.1.215.4422 . DOI : 10.1007 / 978-3-642-00457-5_22 . ISBN 978-3-642-00456-8.
- ^ Jarecki, S .; Шматиков, В. (2007). Достижения в криптологии - EUROCRYPT 2007 . Конспект лекций по информатике. 4515 . С. 97–114. DOI : 10.1007 / 978-3-540-72540-4_6 . ISBN 978-3-540-72539-8.