Безопасные двусторонние вычисления

Безопасные двухсторонние вычисления (2PC), также известные как безопасная оценка функций, являются подзадачами безопасных многосторонних вычислений (MPC), которые привлекли особое внимание исследователей из-за их тесной связи со многими криптографическими задачами. ^{[1] [2]} Целью 2PC является создание универсального протокола, который позволяет двум сторонам совместно вычислять произвольную функцию на основе своих входных данных, не делясь значением своих входных данных с противоположной стороной. ^[3] Одним из наиболее известных примеров 2PC является задача Яо о миллионерах , в которой две стороны, Алиса и Боб, являются миллионерами, которые хотят определить, кто из них богаче, не раскрывая своего богатства. ^[4] Формально, у Алисы есть богатство , у Боба есть богатство , и они хотят вычислить, не раскрывая значения или . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\geq b}$ ${\displaystyle a}$ ${\displaystyle b}$

Искаженный протокол схемы Яо для двухсторонних вычислений обеспечивал безопасность только от пассивных злоумышленников. ^[5] Одно из первых общих решений для достижения безопасности от активного злоумышленника было предложено Голдрайхом, Микали и Вигдерсоном ^[6] путем применения доказательства с нулевым разглашением для обеспечения получестного поведения. ^[7] Этот подход в течение многих лет считался непрактичным из-за высоких накладных расходов на сложность. Тем не менее, были сделаны значительные улучшения в применении этого метода в 2PC, и Абаскал, Фагихи Серешги, Хазай, Ювал Ишай и Венкитасубраманиам представили первый эффективный протокол, основанный на этом подходе. ^[8] Другой тип протоколов 2PC, которые защищены от активных злоумышленников, был предложен Йехудой Линделлом и Бенни Пинкасом, ^[9] Ишаем, Маноджем Прабхакараном и Амитом Сахаем ^[10] и Йеспером Буусом Нильсеном и Клаудио Орланди. ^[11] Другое решение этой проблемы, которое явно работает с фиксированным вводом, было предложено Станиславом Ярецким и Виталием Шматиковым . ^[12]

Безопасные многосторонние вычисления

Безопасность

Безопасность протокола двухсторонних вычислений обычно определяется путем сравнения с идеализированным сценарием, который является безопасным по определению. ^[13] Идеализированный сценарий включает в себя доверенную сторону , которая собирает входные данные двух сторон, в основном клиента и сервера, по защищенным каналам и возвращает результат, если ни одна из сторон не выбирает прерывание. ^[14] Криптографический протокол двухсторонних вычислений является безопасным, если он ведет себя не хуже, чем этот идеальный протокол, но без дополнительных допущений доверия . Это обычно моделируется с помощью симулятора. Задача симулятора — действовать как обертка вокруг идеализированного протокола, чтобы он выглядел как криптографический протокол. Моделирование успешно по отношению к информационно-теоретическому , соответственно вычислительно ограниченному противнику, если выходные данные симулятора статистически близки , соответственно вычислительно неотличимы от выходных данных криптографического протокола. Протокол двухсторонних вычислений является безопасным, если для всех противников существует успешный симулятор.

Смотрите также

• Важным примитивом в 2PC является забывчивая передача .
• Универсальная компоновка

Ссылки

1. Ван, Сяо; Малоземофф, Алекс Дж.; Кац, Джонатан (2017), Корон, Жан-Себастьян; Нильсен, Йеспер Буус (ред.), «Быстрые безопасные вычисления с двумя участниками в условиях однократного выполнения», Достижения в криптологии – EUROCRYPT 2017 , Конспект лекций по информатике, т. 10212, Cham: Springer International Publishing, стр. 399–424, doi : 10.1007/978-3-319-56617-7_14, ISBN 978-3-319-56616-0, получено 2022-10-19
2. "MPC Wallet - Что такое MPC?". ZenGo . Получено 2022-10-19 .
3. Хенека, Вилко; Кёгль, Стефан; Садеги, Ахмад-Реза; Шнайдер, Томас; Веренберг, Иммо (2010). "TASTY". Труды 17-й конференции ACM по компьютерной и коммуникационной безопасности (PDF) . Чикаго, Иллинойс, США: ACM Press. стр. 451–462. doi :10.1145/1866307.1866358. ISBN 978-1-4503-0245-6. S2CID  7276194.
4. Линь, Сяо-Ин; Ценг, Вэнь-Гуэй (2005), Иоаннидис, Джон; Керомитис, Ангелос; Юнг, Моти (ред.), «Эффективное решение проблемы миллионеров на основе гомоморфного шифрования», Applied Cryptography and Network Security , т. 3531, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 456–466, doi : 10.1007/11496137_31 , ISBN 978-3-540-26223-7
5. Яо, AC (1982). «Протоколы для безопасных вычислений». 23-й ежегодный симпозиум по основам компьютерной науки (sfcs 1982) . стр. 160–164. doi :10.1109/SFCS.1982.38. S2CID  206558698.
6. Goldreich, O.; Micali, S.; Wigderson, A. (1987-01-01). "Как играть в ЛЮБУЮ ментальную игру". Труды девятнадцатой ежегодной конференции ACM по теории вычислений - STOC '87 . Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 218–229. doi :10.1145/28395.28420. ISBN 978-0-89791-221-1. S2CID  6669082.
7. Goldwasser, S; Micali, S; Rackoff, C (1985-12-01). "Сложность знаний интерактивных систем доказательства". Труды семнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '85 . Провиденс, Род-Айленд, США: Ассоциация вычислительной техники. стр. 291–304. doi :10.1145/22145.22178. ISBN 978-0-89791-151-1. S2CID  8689051.
8. Абаскал, Джексон; Фагихи Серешги, Мохаммад Хоссейн; Хазай, Кармит; Ишай, Ювал; Венкитасубраманиам, Мутурамакришнан (2020-10-30). «Практична ли классическая парадигма GMW? Случай неинтерактивного активно защищенного 2PC». Труды конференции ACM SIGSAC 2020 года по компьютерной и коммуникационной безопасности . CCS '20. Виртуальное мероприятие, США: Ассоциация вычислительной техники. стр. 1591–1605. doi :10.1145/3372297.3423366. ISBN 978-1-4503-7089-9. S2CID  226228208.
9. Линделл, Y.; Пинкас, B. (2007). "Эффективный протокол для безопасных двусторонних вычислений в присутствии злонамеренных противников". Достижения в криптологии - EUROCRYPT 2007. Конспект лекций по информатике. Том 4515. С. 52–78. doi :10.1007/978-3-540-72540-4_4. ISBN 978-3-540-72539-8.
10. Ишай, Й.; Прабхакаран, М.; Сахай, А. (2008). «Основание криптографии на забывчивой передаче – эффективно». Достижения в криптологии – CRYPTO 2008. Конспект лекций по информатике. Том 5157. С. 572–591. doi :10.1007/978-3-540-85174-5_32. ISBN 978-3-540-85173-8.
11. Нильсен, Дж. Б.; Орланди, К. (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.
12. Jarecki, S.; Shmatikov, V. (2007). "Эффективные безопасные вычисления с двумя сторонами на фиксированных входах". Advances in Cryptology - EUROCRYPT 2007. Lecture Notes in Computer Science. Vol. 4515. pp. 97–114. doi :10.1007/978-3-540-72540-4_6. ISBN 978-3-540-72539-8.
13. Линделл, Йехуда; Пинкас, Бенни (2015). «Эффективный протокол для безопасных двусторонних вычислений в присутствии злонамеренных противников». Журнал криптологии . 28 (2): 312–350. doi : 10.1007/s00145-014-9177-x . ISSN  0933-2790. S2CID  253638839.
14. Крепо, Клод; Вульшлегер, Юрг (2008), Сафави-Наини, Рейхане (ред.), «Статистические условия безопасности для двухсторонней безопасной оценки функций», Information Theoretic Security , Lecture Notes in Computer Science, т. 5155, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 86–99, doi :10.1007/978-3-540-85093-9_9, ISBN 978-3-540-85092-2, получено 2022-10-19