Неразличимость, запутывание

Тип криптографического программного обеспечения для обфускации

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

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

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

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

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

Пусть — некоторый равномерный вероятностный полиномиальный алгоритм. Тогда называется обфускатором неразличимости тогда и только тогда, когда он удовлетворяет обоим из следующих двух утверждений: ^{[5] [6] [7]} ${\displaystyle {\mathcal {iO}}}$ ${\displaystyle {\mathcal {iO}}}$

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

История

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

Реализация программного обеспечения с открытым исходным кодом для кандидата iO была создана в 2015 году. ^[10]

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

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

Предполагаемая конструкция iO с доказуемой безопасностью при конкретных предположениях о прочности, касающихся мультилинейных отображений, была опубликована Гаргом и др. (2013), ^{[2] [11] [3],} но это предположение позже было опровергнуто. ^{[11] [3]} (Ранее Гарг, Джентри и Халеви (2012) построили предполагаемую версию мультилинейного отображения на основе эвристических предположений. ^[4] )

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

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

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

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

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

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

Потенциальные приложения

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

• Обфускация неразличимости для программ в модели RAM ^[5] и для машин Тьюринга ^{[16] [17]}
• IND-CCA - безопасная криптография с открытым ключом ^[18]
• Короткие цифровые подписи ^[18]
• IND-CCA - безопасные схемы инкапсуляции ключей ^[18]
• Идеально нулевое разглашение неинтерактивных доказательств с нулевым разглашением и краткие неинтерактивные аргументы ^[18]
• Конкурентные протоколы с нулевым разглашением ^[5]
• Мультилинейные отображения с ограниченными степенями полиномов ^[5]
• Инъективные функции-ловушки ^[18]
• Полностью гомоморфное шифрование ^[5]
• Шифрование свидетелей ^{[5] [2]}
• Функциональное шифрование ^[2]
• Разделение секрета для любого монотонного языка NP ^[5]
• Получестный забывчивый перевод ^[18]
• Отрицаемое шифрование (как отрицающее отправителя, так и полностью отрицаемое) ^{[18] [5] [2]}
• Многосторонний, неинтерактивный обмен ключами ^[5]
• Адаптивно защищенная сжатая искаженная оперативная память ^[5]
• Корреляционные трудноразрешимые функции ^[5]
• Шифрование на основе атрибутов ^[5]
• Незаметный перевод ^[2]
• Отслеживание предателя ^[2]
• Схемы градуированного кодирования ^[2]

Кроме того, если существуют iO и односторонние функции, то задачи класса сложности PPAD являются доказуемо сложными. ^{[5] [19]}

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

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

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

Ссылки

1. Klarreich, Erica (2014-02-03). «Прорыв в криптографии может сделать программное обеспечение невзламываемым». Quanta Magazine . Архивировано из оригинала 2022-04-14 . Получено 2019-02-15 .
2. Пелле--Мэри, Элис (26 мая 2020 г.). "Co6GC: Обфускация программы | COSIC". www.esat.kuleuven.be . Архивировано из оригинала 11 ноября 2020 г. . Получено 22 августа 2021 г. .
3. Кларрайх, Эрика (2020-10-10). «Ученые-компьютерщики достигли „жемчужины короны“ криптографии». Журнал Quanta . Архивировано из оригинала 2022-05-07 . Получено 2020-11-10 .
4. Barak, Boaz (29 декабря 2020 г.). «Новые разработки в области запутывания неразличимости (iO) | Институт теории вычислений Саймонса». simons.berkeley.edu . Архивировано из оригинала 22 августа 2021 г. . Получено 22 августа 2021 г. .
5. Jain, Aayush; Lin, Huijia ; Sahai, Amit (2020). "Неразличимость запутывания от обоснованных предположений". Архив Cryptology ePrint . arXiv : 2008.09317 . Архивировано из оригинала 2022-03-03 . Получено 2020-11-16 .
6. Moran, Tal; Rosen, Alon (7 октября 2013 г.). «В Пессиленде нет обфускации неразличимости» (PDF) . Архив IACR Cryptology ePrint . Архивировано (PDF) из оригинала 19 января 2022 г. . Получено 15 января 2022 г. .
7. Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke (2012-05-03). "О (не)возможности запутывания программ" (PDF) . Journal of the ACM . 59 (2): 6:1–6:48. doi :10.1145/2160158.2160159. ISSN  0004-5411. S2CID  2409597. Архивировано (PDF) из оригинала 25.02.2023 . Получено 30.06.2024 .
8. Klarreich, Erica (2014-01-30). «Совершенствуя искусство разумной бессмыслицы». Quanta Magazine . Архивировано из оригинала 2021-08-06 . Получено 2021-08-22 .
9. Goldwasser, Shafi ; Rothblum, Guy N. (2007). "On Best-Possible Obfuscation". В Vadhan, Salil P. (ред.). Theory of Cryptography . Lecture Notes in Computer Science. Vol. 4392. Berlin, Heidelberg: Springer. pp. 194–213. doi :10.1007/978-3-540-70936-7_11. hdl : 1721.1/129413 . ISBN 978-3-540-70936-7. Архивировано из оригинала 2022-01-19 . Получено 2021-08-22 .
10. Banescu, Sebastian; Ochoa, Martín; Kunze, Nils; Pretschner, Alexander (2015). "Idea: Benchmarking Indistinguishability Obfuscation – A Candidate Implementation" (PDF) . В Piessens, Frank; Caballero, Juan; Bielova, Nataliia (ред.). Engineering Secure Software and Systems . Lecture Notes in Computer Science. Vol. 8978. Cham: Springer International Publishing. pp. 149–156. doi :10.1007/978-3-319-15618-7_12. ISBN 978-3-319-15618-7. Архивировано (PDF) из оригинала 2021-08-22 . Получено 2021-08-22 .
11. Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2013). "Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . IEEE. стр. 40–49. doi :10.1109/focs.2013.13. ISBN 978-0-7695-5135-7.
12. Эпплбаум, Б; Ишай, Ю; Кушилевиц, Э (2006). «Криптография в NC0» (PDF) . SIAM Journal по вычислительной технике . 36 (4): 845–888. дои : 10.1137/S0097539705446950. Архивировано из оригинала (PDF) 30 ноября 2021 г. Проверено 11 ноября 2020 г.
13. Импальяццо, Рассел (19–22 июня 1995 г.). «Личный взгляд на сложность в среднем случае». Труды по теории структуры в теории сложности. Десятая ежегодная конференция IEEE . стр. 134–147. doi :10.1109/SCT.1995.514853. ISBN 0-8186-7052-5. S2CID  2154064. Архивировано из оригинала 27 июля 2022 г. . Получено 27 июля 2022 г. .
14. Bitansky, Nir; Nishimaki, Ryo; Passelègue, Alain; Wichs, Daniel (30 августа 2017 г.). «From Cryptomania to Obfustopia through Secret-Key Functional Encryption» (PDF) . Архив IACR Cryptology ePrint . Архивировано (PDF) из оригинала 20 января 2022 г. . Получено 15 января 2022 г. .
15. Garg, Sanjam; Pandey, Omkant; Srinivasan, Akshayaram; Zhandry, Mark (2017). «Breaking the Sub-Exponential Barrier in Obfustopia». В Coron, Jean-Sébastien; Nielsen, Jesper Buus (ред.). Advances in Cryptology – EUROCRYPT 2017. Lecture Notes in Computer Science. Vol. 10212. Cham: Springer International Publishing. pp. 156–181. doi :10.1007/978-3-319-56617-7_6. ISBN 978-3-319-56617-7. Архивировано из оригинала 2022-01-15 . Получено 2022-01-15 .
16. Коппула, Венката; Левко, Эллисон Бишоп; Уотерс, Брент (2015-06-14). "Неразличимость обфускации для машин Тьюринга с неограниченной памятью" (PDF) . Труды сорок седьмого ежегодного симпозиума ACM по теории вычислений . STOC '15. Портленд, Орегон, США: Ассоциация вычислительной техники. стр. 419–428. doi :10.1145/2746539.2746614. ISBN 978-1-4503-3536-2. S2CID  1368494. Архивировано (PDF) из оригинала 2021-09-11 . Получено 2021-09-11 .
17. Ananth, Prabhanjan; Jain, Abhishek; Sahai, Amit (2017). «Неразличимость обфускации для машин Тьюринга: постоянные накладные расходы и амортизация» (PDF) . В Katz, Jonathan; Shacham, Hovav (ред.). Достижения в криптологии – CRYPTO 2017 . Конспект лекций по информатике. Том 10402. Cham: Springer International Publishing. стр. 252–279. doi :10.1007/978-3-319-63715-0_9. ISBN 978-3-319-63715-0. Архивировано (PDF) из оригинала 2021-09-11 . Получено 2021-09-11 .
18. Sahai, Amit; Waters, Brent (2013). «Как использовать обфускацию неразличимости: отрицаемое шифрование и многое другое». Архив Cryptology ePrint . Архивировано из оригинала 2022-02-03 . Получено 2021-03-14 .
19. Bitansky, Nir; Paneth, Omer; Rosen, Alon (октябрь 2015 г.). «О криптографической сложности нахождения равновесия Нэша». 56-й ежегодный симпозиум IEEE по основам компьютерной науки 2015 г. стр. 1480–1498. doi :10.1109/FOCS.2015.94. ISBN 978-1-4673-8191-8. S2CID  217890992. Архивировано из оригинала 2024-06-10 . Получено 2024-06-30 .
20. Ашаров, Гилад; Сегев, Гил (2015). «Ограничения мощности обфускации неразличимости и функционального шифрования». Архив Cryptology ePrint . Архивировано из оригинала 21.01.2022 . Получено 14.03.2021 .