как работать с секретными данными

[juan_gandhi]

Алисе нужно посчитать ковариационную матрицу, но у неё не хватает вычислительных мощностей. Мошности есть у Боба, но Алиса не доверяет Бобу свои данные. Как быть?!

Вот решение, которое я вчера в машине вычитал в CACM, который мне присылают в попытках уговорить меня заплатить им 400 баксов за членство и библиотеку, и поддержать их рэкет и ксенофобию (чуть не в каждом номере читаешь о вреде иммигрантов).

Прежде всего, всякую операцию над числами да и вообще можно представить в виде операций над битами; а операций над битами не так много; и если биты представить в виде чисел по модулю 2, то XOR есть сложение, а конъюнкция есть умножение. Остальное выводится.

Теперь нам надо биты зашифровать и передать Бобу, вместе с программой.

Для шифрования используем одно секретное число p > 2. Бит шифруем так:
f(b) = (r1 * 2) + r2 * p + b,

где r1 и r2 - случайные положительные целые числа, причём r1 < p/2.

Восстановить b просто: b = (f(b) % p) % 2.

Понятное дело, что сложение и умножение при таких операциях сохраняется, так что

f-1(f(a) * f(b)) = a * b
f-1(f(a) + f(b)) = a + b


Убиваем двух зайцев - и данные не раскрыты, и Бобу сервер загрузим по самое немогу.

Ну самом деле, конечно, вместо 2 везде можно подставить 256, и выйдет то же самое.

Всё просто, правда? В CACM это описание занимает страниц шесть, с хитрыми формулами и примерами из ювелирной промышленности.