Неформально, обфускатор O — это эффективный и вероятностный «компилятор» (алгоритм), который принимает на вход программу (или схему из фунциональных элементов) P и выдаёт на выходе новую программу O(P), имеющую «запутанное» строение и ту же функциональность что и P. Обфускация, если бы она существовала, могла бы широко применяться в криптографии, а также при решении различных теоретико-сложностных задач, начиная от защиты программного обеспечения и гомоморфного шифрования и заканчивая доказательством теоретико-сложностных аналогов теоремы Райса.
Обфускация основывается на понятии термина «запутанного» строения. Под данным термином понимается то, что O(P) является «черным ящиком» для конечного пользователя. Если что-то может быть эффективно вычисленно по коду программы O(P), то это должно также легко вычисляться в модели вычислений с оракулом, имеющим доступ к оригинальной программе P.
В данной работе мы начнём исследование понятия обфускации в рамках строгой математической модели. Мы покажем, что универсальная обфускация в том смысле, под которым её обычно понимают, невозможна. Мы докажем это построением такого семейства эффективно вычисляемых функций P, которые являются необфусцируемыми в принципе, в том смысле что имея любое эффективное представление O(P), можно эффективно восстановить P, однако в модели вычисления с оракулом невозможно восстановить даже единичный бит информации о P со сколь-либо значимой вероятностью.
Мы обобщим наш результат на следующие случаи: если алгоритм обфускации не ограничен полиномиально по времени, если O(P) вычисляет P с некоторой погрешностью, если мы обфусцируем функции только из класса TC0. Мы также ограничим потенциальные области применения обфускации, построив необфусцируемые схемы подписи, алгоритмы шифрования и семейства генераторов псевдослучайных чисел.
Ссылка на полный перевод в формате PDF
ссылка на оригинал статьи http://habrahabr.ru/post/270409/
Добавить комментарий