Может ли полностью гомоморфное шифрование использоваться для выполнения забытого кода?

Прочитав этот ответ некоторое время назад, я заинтересовался полностью гомоморфным шифрованием. Прочитав введение в диссертацию Джентри, я начал задаваться вопросом, может ли его схема шифрования использоваться для выполнения забытого кода, как определено в третьем абзаце.

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

Под забывчивым выполнением кода я имею в виду, что мы шифруем часть кода предназначенную для решения некоторой проблемы P, и отправляем ее во враждебную среду. Противник хочет использовать C, чтобы решить P , но мы не хотим, чтобы он знал, как работает C. Если у него есть вход I для P , он может зашифровать I и затем использовать (некоторую схему шифрования на C ) с I , который затем возвращает (не зашифрованный) выходной O (решение P для ввода $C$$P$$C$$P$$C$$I$$P$$I$$C$$I$$O$$P$$I$). Схема шифрования гарантирует, что злоумышленник никогда не узнает, как работает фрагмент кода, то есть для него он работает как оракул.

Основное практическое использование (я могу думать) для такой схемы шифрования было бы сделать пиратство более трудным или даже невозможным.

Причина, по которой я думаю, что это может быть возможно при использовании полностью гомоморфной схемы шифрования, заключается в том, что мы можем выполнять произвольные схемы на зашифрованных данных, в частности на универсальной машине Тьюринга. Затем мы можем зашифровать код, как если бы это были данные, а затем использовать схему для универсальной машины Тьюринга на этих зашифрованных данных для выполнения кода.

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

Я могу придумать несколько проблем, которые могут вызвать проблемы с этим подходом. Во-первых, если мы используем полностью гомоморфное шифрование без изменений, результат вычисления ( ) будет зашифрован. Поэтому для противника, желающего использовать ваш код для решения P, было бы бесполезно . Хотя это может быть полезно, скажем, для облачных вычислений, это не то, чего я хочу достичь.$O$$P$

Во-вторых, поскольку мы используем схемы, а не произвольные машины Тьюринга, мы не можем использовать произвольные объемы памяти: мы ограничены заранее определенным объемом памяти. Это означает, что если мы хотим запустить программу таким образом, ее объем памяти всегда будет одинаковым, а именно пиковое использование памяти.

Наконец, используемые константы почти наверняка уничтожат любое практическое использование такой системы, но я думаю, что идея, тем не менее, интересна.

К сожалению, есть результат, который теоретически запрещает «забывчивое выполнение кода»:

Боаз Барак, Одед Голдрайх, Рассел Импальяццо, Стивен Рудич, Амит Сахай, Салил Вадхан и Ке Ян. О (Im) возможности запутывания программ , ПРЕИМУЩЕСТВА В КРИПТОЛОГИИ - КРИПТО 2001.

Вот ссылки:

• http://www.wisdom.weizmann.ac.il/~oded/p_obfuscate.html
• http://eprint.iacr.org/2001/069
• http://www.springerlink.com/content/telalqdcx3n600uf/

Аннотация гласит:

Неформально, обфускатор - это (эффективный, вероятностный) «компилятор», который принимает в качестве входных данных программу (или схему) P и создает новую программу O ( P ), которая имеет те же функциональные возможности, что и P, но в некотором смысле «нечитаемая» , Обфускаторы, если они существуют, будут иметь широкий спектр криптографических и теоретико-сложных приложений, от защиты программного обеспечения до гомоморфного шифрования до теоретико-сложных аналогов теоремы Райса. Большинство этих приложений основаны на интерпретации условия «нечитаемости» в обфускации как означающего, что O ( P $\cal O$$P$$\cal O(P)$$P$$\cal O(P)$это «виртуальный черный ящик» , в том смысле , что все , можно эффективно вычислить данную , можно также эффективно вычислить данный оракул доступ к P .$\cal O(P)$$P$

$\cal F$$\pi$$f$$\cal F$$\pi(f)$$f$$\cal F$$\pi(f)$ гораздо лучше, чем случайные догадки.

$\rm{TC}$ $0$

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

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

Учитывая этот результат невозможности, есть два (не дизъюнктных) способа, которыми можно ослабить определение: либо ограничивая классы программ / функций, которые требуется запутать, либо давая более слабое представление о безопасности.

Второй подход, возможно, возможен, и мы отмечаем некоторые слабые понятия, подобные запутыванию, в нашей статье. Тем не менее, обратите внимание, что наша атака полностью восстанавливает исходный код какой-либо программы, как бы она ни была запутана. Таким образом, вам нужно как-то сделать определение безопасности, которое тривиализируется для случая наших контрпримеров.

Первый подход был сделан для каждой ограниченной функциональности (например, точечных функций), но опять-таки нужно убедиться, что класс не содержит нашего контрпримера, что примерно означает, что он не должен содержать псевдослучайных функций.