Области применения гомоморфного шифрования

[Shark]

Электронный подсчет голосов уже и сейчас можно применять, там даже не нужна полная гомоморфность. И даже есть схемы для проверки целостности бюллетеней (например, www.youtube.com/watch?v=izddjAp_N4I). Но на деле эти схемы, почему-то, не применяются.

[starius]

Спасибо, интересная статья.

Возникло несколько вопросов.

1. Однозначно ли соответствует шифротекст открытому тексту в гомоморфном шифровании?

Пользователь отсылает серверу зашифрованный бинарный вектор, каждый бит которого — зашифрованный нуль (естественно, с помощью гомоморфного алгоритма), кроме i-го бита.

Если шифротекст однозначно соответствует открытому тексту, то сервер увидит n-1 одинаковых шифратов на входе и поймёт, что они соответствуют 0, а оставшийся соответствует 1.

2.

Тогда каждый из избирателей составляет вектор предпочтения — (П1, П2, ..., Пn), где каждое Пi ∈ {0, 1}, после чего шифрует каждый элемент из него и отправляет список зашифрованных нулей и единиц инициатору голосования.

Что мешает инициатору расшифровать данные от каждого участника в отдельности и узнать, кто как проголосовал?

3.

На сервере тогда выполняется скалярное умножение полученного вектора на x.

Получается, для обработки одного поискового запроса серверу придётся пройтись по всей базе данных?

[clex]

1. Нет, не однозначно. В таких системах часто добавляется случайный шум для того, чтоб невозможно было установить соответствия между ОТ и ШТ.

2. Ничего не мешает. Тут, думаю, нужно было сделать акцент на удобство. Т.е. в итоге нам надо произвести n расшифровок, а не m, где m — число избирателей

3. Да, получается так.

[starius]

2. Получается, координатор знает, кто как проголосовал. Кроме того, любой из участников может испортить голосование, если пришлёт случайные числа вместо своих результатов. Чтобы вычислить вредителя, придётся расшифровывать все данные. Мне казалось, существуют системы голосования, лишённые обоих этих недостатков.

[clex]

Для того, чтоб координатор не узнал ничего о голосах отдельных пользователей, можно производить сложение бюллетеней до момента отправки. Или, как вариант, ввести третью сторону, не владеющую секретным ключом, которая будет складывать бюллетени перед отправкой их координатору.

Насчет второго ничего сказать не могу, но, думаю, этого можно избежать, усложнив немного схему.

[Shark]

Можно обойтись и без третьей стороны. Заинтересованные лица генерируют ключи и отдают публичные, с помощью которых мы зашифровываем. После обработки стороны приходят к соглашению, что подсчет проведен верно, фальсификации в пределах допустимого и только тогда отдают свои частные ключи для расшифровки. Ни одна заинтересованная сторона не сможет узнать результаты без согласия других.