Массово предлагаются услуги для всех желающих по выполнению вычислений на высокопроизводительных компьютерах, реализованных в виде облачных и других систем, от компаний предоставляющих подобные сервисы в публичных сетях.
Однако использование публичных вычислительных сетей несёт для их потребителей риски:
- Утечки приватных данных в процессе их обработки на внешнем устройстве или в процессе передачи данных;
- Возможность наличия искажений в получаемых результатах вычислений на внешнем устройстве или в процессе передачи данных. При этом, даже многократный повтор вычислений с одними и теми же исходными данными не позволит обнаружить наличие этих искажений если они носят системный, а не случайный характер.
Мы не будем рассматривать вопросы утечки приватных данных или искажений в результатах вызванных в процессе передачи данных, оставляя эту тему классической криптографии по обеспечению закрытого канала связи требуемой степени надёжности.
Рассмотрим вопрос, когда сам внешний вычислитель может подвержен компрометации, и на нём самом возможны и анализ приватных данных в процессе обработки, и искажение результатов вычислений, и постараемся решить задачу, которую сформулируем следующим образом:
- Требуется обеспечить механизм обработки приватных данных на внешнем вычислительном устройстве, который, при сохранении возможностей использования типовых алгоритмов, позволил бы сделать невозможным (то есть достаточно сложным) выявление значений приватных данных, а также позволял бы выявлять и исправлять возможные искажения в результатах вычислений, вносимые случайно или системно.
- Поскольку, несомненно, потребуется некоторая дополнительная обработка заданий и результатов, на стороне потребителя, то желательно, чтобы сложность(цена, время) такой обработки была значительно меньше сложности(цены, времени) решения основной задачи – иначе у потребителя нет смысла для проведения вычислений на внешних публичных сетях.
- Также, несомненно, может возрасти общее количество вычислений, отдаваемых на внешний вычислитель, поскольку любое внесение избыточности в исходные данные, либо с целью исключения их однозначного определения, либо с целью контроля за их достоверностью, несомненно потребует обработки большего количества информации. Однако, поскольку внешние вычислительные мощности могут быть увеличены только за счёт большей оплаты со стороны потребителя, то разумное увеличение стоимости не должно являться решающим фактором при выборе алгоритма механизма защиты данных.
Термины и обозначения
Обозначим формулой 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
Задача линейного программирования
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.
Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.
Рассмотрим задачу линейного программирования ax<=b && cx->max, где
- a и b — исходные данные — матрица и вектор с элементами из поля R
- c — исходные данные — вектор с элементами из поля R
- x – искомые данные – вектор с элементами из поля R
Алгоритм защиты вычислений решения задачи линейного программирования
- Сформируем обратимую матрицу V и вектор z из случайных величин
- Вычисляем на локальном вычислителе a'=aV, c'=cV, b'=b-az
- Передаём на внешний вычислитель задачу решения уравнения a'x'<=b' && c'x'->max
- Используя полученное решение задачи линейного программирования a'x'<=b' && c'x'->max, вычисляем на локальном вычислителе x=Vx'+z
Замечания:
- Справедливы формулы 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