Эта штука позволит отдавать вычисления над секретными данными в "облако", не беспокоясь о возможности взлома самих данных.
И, похоже, эта возможность очень близка.
(моё понимание решения и проблемы)
Мы создаём специальную несимметричную систему шифрования, X=E(x) и x=D(X), при этом за счёт введения случайных чисел E(x)/=E(x) (два шифрования дают одинаковый результат с малой вероятностью). В ней для нескольких интересующих нас функций f, g и h мы создаём функции F, G и H: D(F(X,Y))=f(x,y), то же для H и h, G и g.
Например, если у нас биты, то создав функции для AND и NOT мы получаем возможность выразить сложение, умножение, деление, минимум, максимум и прочее.
Понакодировав данных Xi=E(xi), и задав алгоритм обработки с помощью наших функций, мы отправляем всё на вычисления в "облако", которое потенциально недружественно. Обратно к нам приходит Yj, которое мы раскодируем (на это-то у нас мощностей хватает) и используем в наших целях.
Товарищи из "облака" ни о чём догадаться не могут и даже толком уворовать информацию не в силах.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, thesz, Вы писали:
T>Товарищи из "облака" ни о чём догадаться не могут и даже толком уворовать информацию не в силах.
Как я понял из википедии, единственное, что мы можем делать в облаке, это сложение и умножение. Мы не можем проверять никакие условия, и выполнять действия условно. И вроде бы ничего не мешает злонамеренному облаку выполнить "не те" операции, и вернуть нам ошибочный результат (хотя, конечно, для многих алгоритмов проверка результата может быть сделана гораздо быстрее на стороне клиента).
Здравствуйте, hexamino, Вы писали:
H>Здравствуйте, thesz, Вы писали:
T>>Товарищи из "облака" ни о чём догадаться не могут и даже толком уворовать информацию не в силах.
H>Как я понял из википедии, единственное, что мы можем делать в облаке, это сложение и умножение.
Правда, модуль должен быть чётным.
H>Мы не можем проверять никакие условия, и выполнять действия условно. И вроде бы ничего не мешает злонамеренному облаку выполнить "не те" операции, и вернуть нам ошибочный результат (хотя, конечно, для многих алгоритмов проверка результата может быть сделана гораздо быстрее на стороне клиента).
Мы можем выполнять операции не в одном облаке.
Это проверка сбоя аппаратуры.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, thesz, Вы писали:
T>Это же AND! T>Это же NOT!
Ну хорошо, а можно выполнить какие-нибудь действия по условию? Как организовать цикл или рекурсию? Можно ли написать, например, алгоритм разложения числа на простые сомножители?
T>>Это же AND! T>>Это же NOT!
H>Ну хорошо, а можно выполнить какие-нибудь действия по условию?
Выполняем действие 1, получаем результат Xi
Выполняем действие 2, получаем результат Yi
Выполняем проверку условия, получаем всего один результат C.
Выбираем окончательный результат Ri=NOT(NOT(C&Xi))&(NOT(NOT(C)&Yi))) (Ri=C?Xi:Yi).
H>Как организовать цикл или рекурсию?
Если есть условие, то это можно сделать.
Не Тьбринг-полный вариант, но всё же.
H>Можно ли написать, например, алгоритм разложения числа на простые сомножители?
Надо подумать.
Вообще, разложение на простые множители сводится к SAT проблеме — получить вектор Xi, который удовлетворяет функцию F(xi) в коньюктивно-нормальной форме. То есть, F(Xi)=True.
На первый взгляд, обмен всё равно будет экспоненциально большим.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)