Массово предлагаются услуги для всех желающих по выполнению вычислений на высокопроизводительных компьютерах, реализованных в виде облачных и других систем, от компаний предоставляющих подобные сервисы в публичных сетях.
Однако использование публичных вычислительных сетей несёт для их потребителей риски:
- Утечки приватных данных в процессе их обработки на внешнем устройстве или в процессе передачи данных;
- Возможность наличия искажений в получаемых результатах вычислений на внешнем устройстве или в процессе передачи данных. При этом, даже многократный повтор вычислений с одними и теми же исходными данными не позволит обнаружить наличие этих искажений если они носят системный, а не случайный характер.
Мы не будем рассматривать вопросы утечки приватных данных или искажений в результатах вызванных в процессе передачи данных, оставляя эту тему классической криптографии по обеспечению закрытого канала связи требуемой степени надёжности.
Рассмотрим вопрос, когда сам внешний вычислитель может подвержен компрометации, и на нём самом возможны и анализ приватных данных в процессе обработки, и искажение результатов вычислений, и постараемся решить задачу, которую сформулируем следующим образом:
- Требуется обеспечить механизм обработки приватных данных на внешнем вычислительном устройстве, который, при сохранении возможностей использования типовых алгоритмов, позволил бы сделать невозможным (то есть достаточно сложным) выявление значений приватных данных, а также позволял бы выявлять и исправлять возможные искажения в результатах вычислений, вносимые случайно или системно.
- Поскольку, несомненно, потребуется некоторая дополнительная обработка заданий и результатов, на стороне потребителя, то желательно, чтобы сложность(цена, время) такой обработки была значительно меньше сложности(цены, времени) решения основной задачи – иначе у потребителя нет смысла для проведения вычислений на внешних публичных сетях.
- Также, несомненно, может возрасти общее количество вычислений, отдаваемых на внешний вычислитель, поскольку любое внесение избыточности в исходные данные, либо с целью исключения их однозначного определения, либо с целью контроля за их достоверностью, несомненно потребует обработки большего количества информации. Однако, поскольку внешние вычислительные мощности могут быть увеличены только за счёт большей оплаты со стороны потребителя, то разумное увеличение стоимости не должно являться решающим фактором при выборе алгоритма механизма защиты данных.
Термины и обозначения
Обозначим формулой f(x)=f0? постановку задачи решения математического уравнения.
В качестве отправной точки для рассуждений выберем задачу решения системы линейных уравнений.
Обозначим формулой (x0+ex): f(x0+ex)=f0 принятие в качестве решения задачи значения (x0+ex), где
- x0 — истинное решение задачи,
- ex — искажение добавленное к истинному решению задачи.
Постановка задачи
Требуется найти преобразования задачи Ek и преобразование найденного решения Dk, такие что
- Ek: f(x)=f0? -> g(y)=g0 ?
- (y0+ey): g(y0+ey)=g0
- Dk: (y0+ey) -> (x0+ex)
- (x0+ex): f(x0+ex)=f0
где
- f:R->R и
- g:C->C
При этом должна сохраняться экономическая/временная/или другая выгода от выполнения вычислений на внешнем вычислителе
price( f(x)=f0? -> g(y)=g0? ) + price( (y0+ey) -> (x0+ex) ) << price( f(x)=f0? )
Решение системы линейных уравнений
Рассмотрим задачу решения системы линейных уравнений ax=b, где
- a и b — исходные данные — матрицы с элементами из поля R
- x – искомые данные – матрица с элементами из поля R
Замечания:
- Решение представляет собой множество, являющееся линейной комбинацией векторов фундаментальной системы решений.
- Для упрощения, считаем, что размеры всех элементов матричного уравнения согласованы между собой.
- Полагаем, что сложность вычисления обратной матрицы к произвольной матрице на локальном компьютере значительно больше сложности умножения или сложения двух матриц.
- Также отметим, что множество матриц с элементами из поля R с операциями умножения и сложения являются ассоциативным кольцом с делителями нуля.
Линейные преобразования системы линейных уравнений
- ax=b -> Uax=Ub -> a'x'=b' | a'=Ua, b'=Ub, x=x'
- ax=b -> aV/Vx=b -> a'x'=b' | a'=aV, b'=b, x=Vx'
- ax=b -> a(x-z)=b-az -> a'x'=b' | a'=a, b'=b-az, x=x'+z
Алгоритм защиты вычислений задачи решения системы линейных уравнений
- Сформируем обратимые матрицы U и V и вектор z из случайных величин
- Вычисляем на локальном вычислителе a'=UaV, b'=U(b-az)
- Передаём на внешний вычислитель задачу решения уравнения a'x'=b'
- Используя полученное решение уравнения a'x'=b', вычисляем на локальном вычислителе x=Vx'+z
- Проверка истинности найденного решения может быть выполнена явной подстановкой найденного решения в формулу системы линейных уравнений ax=b
Замечания:
Справедливы формулы ax=b -> UaV/V(x-z)=U(b-az) -> a'x'=b' | a'=UaV, b'=U(b-az), x=Vx'+z
Абстрактный вычислитель
Согласно теории алгоритмов, современные технические устройства, при решении задач обработки данных могут быть представлены в виде конечного абстрактного вычислителя, полностью имитирующем вычисление на любом техническом устройстве.
Модели таких абстрактных вычислителей были предложены Тьюрингом, Марковым и другими.
Будем использовать запись y=x*F для обозначение работы этих вычислителей над исходными данными x по алгорифму F где y – искомые данные.
Последовательное применение нескольких алгорифмов (программа) F1,…,Fn при обработке данных будем обозначать как y=x*F1*…*Fn
Теория алгоритмов, говорит нам, что любой алгоритм (или композиция алгоритмов) имеют эквивалентные алгоритмы, а значит, можно составить алгорифм “уменьшения” количества шагов программы или алгоритм “обфукации” программы для усложнения анализа кода программы, используя запись программы F1*…*Fn как исходные данные для обработки.
Публичный абстрактный вычислитель
Постановка задачи:
Пусть требуется выполнить вычисления y=x*F над исходными данными x по алгорифму F где y – искомые данные.
Замечания:
- При передачи задания на внешний вычислитель мы сообщаем этому вычислителю исходные данные x и алгорифм F, получая в ответ искомые данные y
- В тоже время очевидно, что существуют алгорифмы, обладающие свойствами x = x*E*U и y = y*V*D для любых допустимых x и y. Примеры таких алгорифмов известны из задач криптографии и задач восстановления искажённых данных (коды исправляющие ошибки)
- А значит любая задача вида y=x*F может быть заменена на задачу вида y = x*E*U*F*V*D = (x*E)*(U*F*V)*D = (x*E)*G*D, где G=U*F*V
Алгоритм защиты вычислений на публичном вычислителе
- Возьмём произвольные алгорифмы, обладающие свойствами x = x*E*U и y = y*V*D для любых допустимых x и y, и такие, что алгорифмы E и D не являются слишком затратными для вычисления на локальном вычислителе.
- Составим алгорифм G=U*F*V и используя алгорифм “уменьшения” количества вычислений или алгоритм “обфукации” преобразуем его к программе G’ используя локальный вычислитель.
- Вычислим на локальном вычислителе x’=x*E
- Выполним на внешнем вычислителе задачу y’=x’*G’, сообщив на внешний вычислитель x’ в качестве исходных данных, программу G’ и получив в ответ значение y’.
- Вычислим на локальном вычислителе y=y’*D
Замечания:
- Использование алгорифмов Е и D, полученных из теорий криптографии и восстановления искажённых данных позволит обеспечить защиту приватных данных переданных на внешний вычислитель или полученных от внешнего вычислителя, а также детектировать факты искажения результатов обработки данных на внешнем вычислителе.
Литература
- Кудрявцев В.В, Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985.
- Мальцев А. И. Алгоритмы и вычислимые функции. М.: Наука, 1986.
- МакВильмс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979
- Марков А. А. Введение в теорию кодирования. М.: Наука, 1982
- Карманов В.Г. Математическое программирование. М.: Наука, 2000.
- Турчин В.Ф. Язык программирования РЕФАЛ. Интернет-проект www.refal.net
- Иван Кочуркин @KvanTTT Математические выражения в .NET (разбор, дифференцирование, упрощение, дроби, компиляция). Интернет-публикация habrahabr.ru/post/150043
- @JediPhilosopher Как компьютер сам свой код улучшал, или программируем процесс программирования. Интернет-публикация habrahabr.ru/post/265195
Контакты
- Интернет-адрес проекта: github.com/dprotopopov/cc
Комментарии (29)
mickvav
09.11.2015 00:04+1Проблемы с линейной алгеброй начинаются, когда нужно построить обратимые матрицы с нужными свойствами —
1. Легко вычислимые. (ибо должно быть сильно дешевле построить шифрующие матрицы, чем решить систему локально)
2. Сложно угадываемые (ибо криптграфия, все дела)
3. Хорошо обусловленные (если вы переводами туда-сюда увеличиваете ошибку хотя бы в 100 раз, вся эта кухня на реально нужных задачах оказывается, опять же, уже не нужна). Или надо говорить о публичном нахождении хорошего приближения с дальнейшей локальной доводкой до нужной точности каким-нибудь итерационным методом.
dprotopopov
09.11.2015 00:09да.
Рассматривайте этот текст просто как рассуждения на тему.
В тексте же нет программных кодов, а про матрицы я тоже упоминаю что это не более чем кольцо с делителями нуля.
dprotopopov
09.11.2015 00:10да.
Рассматривайте этот текст просто как рассуждения на тему.
В тексте же нет программных кодов, а про матрицы я тоже упоминаю что это не более чем кольцо с делителями нуля.
koldyr
09.11.2015 08:30не нужно вам всё кольцо, возьмите только мультипликативную группу.
проблема, как написали выше, в построении обратимых матриц. надо переложить эту задачу на внешний вычислитель.
предложение: построить в облаке 2n матриц и обратных к ним и взять произведение n из них.dprotopopov
09.11.2015 23:43построить в облаке 2n матриц и обратных
только надо явно указывать свойства каждой — а то напихают всё из одного класса.
как в ресторане — если закажешь просто пожрать — принесут суп из картошки, рагу из картошки, компот из картошки и десерт из картошки.dprotopopov
09.11.2015 23:56суп из картошки, рагу из картошки, компот из картошки и десерт из картошки — как не комбинируй — одно — выпарил влагу — и хрусти картофельными чипсами.
sysmetic
09.11.2015 10:42А вы знакомы с работой "CryptDB: Protecting Confidentiality with Encrypted Query Processing"? Там предложен несколько другой подход, решающий ту же проблему, и мне он представляется весьма перспективным, потому что не ведет к увеличению требуемой вычислительной мощности (но возможно с некоторым снижением криптостойкости, что пока еще не проанализировано экспертами в области криптоанализа).
dprotopopov
09.11.2015 19:55глянул. что увидел за 5 минут — очередной велосипед по превращению реляционной базы в шифрованную реляционную базу путём добавления ещё одного программного слоя.
у oracle с давних времён шифрование строк таблиц встроено в систему управления базы, но большинство программистов или не знают об этих фичах, а если знают то намеренно не пользуются поскольку стоимость разработки ПО возрастает на порядки.
ведь кроме задачи хранения более важной является система распределения прав.
если несмотря на шифрование данных в таблицах все пользователи продолжают иметь равные права по доступу к данным то проще поместить базу в защищённый периметр — на шифруемый диск в серверной с ограниченным доступом и убедится что из вне общение с устройством возможно только по чётко описанным протоколам и никак иначе.
если имеется ввиду размещение базы в публичном датацентре — для ЛЮБЫХ поситетелей веб-сайтов…
в общем как обычно вся необходимая информация для полного доступа к «шифрованной» базе данных окажется на том же сервере где размещён apache.
да и вопрос хранения данных+их связей — не тема моей публикации.sysmetic
09.11.2015 22:02В статье предлагается шифрование на клиентском ключе при охранении возможности исполнять запросы на сервере, при условии, что сервер НЕ знает клиентского ключа (эта проблема актуальна для публичных облаков, когда клиент не доверяет провайдеру), то есть решается задача, обозначенная в теме Вашего поста.
Что же касается Oracle — то там речь идет о шифровании на ключе, известным серверу, что НЕ решает проблему недоверия к провайдеру.dprotopopov
09.11.2015 22:05Что же касается Oracle — то там есть всё.
если вам знакома только иерархическая модель разделения прав — то все вопросы к царю.sysmetic
09.11.2015 22:49ну так приведите ссылку на какое-нибудь описание того, о чем вы говорите — как сервер Oracle выполняет скажем поиск по таблице, зашифрованной на клиентском ключе, не зная клиентского ключа, — просто мне такого вида шифрования найти не удалось.
dprotopopov
09.11.2015 22:51-1а какую версию вы ПОКУПАЛИ?
dprotopopov
09.11.2015 22:59-1а картинку ключей от квартиры где деньги лежат в своём профиле опубликовать не надо?
dprotopopov
09.11.2015 23:03похвастаться — смотрите какие красыва ключики.
dprotopopov
09.11.2015 23:12-1если сервер НЕ знает клиентского ключа
то и ЛЮБОЙ клиент НЕ знает клиентского ключа
тогда о какой выдаче данных идёт речь? если никто ничего не знает?
Значит кто-то должен знать — и скорее всего вся необходимая информация для полного доступа к «шифрованной» базе данных окажется на том же сервере где размещён apache.
можно постараться заныкать подальше — но при более детальном обыске найдётся всё.dprotopopov
09.11.2015 23:30к тому же в этой статье — сразу в начале нарисован код программы которая формирует вычисляемое поле (расшифрованием данных) — видимо для сортировки или чего-то там для обработки запросом SQL.
дальше можно не читать.dprotopopov
10.11.2015 00:18-1тому же в этой статье — сразу в начале нарисован код программы которая формирует вычисляемое поле (расшифрованием данных)
вы определитесь сразу — вам надо ключ от квартиры где деньги лежат или деньги из квартиры?
Правильно ли Вы выбираете вершки или корешки — как в русской сказке?
Настоящий «хакер» это ведь тот кто ключи подбирает — так ведь в кино толкуют.
lair
Скажите, пожалуйста, чем в вашей статье различаются алгорифм и алгоритм?
dprotopopov
Марков полагал что правильнее писать и называть алгорифм. а не алгоритм ;)
lair
Тогда почему вы не везде пишете «алгорифм»?
dprotopopov
потому что я не Марков ;)
dprotopopov
потому что я не Марков ;)
dprotopopov
потому что я не Марков ;)
Eklykti
потому что он не Марков ;)
dprotopopov
потому что я не Марков ;)