Искаженная схема - это криптографический протокол, который обеспечивает двухстороннее безопасное вычисление, в котором две недоверчивые стороны могут совместно оценить функцию по своим частным входам без присутствия доверенной третьей стороны. В протоколе искаженной схемы функция должна быть описана как логическая схема .
История искаженных схем сложна. Изобретение искаженной схемы было приписано Эндрю Яо , поскольку Яо представил эту идею в устной презентации статьи [1] в FOCS'86. Это было задокументировано Одедом Голдрайхом в 2003 году. [2] Первый письменный документ об этой технике был написан Голдрайхом, Микали и Вигдерсоном в STOC'87. [3] Термин «искаженный цепь» впервые был использован Beaver, Микали и Rogaway в STOC'90. [4] Протокол Яо, решающий проблему миллионеров Яо, был начальным примером безопасных вычислений, но он не имеет прямого отношения к искаженным схемам.
Задний план
Незаметный перевод
В протоколе искаженной схемы мы используем передачу без внимания . При передаче без внимания строка передается между отправителем и получателем следующим образом: у отправителя есть две строки. а также . Получатель выбирает и отправитель отправляет с протоколом передачи не обращая внимания, так что
- получатель не получает никакой информации о ,
- значение не выставляется отправителю.
Обратите внимание, что пока получатель не знает значения, на практике получатель знает некоторую информацию о том, что кодирует так, чтобы получатель не выбирал вслепую . То есть, если кодирует ложное значение, кодирует истинное значение, и получатель хочет получить закодированное истинное значение, получатель выбирает .
Забывающие передачи могут быть построены с использованием асимметричной криптографии как в RSA криптосистеме .
Определения и обозначения
Оператор это конкатенация строк . Оператор- это побитовый XOR . k - параметр безопасности и длина ключей. Оно должно быть больше 80 и обычно устанавливается на 128.
Протокол искаженной схемы
Протокол состоит из 6 шагов:
- Базовая функция (например, в проблеме миллионеров, функция сравнения) описывается как логическая схема с двумя входами. Схема известна обеим сторонам. Этот шаг может быть выполнен сторонним лицом.
- Алиса искажает (шифрует) схему. Мы называем Алису мусорщицей .
- Алиса отправляет Бобу искаженную схему вместе со своим зашифрованным вводом.
- Чтобы рассчитать схему, Бобу также необходимо искажать свой собственный ввод. Для этого ему нужна помощь Алисы, потому что только мусорщик знает, как зашифровать. Наконец, Боб может зашифровать свой ввод, не обращая внимания на передачу. В терминах определения, приведенного выше, Боб является получателем, а Алиса - отправителем в этой не обращающей внимания передаче.
- Боб оценивает (расшифровывает) схему и получает зашифрованные выходные данные. Мы называем Боба оценщиком .
- Алиса и Боб общаются, чтобы узнать результат.
Цепь генерация
Схема булева для малых функций могут быть сгенерированы вручную. Обычно схема состоит из вентилей XOR и AND с двумя входами . Важно, чтобы сгенерированная схема имела минимальное количество логических элементов И (см. Оптимизация Free XOR ). Существуют методы, которые генерируют оптимизированную схему с точки зрения количества логических элементов И с использованием техники логического синтеза . [5] Схема для проблемы миллионеров представляет собой схему цифрового компаратора (которая представляет собой цепочку полных сумматоров, работающих как вычитатель и выводящих флаг переноса ). Полная схема сумматора может быть реализована с использованием только одного логического элемента И и нескольких вентилей XOR . Это означает, что общее количество логических элементов И для схемы Задачи миллионеров равно разрядности входных данных.
Искажение
Алиса (garbler) шифрует логическую схему на этом этапе, чтобы получить искаженную схему . Алиса назначает две случайно сгенерированные строки, называемые метками, каждому проводу в цепи: одну для логической семантики 0 и одну для 1. (Длина метки составляет k бит, где k - параметр безопасности, и обычно он имеет значение 128). Затем она переходит. ко всем воротам в схеме и заменяет 0 и 1 в таблицах истинности соответствующими метками. В таблице ниже показана таблица истинности для логического элемента И с двумя входами. и вывод :
а | б | c |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Алиса заменила 0 и 1 соответствующими метками:
а | б | c |
---|---|---|
Затем она шифрует выходную запись таблицы истинности двумя соответствующими входными метками. Зашифрованная таблица называется искаженной таблицей. Это сделано для того, чтобы расшифровать искаженную таблицу, только если у него есть две правильные метки ввода. В таблице ниже- это двухключевое симметричное шифрование, в котором k - секретный ключ, а X - значение, которое нужно зашифровать (см. Блок- шифрование с фиксированным ключом ).
Искаженная таблица |
---|
После этого Алиса случайным образом переставляет таблицу, так что выходное значение не может быть определено из строки. Имя протокола, искаженное , получено из этой случайной перестановки.
Обмен данными
Алиса отправляет Бобу вычисленные искаженные таблицы для всех вентилей в схеме. Бобу нужны метки ввода, чтобы открывать искаженные таблицы. Таким образом, Алиса выбирает метки, соответствующие ее вводу.и отправляет их Бобу. Например, если ввод Алисы, затем она отправляет , , , , а также Бобу. Боб ничего не узнает о вводе Алисы,, поскольку метки генерируются Алисой случайным образом и для Боба они выглядят как случайные строки.
Бобу также нужны метки, соответствующие его вводу. Он получает свои метки через незаметные передачи для каждого бита своего ввода. Например, если ввод Боба, Боб сначала спрашивает между лейблами Алисы а также . Посредством передачи 1 из 2, не обращая внимания , он получаети так далее. После незаметных передач Алиса ничего не узнает о вводе Боба, а Боб ничего не узнает о других метках.
Оценка
После передачи данных у Боба есть искаженные таблицы и метки ввода. Он проходит через все ворота один за другим и пытается расшифровать строки в их искаженных таблицах. Он может открыть одну строку для каждой таблицы и получить соответствующую метку вывода:, где . Он продолжает оценку, пока не дойдет до меток вывода.
Выявление результатов
После оценки Боб получает метку вывода, , и Алиса знает его отображение на логическое значение, поскольку у нее есть обе метки: а также . Либо Алиса может поделиться своей информацией с Бобом, либо Боб может показать результат Алисе, так что один или оба из них узнают результат.
Оптимизация
Точка и перестановка
В этой оптимизации Алиса генерирует случайный бит, , называемый бит выбора для каждого провода . Затем она устанавливает первый бит метки 0, к и первый бит метки 1, , к ( НЕ из). Затем она вместо случайной перестановки сортирует искаженную таблицу в соответствии с битом выбора входных данных. Таким образом, Бобу не нужно проверять все четыре строки таблицы, чтобы найти правильную, поскольку у него есть входные метки, и он может найти правильную строку и расшифровать ее с одной попытки. Это снижает нагрузку на оценку в 4 раза. Он также ничего не раскрывает о выходном значении, потому что биты выбора генерируются случайным образом. [6]
Уменьшение ряда
Эта оптимизация уменьшает размер искаженных таблиц с 4 до 3 строк. Здесь вместо того, чтобы генерировать метку для выходного провода логического элемента случайным образом, Алиса генерирует ее, используя функцию входных меток. Она генерирует метки вывода так, что первая запись искаженной таблицы становится равной 0 и ее больше не нужно отправлять: [7]
Бесплатный XOR
В этой оптимизации Алиса генерирует глобальное случайное (k-1) -битное значение который держится в секрете. Во время гардинга входных ворот а также , она только генерирует ярлыки и вычисляет другие метки как а также . Используя эти значения, метка выходного провода логического элемента XOR с входными проводами , установлен на . Доказательство безопасности в случайной модели Oracle для этой оптимизации приведено в статье Free-XOR. [8]
Последствия
Оптимизация свободного XOR подразумевает важный момент, что объем передачи данных (коммуникаций) и количество шифров и дешифрования (вычислений) протокола искаженной схемы зависит только от количества логических элементов И в логической схеме, а не от элементов XOR . Таким образом, между двумя логическими схемами, представляющими одну и ту же функцию, предпочтительна схема с меньшим количеством логических элементов И.
Блочный шифр с фиксированным ключом
Этот метод позволяет эффективно искажать и оценивать логические элементы И, используя AES с фиксированным ключом , вместо дорогостоящей криптографической хеш-функции, такой как SHA-2 . В этой схеме искажения, которая совместима с методами Free XOR и Row Reduction , выходной ключ зашифрован входным токеном а также используя функцию шифрования , где , представляет собой блочный шифр с фиксированным ключом (например, созданный с помощью AES ), и- это уникальный номер для каждого шлюза (например, идентификатор шлюза), называемый настройкой . [9]
Половина и
Эта оптимизация уменьшает размер искаженной таблицы для логических элементов AND с 3 строк в Row Reduction до 2 строк. Показано, что это теоретический минимум количества строк в искаженной таблице для определенного класса методов искажения. [10]
Безопасность
Искаженная схема Яо защищена от получестного противника. Этот тип злоумышленника следует протоколу и не совершает никаких злонамеренных действий, но он пытается нарушить конфиденциальность ввода другой стороны, тщательно исследуя сообщения, передаваемые в протоколе.
Сложнее защитить этот протокол от злоумышленника, который отклоняется от протокола. Одним из первых решений для защиты протокола от злоумышленников является использование доказательства с нулевым разглашением для предотвращения злонамеренных действий во время протокола. [11] В течение многих лет этот подход считался скорее теоретическим решением, чем практическим решением из-за накладных расходов на него. Но показано, что его можно использовать с небольшими накладными расходами. [12] Другой подход заключается в использовании нескольких сборщиков мусора для схемы и проверке правильности подмножества из них, а затем использовании оставшейся части для вычислений с надеждой, что если искажатель был вредоносным, он был бы обнаружен на этапе проверки. [13] Другое решение - сделать схему искажения аутентифицированной, чтобы оценщик мог проверить искаженную схему. [14] [15]
Смотрите также
- Криптография
- ЮАР
- Безопасные многосторонние вычисления
- Проблема миллионеров Яо
Рекомендации
- ↑ Яо, Эндрю Чи-Чи (1986). «Как генерировать и обмениваться секретами». 27-й ежегодный симпозиум по основам информатики (SFCS 1986) . Основы компьютерных наук, 1986., 27-й ежегодный симпозиум по . С. 162–167. DOI : 10.1109 / SFCS.1986.25 . ISBN 978-0-8186-0740-0.
- ^ Гольдрайх, Одед (2003). «Криптография и криптографические протоколы» . Распределенные вычисления - доклады по случаю 20-летия PODC . 16 (2–3): 177–199. CiteSeerX 10.1.1.117.3618 . DOI : 10.1007 / s00446-002-0077-1 . S2CID 9966766 .
- ^ Гольдрайх, Одед; Микали, Сильвио; Вигдерсон, Ави (1987). Как играть в ЛЮБУЮ мысленную игру . Proceeding STOC '87 Труды девятнадцатого ежегодного симпозиума ACM по теории вычислений . С. 218–229. DOI : 10.1145 / 28395.28420 . ISBN 978-0897912211. S2CID 6669082 .
- ^ Бивер, Дональд; Микали, Сильвио; Rogaway, Филипп (1990). Круговая сложность защищенных протоколов . Proceeding STOC '90 Труды двадцать второго ежегодного симпозиума ACM по теории вычислений . С. 503–513. CiteSeerX 10.1.1.697.1624 . DOI : 10.1145 / 100216.100287 . ISBN 978-0897913614. S2CID 1578121 .
- ^ Songhori, Ebrahim M; Хуссейн, Сиамский университет; Садеги, Ахмад-Реза; Шнайдер, Томас; Кушанфар, Фариназ (2015). TinyGarble: сильно сжатые и масштабируемые последовательные искаженные схемы . Безопасность и конфиденциальность (SP), 2015 IEEE симпозиум по . С. 411–428. DOI : 10,1109 / SP.2015.32 . ISBN 978-1-4673-6949-7. S2CID 5346323 .
- ^ Бивер, Дональд; Микали, Сильвио; Rogaway, Филипп (1990). Круглая сложность безопасных протоколов . Материалы двадцать второго ежегодного симпозиума ACM по теории вычислений . С. 503–513. CiteSeerX 10.1.1.697.1624 . DOI : 10.1145 / 100216.100287 . ISBN 978-0897913614. S2CID 1578121 .
- ^ Наор, Мони; Пинкас, Бенни; Самнер, Ройбан (1999). Аукционы с сохранением конфиденциальности и конструкция механизма . Труды 1-й конференции ACM по электронной коммерции . С. 129–139. CiteSeerX 10.1.1.17.7459 . DOI : 10.1145 / 336992.337028 . ISBN 978-1581131765. S2CID 207593367 .
- ^ Колесников Владимир; Шнайдер, Томас (2008). Улучшенная искаженная схема: бесплатные шлюзы и приложения XOR . Международный коллоквиум по автоматам, языкам и программированию . Конспект лекций по информатике. 5126 . С. 486–498. CiteSeerX 10.1.1.160.5268 . DOI : 10.1007 / 978-3-540-70583-3_40 . ISBN 978-3-540-70582-6.
- ^ Белларе, Михир; Хоанг, Вьет Тунг; Килвэди, Шрирам; Rogaway, Филипп (2013). Эффективное искажение блочного шифра с фиксированным ключом . Безопасность и конфиденциальность (SP), 2013 IEEE симпозиум по . С. 478–492. CiteSeerX 10.1.1.299.2755 . DOI : 10,1109 / SP.2013.39 . ISBN 978-0-7695-4977-4. S2CID 1351222 .
- ^ Захур, Сами; Розулек, Майк; Эванс, Дэвид (2015). Две половинки составляют единое целое (PDF) .
- ^ Гольдвассер, S; Micali, S; Рэкофф, К. (1985-12-01). «Сложность знаний интерактивных доказательств-систем» . Материалы семнадцатого ежегодного симпозиума ACM по теории вычислений . СТОК '85. Провиденс, Род-Айленд, США: Ассоциация вычислительной техники: 291–304. DOI : 10.1145 / 22145.22178 . ISBN 978-0-89791-151-1. S2CID 8689051 .
- ^ Абаскаль, Джексон; Фагихи Серешги, Мохаммад Хоссейн; Хазай, Кармит; Ишай, Юваль; Венкитасубраманиам, Мутурамакришнан (30.10.2020). «Практична ли классическая парадигма GMW? Случай неинтерактивных и защищенных 2PC» . Материалы конференции ACM SIGSAC 2020 по компьютерной и коммуникационной безопасности . CCS '20. Виртуальное событие, США: Ассоциация вычислительной техники: 1591–1605. DOI : 10.1145 / 3372297.3423366 . ISBN 978-1-4503-7089-9. S2CID 226228208 .
- ^ Линделл, Иегуда; Пинкас, Бенни (2007). Наор, Мони (ред.). «Эффективный протокол для безопасных двусторонних вычислений в присутствии злоумышленников» . Достижения в криптологии - EUROCRYPT 2007 . Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 4515 : 52–78. Bibcode : 2007LNCS.4515 ... 52L . DOI : 10.1007 / 978-3-540-72540-4_4 . ISBN 978-3-540-72540-4.
- ^ Ишай, Юваль; Кушилевиц, Эяль; Островский, Рафаил; Прабхакаран, Манодж; Сахай, Амит (2011). Патерсон, Кеннет Г. (ред.). «Эффективные неинтерактивные безопасные вычисления» . Достижения в криптологии - EUROCRYPT 2011 . Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 6632 : 406–425. DOI : 10.1007 / 978-3-642-20465-4_23 . ISBN 978-3-642-20465-4.
- ^ Хазай, Кармит; Ишай, Юваль; Венкитасубраманиам, Мутурамакришнан (2017). Калаи, Яэль; Рейзин, Леонид (ред.). «Активно защищенные искаженные схемы с постоянными накладными расходами на связь в простой модели» . Теория криптографии . Конспект лекций по информатике. Чам: Издательство Springer International. 10678 : 3–39 . DOI : 10.1007 / 978-3-319-70503-3_1 . ISBN 978-3-319-70503-3.
дальнейшее чтение
- "Искаженная схема Яо" (PDF) . CS598 . illinois.edu . Проверено 18 октября +2016 .