Обработка приватных данных на публичных вычислительных сетях

    Вычислительные системы прошли путь от мэйнфрэймов к персональным компьютерам, и теперь совершают обратный путь — от персональных компьютеров к мэйнфрэймам.
    Массово предлагаются услуги для всех желающих по выполнению вычислений на высокопроизводительных компьютерах, реализованных в виде облачных и других систем, от компаний предоставляющих подобные сервисы в публичных сетях.
    Однако использование публичных вычислительных сетей несёт для их потребителей риски:
    • Утечки приватных данных в процессе их обработки на внешнем устройстве или в процессе передачи данных;
    • Возможность наличия искажений в получаемых результатах вычислений на внешнем устройстве или в процессе передачи данных. При этом, даже многократный повтор вычислений с одними и теми же исходными данными не позволит обнаружить наличие этих искажений если они носят системный, а не случайный характер.

    Мы не будем рассматривать вопросы утечки приватных данных или искажений в результатах вызванных в процессе передачи данных, оставляя эту тему классической криптографии по обеспечению закрытого канала связи требуемой степени надёжности.
    Рассмотрим вопрос, когда сам внешний вычислитель может подвержен компрометации, и на нём самом возможны и анализ приватных данных в процессе обработки, и искажение результатов вычислений, и постараемся решить задачу, которую сформулируем следующим образом:
    • Требуется обеспечить механизм обработки приватных данных на внешнем вычислительном устройстве, который, при сохранении возможностей использования типовых алгоритмов, позволил бы сделать невозможным (то есть достаточно сложным) выявление значений приватных данных, а также позволял бы выявлять и исправлять возможные искажения в результатах вычислений, вносимые случайно или системно.
    • Поскольку, несомненно, потребуется некоторая дополнительная обработка заданий и результатов, на стороне потребителя, то желательно, чтобы сложность(цена, время) такой обработки была значительно меньше сложности(цены, времени) решения основной задачи – иначе у потребителя нет смысла для проведения вычислений на внешних публичных сетях.
    • Также, несомненно, может возрасти общее количество вычислений, отдаваемых на внешний вычислитель, поскольку любое внесение избыточности в исходные данные, либо с целью исключения их однозначного определения, либо с целью контроля за их достоверностью, несомненно потребует обработки большего количества информации. Однако, поскольку внешние вычислительные мощности могут быть увеличены только за счёт большей оплаты со стороны потребителя, то разумное увеличение стоимости не должно являться решающим фактором при выборе алгоритма механизма защиты данных.


    Термины и обозначения


    Обозначим формулой 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

    Алгоритм защиты вычислений задачи решения системы линейных уравнений


    1. Сформируем обратимые матрицы U и V и вектор z из случайных величин
    2. Вычисляем на локальном вычислителе a'=UaV, b'=U(b-az)
    3. Передаём на внешний вычислитель задачу решения уравнения a'x'=b'
    4. Используя полученное решение уравнения a'x'=b', вычисляем на локальном вычислителе x=Vx'+z
    5. Проверка истинности найденного решения может быть выполнена явной подстановкой найденного решения в формулу системы линейных уравнений ax=b


    Задача линейного программирования


    Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
    Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.
    Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.

    Рассмотрим задачу линейного программирования ax<=b && cx->max, где
    • a и b — исходные данные — матрица и вектор с элементами из поля R
    • c — исходные данные — вектор с элементами из поля R
    • x – искомые данные – вектор с элементами из поля R


    Алгоритм защиты вычислений решения задачи линейного программирования


    1. Сформируем обратимую матрицу V и вектор z из случайных величин
    2. Вычисляем на локальном вычислителе a'=aV, c'=cV, b'=b-az
    3. Передаём на внешний вычислитель задачу решения уравнения a'x'<=b' && c'x'->max
    4. Используя полученное решение задачи линейного программирования 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


    Алгоритм защиты вычислений на публичном вычислителе


    1. Возьмём произвольные алгорифмы, обладающие свойствами x = x*E*U и y = y*V*D для любых допустимых x и y, и такие, что алгорифмы E и D не являются слишком затратными для вычисления на локальном вычислителе.
    2. Составим алгорифм G=U*F*V и используя алгорифм “уменьшения” количества вычислений или алгоритм “обфукации” преобразуем его к программе G’ используя локальный вычислитель.
    3. Вычислим на локальном вычислителе x’=x*E
    4. Выполним на внешнем вычислителе задачу y’=x’*G’, сообщив на внешний вычислитель x’ в качестве исходных данных, программу G’ и получив в ответ значение y’.
    5. Вычислим на локальном вычислителе y=y’*D

    Замечания:


    • Использование алгорифмов Е и D, полученных из теорий криптографии и восстановления искажённых данных позволит обеспечить защиту приватных данных переданных на внешний вычислитель или полученных от внешнего вычислителя, а также детектировать факты искажения результатов обработки данных на внешнем вычислителе.


    Литература


    • Кудрявцев В.В, Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985.
    • Мальцев А. И. Алгоритмы и вычислимые функции. М.: Наука, 1986.
    • МакВильмс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979
    • Марков А. А. Введение в теорию кодирования. М.: Наука, 1982
    • Карманов В.Г. Математическое программирование. М.: Наука, 2000.
    • Турчин В.Ф. Язык программирования РЕФАЛ. Интернет-проект www.refal.net
    • Иван Кочуркин @KvanTTT Математические выражения в .NET (разбор, дифференцирование, упрощение, дроби, компиляция). Интернет-публикация habrahabr.ru/post/150043
    • @JediPhilosopher Как компьютер сам свой код улучшал, или программируем процесс программирования. Интернет-публикация habrahabr.ru/post/265195


    Контакты


    Share post

    Similar posts

    Comments 29

      0
      Скажите, пожалуйста, чем в вашей статье различаются алгорифм и алгоритм?
        0
        Марков полагал что правильнее писать и называть алгорифм. а не алгоритм ;)
          0
          Тогда почему вы не везде пишете «алгорифм»?
            0
            потому что я не Марков ;)
              0
              потому что я не Марков ;)
                0
                потому что я не Марков ;)
                  +9
                  потому что он не Марков ;)
                    0
                    потому что я не Марков ;)
              +1
              Проблемы с линейной алгеброй начинаются, когда нужно построить обратимые матрицы с нужными свойствами —
              1. Легко вычислимые. (ибо должно быть сильно дешевле построить шифрующие матрицы, чем решить систему локально)
              2. Сложно угадываемые (ибо криптграфия, все дела)
              3. Хорошо обусловленные (если вы переводами туда-сюда увеличиваете ошибку хотя бы в 100 раз, вся эта кухня на реально нужных задачах оказывается, опять же, уже не нужна). Или надо говорить о публичном нахождении хорошего приближения с дальнейшей локальной доводкой до нужной точности каким-нибудь итерационным методом.
                0
                да.
                Рассматривайте этот текст просто как рассуждения на тему.
                В тексте же нет программных кодов, а про матрицы я тоже упоминаю что это не более чем кольцо с делителями нуля.
                  0
                  да.
                  Рассматривайте этот текст просто как рассуждения на тему.
                  В тексте же нет программных кодов, а про матрицы я тоже упоминаю что это не более чем кольцо с делителями нуля.
                    0
                    не нужно вам всё кольцо, возьмите только мультипликативную группу.
                    проблема, как написали выше, в построении обратимых матриц. надо переложить эту задачу на внешний вычислитель.
                    предложение: построить в облаке 2n матриц и обратных к ним и взять произведение n из них.
                      0
                      надо переложить эту задачу на внешний вычислитель.

                      да
                        0
                        построить в облаке 2n матриц и обратных

                        только надо явно указывать свойства каждой — а то напихают всё из одного класса.
                        как в ресторане — если закажешь просто пожрать — принесут суп из картошки, рагу из картошки, компот из картошки и десерт из картошки.
                          0
                          суп из картошки, рагу из картошки, компот из картошки и десерт из картошки — как не комбинируй — одно — выпарил влагу — и хрусти картофельными чипсами.
                    0
                    А вы знакомы с работой "CryptDB: Protecting Confidentiality with Encrypted Query Processing"? Там предложен несколько другой подход, решающий ту же проблему, и мне он представляется весьма перспективным, потому что не ведет к увеличению требуемой вычислительной мощности (но возможно с некоторым снижением криптостойкости, что пока еще не проанализировано экспертами в области криптоанализа).
                      0
                      глянул. что увидел за 5 минут — очередной велосипед по превращению реляционной базы в шифрованную реляционную базу путём добавления ещё одного программного слоя.
                      у oracle с давних времён шифрование строк таблиц встроено в систему управления базы, но большинство программистов или не знают об этих фичах, а если знают то намеренно не пользуются поскольку стоимость разработки ПО возрастает на порядки.
                      ведь кроме задачи хранения более важной является система распределения прав.
                      если несмотря на шифрование данных в таблицах все пользователи продолжают иметь равные права по доступу к данным то проще поместить базу в защищённый периметр — на шифруемый диск в серверной с ограниченным доступом и убедится что из вне общение с устройством возможно только по чётко описанным протоколам и никак иначе.
                      если имеется ввиду размещение базы в публичном датацентре — для ЛЮБЫХ поситетелей веб-сайтов…
                      в общем как обычно вся необходимая информация для полного доступа к «шифрованной» базе данных окажется на том же сервере где размещён apache.
                      да и вопрос хранения данных+их связей — не тема моей публикации.
                        0
                        В статье предлагается шифрование на клиентском ключе при охранении возможности исполнять запросы на сервере, при условии, что сервер НЕ знает клиентского ключа (эта проблема актуальна для публичных облаков, когда клиент не доверяет провайдеру), то есть решается задача, обозначенная в теме Вашего поста.

                        Что же касается Oracle — то там речь идет о шифровании на ключе, известным серверу, что НЕ решает проблему недоверия к провайдеру.
                          0
                          Что же касается Oracle — то там есть всё.
                          если вам знакома только иерархическая модель разделения прав — то все вопросы к царю.
                            0
                            что известно двоим — известно свинье (с) Миллер
                              0
                              ну так приведите ссылку на какое-нибудь описание того, о чем вы говорите — как сервер Oracle выполняет скажем поиск по таблице, зашифрованной на клиентском ключе, не зная клиентского ключа, — просто мне такого вида шифрования найти не удалось.
                                –1
                                а какую версию вы ПОКУПАЛИ?
                                  –1
                                  а картинку ключей от квартиры где деньги лежат в своём профиле опубликовать не надо?
                                    0
                                    похвастаться — смотрите какие красыва ключики.
                                      –1
                                      если сервер НЕ знает клиентского ключа
                                      то и ЛЮБОЙ клиент НЕ знает клиентского ключа
                                      тогда о какой выдаче данных идёт речь? если никто ничего не знает?
                                      Значит кто-то должен знать — и скорее всего вся необходимая информация для полного доступа к «шифрованной» базе данных окажется на том же сервере где размещён apache.
                                      можно постараться заныкать подальше — но при более детальном обыске найдётся всё.
                                        0
                                        к тому же в этой статье — сразу в начале нарисован код программы которая формирует вычисляемое поле (расшифрованием данных) — видимо для сортировки или чего-то там для обработки запросом SQL.
                                        дальше можно не читать.
                                          –1
                                          тому же в этой статье — сразу в начале нарисован код программы которая формирует вычисляемое поле (расшифрованием данных)

                                          вы определитесь сразу — вам надо ключ от квартиры где деньги лежат или деньги из квартиры?
                                          Правильно ли Вы выбираете вершки или корешки — как в русской сказке?
                                          Настоящий «хакер» это ведь тот кто ключи подбирает — так ведь в кино толкуют.
                        +1
                        Странно, что ни разу в статье не упомянуто гомоморфное шифрование
                          0
                          вот и упомянули

                        Only users with full accounts can post comments. Log in, please.