Теоретические основания
Пусть обфускатор – это (эффективный, вероятностный) «компилятор», который по входу программы (схеме) P выдает новую программу О(P), удовлетворяющую следующим условиям:
1. Условие функциональности. Обфусктор O(P) должен вычислять ту же самую функцию, что и программа P.
2. Условие (свойство) «виртуального черного ящика». «Все, что может быть вычислено эффективным образом из обфускатора O(P), может быть эффективно вычислено при оракульном доступе к программе P».
Одна из интерпретаций определения, приведенного выше, неформально можно объяснить так, что: во-первых, должна сохраняться функциональная эквивалентность P и O(P) и, во-вторых, все что противник мог бы получить при доступе к обфусцирующей программе, он мог бы с таким же успехом получить при доступе к некоторому «черному ящику».
Основной результат работы [BGI] заключается в том, что даже при очень слабой формализации, полная обфускация программ является теоретически невозможной. Это доказывается посредством построения (посредством односторонних функций) семейства функций F, которые являются необфусцирующими
в том смысле, что существует свойство p :F®{0,1} такое, что:
· по данной программе (схеме), которая вычисляет функцию fÎF, значение p(f) может быть также эффективно вычислено;
· по данному оракульному доступу к (случайно выбранной) функции fÎF, никакой эффективный алгоритм не может вычислять p(f) лучше, чем случайным угадыванием.
Таким образом, при таком определении семейства функций F, не существует способов обфускации программ при вычислении F, даже если обфускация предназначена для сокрытия лишь одного бита информации об этой функции (т.е. p(f)) и даже если обфускатор имеет неограниченное время вычислений.
Приводятся примеры некоторых, казалось бы потенциальных приложений обфускаторов для программ, реализующих схемы цифровой подписи, схемы шифрования, и псевдослучайные функции, однако обфускация для которых не возможна.
Этот результат о теоретической невозможности полной обфускации расширен различными путями, включая обфускаторы, которые: (a) не обязательно вычисляют за полиномиальное время, (б) только приблизительно сохраняют функциональные возможности (аппроксимирующие обфускаторы) и (в) должны работать только для очень ограниченных моделей вычислений.
