Структура компилятора одноразовой программы

Одно из основных и неотъемлемых свойств традиционных компьютерных программ заключено в том, что пользователь может скопировать программу и запустить её любое число раз на любых входных данных. В некоторых случаях такое поведение пользователя нежелательно и разработчик программы хотел бы ограничить число повторных запусков программы. Подобные возможности могут быть полезны при работе с криптовалютой, блокчейном и цифровой подписью [1].

Одноразовые программы (one-time program) являются решением этой проблемы. Однако, невозможно решить данную проблему с использование только программных средств. Для реализации необходимого поведения необходима комплексная программно-аппаратная система, контролирующая число запуска программ и не допускающая утечек информации о коде программы. Важным компонентов такой системы является компилятор – программа, преобразующая традиционную программу в одноразовую программу. Преобразование осуществляется с помощью упаковки традиционной программы в соответствующий модуль-обёртку, предназначенную для запуска на системе и защищающий данные и программу.

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

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

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

Компилятор преобразует любую машину Тьюринга T в одноразовую программу P, которая удовлетворяет двум интуитивным свойствам (функциональность и однократная секретность), описанным выше. Что касается функциональности, для любого x ∈{0,1}^n когда программа запускается один раз на входе x, она выдает T(x), скажем P (x) = T (x). Что касается одноразовой секретности, для любого PPT противник A, существует PPT-симулятор S с одноразовым доступом к машине T. Симулятор получает выходные данные машины, время работы и использование пространства на одном входе по своему выбору, и его время работы является полиномиальным от времени работы машины T в худшем случае (и в n). Для любой машины T следующие два распределения неразличимы [3]. Во-первых, вывод злоумышленника A, когда он запускается с произвольным доступом к одноразовой программе P (то есть полный доступ к компоненту программного обеспечения и черный ящик к компоненту оборудования). Во-вторых, выход симулятора с одноразовым доступом к Т.

Рассмотренный в статье компилятор является необходимой частью программноаппаратной системы для работы одноразовых и k-разовых программ. Использование таких средств является перспективным в таких областях, как блокчейн, цифровая валюта, а также при распространении и работе с объектами авторского права.