Запутывание неотличимости

В криптографии обфускация неотличимости (сокращенно IO или iO ) — это тип программной обфускации с определяющим свойством, заключающимся в том, что запутывание любых двух программ, вычисляющих одну и ту же математическую функцию , приводит к созданию программ, которые невозможно отличить друг от друга. Неформально такая обфускация скрывает реализацию программы, но при этом позволяет пользователям ее запускать. Формально iO удовлетворяет тому свойству, что обфускации двух схем одинакового размера, реализующих одну и ту же функцию, неразличимы в вычислительном отношении .

Обфускация неотличимости имеет несколько интересных теоретических свойств. Во-первых, iO — это «наилучшая возможная» обфускация (в том смысле, что любой секрет программы, который вообще может быть скрыт любым обфускатором, также может быть скрыт iO). Во-вторых, iO можно использовать для создания почти всего спектра криптографических примитивов , включая как обыденные, такие как криптография с открытым ключом, так и более экзотические, такие как шифрование с возможностью отрицания и функциональное шифрование (которые представляют собой типы криптографии, о применении которых никто ранее не знал). построить ), но за заметным исключением семейств хеш-функций, устойчивых к коллизиям . По этой причине его называют «криптополным». Наконец, в отличие от многих других видов криптографии, запутывание неотличимости продолжает существовать, даже если P=NP (хотя в этом случае его пришлось бы конструировать по-другому), хотя это не обязательно означает, что iO существует безоговорочно.

Хотя идея запутывания криптографического программного обеспечения существует с 1996 года, запутывание неотличимости было впервые предложено Бараком и др. (2001), которые доказали, что iO существует, если P=NP. Для случая P≠NP (который сложнее, но и более правдоподобен) ), прогресс был медленнее: Garg et al. (2013) предложил конструкцию iO, основанную на предположении о вычислительной сложности, относящемся к полилинейным картам , но это предположение позже было опровергнуто. Построению, основанному на «хорошо обоснованных предположениях» (предположениях о надежности, которые были хорошо изучены криптографами и, таким образом, широко считались безопасными), пришлось подождать до Джайн, Лин и Сахаи (2020). (Даже в этом случае одно из этих предположений, использованных в предложении 2020 года, не защищено от квантовых компьютеров .)

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

Формальное определение

Более широкий охват этой темы см. в разделе «Вычислительная неотличимость» .

Позволять ${\mathcal {iO}}$ — некоторый однородный вероятностный алгоритм с полиномиальным временем . Затем ${\mathcal {iO}}$ называется обфускатором неотличимости тогда и только тогда, когда он удовлетворяет обоим следующим двум утверждениям:

• Полнота или функциональность : для любой логической схемы C входной длины n и входного $x\in \{0,1\}^{n}$, у нас есть
  $$\Pr[C'(x)=C(x):C'\leftarrow {\mathcal {iO}}(C)]=1.$$
• Неотличимость : для каждой пары цепей. $C_{0},C_{1}$ одинакового размера k , реализующие одну и ту же функциональность, распределения $\{{\mathcal {iO}}(C_{0})\}$ и $\{{\mathcal {iO}}(C_{1})\}$ вычислительно неотличимы. Другими словами, для любого вероятностного противника A с полиномиальным временем существует пренебрежимо малая функция $\varepsilon (k)$ ( т.е. функция, которая со временем растет медленнее, чем $1/p(k)$ для любого многочлена p ) такого, что для любой пары цепей $C_{0},C_{1}$ того же размера k , которые реализуют одну и ту же функциональность, мы имеем
  $$|\Pr[A({\mathcal {iO}}(C_{0}))=1]-\Pr[A({\mathcal {iO}}(C_{1}))=1]|\leq \varepsilon (k).$$

История

В 2001 году Барак и др., показав, что обфускация черного ящика невозможна, также предложили идею обфускатора неотличимости и построили неэффективный. Хотя это понятие казалось относительно слабым, Голдвассер и Ротблюм (2007) показали, что эффективный обфускатор неотличимости будет наилучшим из возможных обфускаторов, а любой наилучший обфускатор будет обфускатором неотличимости. (Однако для неэффективных обфускаторов не существует наилучшего обфускатора, если полиномиальная иерархия не рухнет на второй уровень. )

Программная с открытым исходным кодом была создана в 2015 году. реализация кандидата iO

Конструкции-кандидаты

Барак и др. (2001) доказали, что неэффективный для схем существует обфускатор неотличимости; то есть лексикографически первая схема, вычисляющая ту же функцию. Если выполняется P = NP , то обфускатор неотличимости существует, даже если никакого другого вида криптографии не существует.

Кандидатная конструкция iO с доказуемой безопасностью при конкретных предположениях о жесткости, относящихся к многолинейным картам, была опубликована Гаргом и др. (2013), но позже это предположение было признано недействительным. (Ранее Гарг, Джентри и Халеви (2012) построили возможную версию полилинейной карты, основанную на эвристических предположениях. )

Начиная с 2016 года Лин начал исследовать конструкции iO на основе менее строгих версий полилинейных отображений, строя кандидата на основе карт степени до 30 и, в конечном итоге, кандидата на основе карт степени до 3. Наконец, в 2020 году Джайн, Лин и Сахаи предложили конструкцию iO, основанную на симметричном внешнем алгоритме Диффи-Хельмана , обучении с ошибками и предположениях об обучении плюс шум . а также существование суперлинейного растяжения псевдослучайного генератора в классе функций NC ⁰ . (Существование псевдослучайных генераторов в NC ⁰ (даже при сублинейном растяжении) была давней открытой проблемой до 2006 года. ) Вполне возможно, что эту конструкцию можно сломать с помощью квантовых вычислений , но существует альтернативная конструкция, которая может быть защищена даже от этого (хотя последняя опирается на менее устоявшиеся предположения о безопасности).

Практичность

Были попытки реализовать и протестировать кандидатов iO. В 2017 году произошла обфускация функции $x_{1}\wedge x_{2}\wedge \dots \wedge x_{32}$ при уровне безопасности 80 бит создание заняло 23,5 минуты и составило 11,6 ГБ со временем оценки 77 мс. Кроме того, запутывание схемы шифрования Advanced Encryption Standard с уровнем безопасности 128 бит будет иметь размер 18 Пбайт и время оценки около 272 лет.

Существование

Для более широкого освещения этой темы см. Проблема P и NP § P ≠ NP .

Полезно разделить вопрос о существовании iO, используя Рассела Импальяццо . «пять миров» это пять различных гипотетических ситуаций, связанных со сложностью в среднем случае :

• Алгоритма : В этом случае P = NP , но iO существует.
• Эвристика : в этом случае задачи NP в среднем просты; иО не существует.
• Пессиланд : В данном случае BPP ≠ NP, но односторонних функций не существует; в результате iO не существует.
• Minicrypt : в этом случае существуют односторонние функции , но безопасной криптографии с открытым ключом нет ; iO не существует (поскольку известны явные конструкции криптографии с открытым ключом из iO и односторонние функции).
• Криптомания : в этом случае безопасная криптография с открытым ключом существует, но iO не существует.
• Обфустопия : В этом случае считается, что iO существует.

Возможные применения

Обфускаторы неотличимости, если они существуют, могли бы использоваться для огромного количества криптографических приложений, настолько, что их стали называть «центральным узлом» криптографии. «жемчужина криптографии», или «крипто-полный». Конкретно, обфускатор неотличимости (с дополнительным предположением существования односторонних функций ) можно использовать для создания следующих видов криптографии:

• Обфускация неотличимости программ в модели оперативной памяти и для машин Тьюринга
• IND-CCA – безопасная криптография с открытым ключом
• Короткие цифровые подписи
• IND-CCA — безопасной инкапсуляции ключей. схемы
• разглашением Неинтерактивные доказательства с нулевым и краткие неинтерактивные аргументы.
• Параллельные протоколы с постоянным циклом с нулевым разглашением
• Полилинейные карты с ограниченными полиномиальными степенями
• Инъективные функции-ловушки
• Полностью гомоморфное шифрование
• Шифрование свидетеля
• Функциональное шифрование
• Совместное использование секретов для любого монотонного NP-языка.
• Получестный забывчивый трансфер
• Отклоняемое шифрование (как с возможностью отрицания отправителя, так и с полным отрицанием)
• Многосторонний неинтерактивный обмен ключами
• Адаптивно безопасная сжатая искажённая оперативная память
• Корреляционные трудноразрешимые функции
• Шифрование на основе атрибутов
• Не обращающий внимания трансфер
• Розыск предателей
• Схемы градуированного кодирования

Кроме того, если существуют iO и односторонние функции, то проблемы класса сложности PPAD доказуемо сложны.

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

См. также

• Запутывание черного ящика , более сильная форма запутывания, оказалась невозможной.