Comments 20
Интересные примеры с оценкой размеров файла. Кстати, есть еще видео с подробным разбором скомпилированного таким образом кода.
Можем ли мы в качестве входной переменной указать одно число, но внутри приложения разделить его на два тривиальными операциями побитового сдвига (целочисленное деление) и битовой маской (так же остаток от деления)?
p.s. можно не вырожденный пример использования такого компилятора?
Тема крайне интересная, но Я для нее довольно тупой.
А скажите, кто разбирается в вопросе - возможны ли ПГШ вычисления?
То есть ты даешь серверу образ программы, он его выполняет на твоих приходящих входных данных, но не знает ничего ни о данных, ни о программе?
Хотя бы теоретически.
Чисто теоретически программа может быть интерпретатором, который "исполняет" входящие данные.
Соответственно, сервер может знать об интерпретаторе (который собственно может быть и частью сервера), но он не будет знать что именно он исполняет.
Только если он тьюринг-полный.
Ограничения, накладываемые требованиями криптографии могут убить эту красивую мысль
Ну мне кажется что какой-нибудь брейнфак на заданное число итераций можно реализовать даже сейчас. Тьюринг-полным он не будет потому что количество итераций ограничено, правда. Но в прикладных задачах тьюринг-полнота не всегда нужна. Взгляните хотя бы на eBPF, который специально не тьюринг-полный, но применяется еще как.
Опять же, с точки зрения математики, исполнение программы ничем не отличается от вычислений (см. Лябмда-исчисление, например), так что всякая функциональщина наверное должна работать только в путь. Мне кажется тут даже можно будет решить вопрос с ограничением на количество итераций.
zero-knowledge с появлением криптокоинов и смартконтрактов только растёт и пахнет.
Для нематематиков - гомоморфность, это когда ты производишь какую-то операцию над объектом (в данном случае шифруешь), а потом отправляешь в обработку в таком виде и результат не будет отличаться от случая, если ты отдашь исходные данные на обработку, а уже потом пошифруешь. Кажется в 18 году гуглеры как раз выкатывали доказательство про подобное шифрование, а теперь видимо смогли написать компилятор.
Подоплёкой было то, что как раз начался бум нейронных сетей и часть картинок случайно могла быть взята из частных данных, поэтому для того чтобы обезопасить хотелось бы как-то пошифровать эти данные, чтобы архитектор нейросети не мог узнать, с какими данными он работает внутри. Нейросети соответственно учатся обработке на таких данных и когда наступает момент выйти в поля, то на вход подаётся уже нешифрованные данные, а преобразование соответствует тому, на что её тренировали.
Смартконтракты - это похожая штука, но в профиль.
Они открытые, просто исполняются на рандомных мощностях в сети.
Гомоморфность, как Я понимаю, похоже на то, что вы описали - шифруешь данные, отдаешь на обработку, расшифровываешь - и получаешь результат, как если бы обработал сам, при этом тот, кто обрабатывает не узнает ничего о данных.
Про нейросети впервые слышу, мысль интересная, но не представляю, насколько это будет дорого.
Смартконтракты это в первую очередь про надёжную подпись этих самых контрактов при помощи асинхронных алгоритмов. Валидатор контракта в большинстве текущих архитектур расшифровывать данные своим ключём. zk соовтвественно пытается избавиться от этого, одним из вариантов которого является то самое гомоморфное шифрование.
насколько это будет дорого.
вот этот момент не понял. Что именно дорого? Физически большая часть данных для нейросетей уже хранится на шифрованных носителях, поэтому на шифрование трат сверху наверное не будет. Использование ПГШ по идее не должно давать каких-то дополнительных накладных вещей при разработке нейросети, то бишь там букваьлно будет что-нибудь типа 'process_data(data, fhe_encrypted = True)`. Разработка алгоритма и компилятора саоме дорогое, насколько я понимаю, но нам этим не заниматься.
Описанный вами сценарий возможен. Но для такой реализации как раз и нужен подобный компилятор.
Но такое получится только когда и данные и алгоритм используют один и тот же контекст(ключ).
Классический сценарий предполагает отправку всех данных(входных и констант алгоритма) в зашифрованном виде в облако, обработка под FHE и возврат зашифрованного результата.
Например, недавно мы пробовали LinearRegression так реализовать, все получилось:
Плюсы:
1. Точность почти как у незашифрованной версии
2. Почти нет различия в размере передачи данных
Минусы:
1. Время обучения больше примерно в 45 раз
2. Валидация только на стороне отправителя данных
3. Слишком много деталей нужно знать для реализации(все зависит от размеров матриц)
4. Инференс зависит от ключа
Как минимум, очень сильно обфусцировать можно. Когда-то давно размышлял над подобным, и идея была следующая.
Создать виртуальную машину из M блоков одинаковой длины, скажем в N бит, которые по сути являются просто числами. В каждом блоке должно быть отведено какое-то количество бит для обмена информацией между собой, бит регистров, служебных бит, и возможно какое-то избыточное количество бит для повышения стойкости к реверс инжинирингу.
У блока будет конечное количество всех возможных состояний, для каждого из которых будет ровно одно следующее. Все эти состояния и переходы можно заранее просчитать, и представить массивом чисел вида "state[current] = next". После чего номера состояний можно перемешать хорошим рандомом, и используя их создать обфусцированный массив. На вычисляющей машине будет только обфусцированный массив, а карта соответствий значений из изначального и обфусцированного масссива будет служить ключем.
Упрощенный пример для понимания. Допустим блок имеет например структуру "RRRRXXYY", где XX и YY биты входных регистров, RRRR биты регистра результата, а операция скажем сумма. Тогда в изначальном массиве индексу "0000.01.10" будет соответствовать число "0011.00.00" (разделил регистры точками для удобства чтения). В изначальном массиве это будет "state[6] = 48". А после рандомизации эти же два состояния могут оказаться любыми числами, например "state[37456] = 91204". Главное, чтобы направление всех переходов сохранялись.
Само собой, в реальной реализации входные и выходные регистры могут совмещаться для экономии, будет много других служебных бит, и сами операции скорее всего будут другого уровня абстракций (логические вентили, например), и т.д. и т.п., но общий принцип примерно такой.
Каждый шаг каждый из M блоков виртуальной машины переключается в свое следующее состояние. Самая сложная часть, вероятно, будет общением между блоками - условная "шина" должна вещать данные всем блокам сразу, а блоки у себя внутри как-то понимать, им это адресовано, или нет. Большая часть бит скорее всего на эту адресацию и уйдет. Соответственно самих блоков тоже понадобится много. Они, кстати, не обязательно должны быть однотипными, и возможно несколько массивов состояний будут удобней при том же суммарном объеме. Ввод вывод - отдельная проблема.
Работать все это будет очень медленно, зато весьма обфусцированно. Тут конечно, нужно вспомнить принцип "каждый может создать шифр, который сам не может взломать", а поскольку я не спец по криптографии, даже теоретическая эффективность описанного выше сомнительна. Тем более, что я даже не пытался все это реализовать в коде, лишь на уровне идеи, и может даже оказаться что это толком невозможно.
Если следующий шаг жестко задан, то как делать управление потоком вычисления? Всякие if, goto и while?
В ПГШ это возможно благодаря тому что все вычисление от начала до конца - это одна огромная логическая формула, которая внутри себя параллельно "вычисляет" все возможные исходы, а потом игнорирует все лишнее, потому что x && false == false и x && true == x.
Если следующий шаг жестко задан, то как делать управление потоком вычисления?
Он и не задан жестко. Это же виртуальная машина, просто реализованная с промежуточными слоями абстракции. У нее помимо регистров есть и стек, и куча, и все что понадобится.
Еще один пример для аналогии. В игре Конвея Жизнь можно используя фигуры реализовать логически вентили, а используя их - тьюринг полный компьютер. Саму Жизнь мы реализуем используя lookup table. Эту самую таблицу мы заранее материализуем, перемешиваем, и сохраняем. Скрываемый алгоритм либо конструируем руками, либо пишем генератор, после чего берем полученное состояния поля, конвертируем его под сохраненную ранее перемешанную таблицу. И уже в таком виде это можно запускать на посторонней машине. По общему принципу это совпадает с тем, что я пытался описать выше, только еще менее эффективно.
Полезно было бы, если этот подход к БД был применим. Особенно для операций сравнения строк или для like например. Чтобы слив базы не приводил к раскрытию информации, если у атакубщего нет доступа к ключу шифрования.
расширение для postgres
MuchPIR is Private Information Retrieval using Homomorphic Encryption implemented as a C/C++ Aggregate extension to Postgres.
Компилятор с полностью гомоморфным шифрованием от Google