4 Устойчивые и проверяемые микс-конструкции

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

Большинство предложенных схем используют микс-каскады. По этой причине нет никаких предуведомлений информации между отправителем сообщения и промежуточными миксами в каскаде. Подразумевается, что информация о маршрутизации не является необходимой, поскольку миксы обрабатывают информацию в фиксированном порядке. Первая схема, которая использовала эти преимущества была схема эффективного канала и голосования "всё-или-ничего", предложенная Парком, Айтохом и Куросавой в [156]. В этой системе сообщение является шифртекстом Эль-Гамаля фиксированной длины (длина не зависит от числа миксов, через которые оно должно пройти). Кроме этого, эта схема использует стратегию "вырезать и выбрать", что делает его "всем-или-ничем", означающим, что если любой шифртекст будет удалён из микс-пакета, то никакого результата на его выходе получено не будет. Это свойство гарантирует, что частичные результаты не повлияют на перевыборы.

У Чаума был оригинальный дизайн для расшифровывающих миксов, в которых шифрование каждого микса в маршруте было послойным на сообщении отправителя и слои отделялись соответствующим миксом по мере обработки этого собщения. Помимо предположения о каскадной топологии множество разработчиков стойких и проверяемых микс-систем следовали Парку и др. вместо следования принципу перешифрования. Согласно этому подходу сообщение обычно было зашифровано с использованием шифрования с открытым ключом только раз, используя гомоморфное шифрование, такое как метод Эль-Гамаля. Каждый микс перешифровывал сообщение вместе с новым рэндомизирующим значением так, что это изменяло его внешнее представление, за счёт чего сообщения могли быть фиксированной длины, независимо от длины пути. Все сообщения, посылаемые в каскад, были зашифрованы одним и тем же открытым ключом. Для приложений, таких как отправка анонимной почты произвольным получателям в различных местоположениях это будет не очень применимо. Для приложений, таких как муниципальные выборы, это тем не менее оказывается естественным образом пригодным.

Бёрджит Пфитцман нашёл две атаки против предложения Парка, Айтоха и Куросавы [160]. Первая атака очень близка к ранее обсуждавшейся нами выше из работы [161] против различных микс-дизайнов и заставляет использовать характеристики, инвариантные от различных состояний смешивания вследствии криптосистемы Эль-Гамаля. Он также обнаружил активную атаку, в которой вход шифртекста Эль-Гамаля делается "слепым" за счёт возведения в степень, результат которого на конечном выходе также возводится в эту степень. Это атака с подобранным шифртекстом, против которой борются множество систем и в конечном счёте проигрывают. Пфитцман также отмечает, что подразумеваемая модель угрозы слабее предложенной Чаумом. Нечестный отправитель способен нарушить функционирование всей сети, что даже хуже, чем для отдельного микса, как в случае из работы Чаума. Он не предложил никаких практических мер противодействия этим атакам: любая честная попытка исправления скомпрометировала бы какое-либо из интересных свойств системы.

Параллельно с работой Бёрджета Пфитцмана, Кайлиан и Сэко предложили микс-систему голосования, свободную от квитанций [122]. Они попытались добавить универсальную проверяемость в [156], что означает, что все отправители способны проверить, что все голоса были приняты к учёту, а не просто их личный голос. Они также выяснили, что множество предложенных проверяемых микс-схем предоставляют в конце смешивания квитанцию, которая может быть использована для принуждения к продаже голосов. Тогда они попытались сделать свою систему свободной от квитанций. Они сделали это, заставляя каждый микс учитывать свой вход и выход и предоставлять доказательство знания с нулевым разглашением, что он выполнял расшифрование и перемешивание корректным образом. К сожалению, Мичелс и Хорстер показали в [138], что такая схема не является свободной от квитанций если отправитель сотрудничает в сговоре с миксом и активные атаки, основанные на ослеплении, предложенные Бёрджитом Пфитцманом могут быть использованы для связи входов и выходов.

Для того, чтобы избежать крах системы если подмножество миксов оказывается злонамеренным, Огата и др. предложили устойчивый к сбоям анонимный канал [149]. Он ипользует пороговую криптосистему для уверенности в том, что большинство миксов могут декодировать сообщения, даже если некоторое меньшинство миксов не участвует. Было предложено две системы, одна основана на Эль-Гамале и другая, основана на проблеме r-ого остатка. Доказательство с нулевым знанием корректного перемешивания также предложено для проблемы r-остатка.

В 1998 году Эйб представил микс-систему, которая обеспечивает универсальную проверяемость и была эффективной в смысле того, что работа по проверке была независима от числа микс-серверов [1]. Эйб также показал атаки на [122], которые используют информацию для проверки со стороны выхода для того чтобы разрушить приватность системы. Затем он представил микс-систему, которая работает в две фазы: перешифрование Эль-Гамаля и пороговое расшифрование. Корректность первой фазы доказывается до начала второй фазы, а затем производится доказательство корректности расшифрования на выходе в конце второй фазы.

Системы, которые обеспечивают универсальную проверямость, основанную на доказательствах перестановок и доказательствах знания с нулевым разглашением очень вычислительно затратны. В [110] Якобсон сконструировал практический микс для уменьшения числа затратных операций. В порядке доказательства корректности перемешивания, новые техники были названы и представлены как устойчивость к повторениям и слепая деструктивная устойчивость. Сеть работает в две фазы: сначала шифртексты делаются слепыми по Эль-Гамалю, затем список входов повторяется. Каждый повторенный вход декодируется всеми миксами, которые выдают в результате список слепых открытых текстов. Полученные списки сортируются и сравниваются. Если все элементы представлены во всех списках, то это значит, что никакой из миксов в системе не был подвергнут повреждающему влиянию и затем можно провести снятие ослепляющих параметров и осуществлять дальнейший миксинг. В противоположном случае запускается протокол нахождения обманщика (читера). Будучи высокоэффективным, практический микс не был в достаточной степени доказано безопасным, что было представлено Десмедтом и Куросавой [51]. Они показали, что злонамеренный микс в системе практических миксов может изменить шифртекст и всё равно остаться необнаруженным. Они представили новый микс-дизайн, в котором проверка осуществляется на подмножестве миксов. Подмножества генерируются таким способом, что по крайней мере один гарантированно не содержит никакого злонамеренного микса.

В попытке дальнейшего снижения стоимости смешивания Якобсон представил флэш-микс, который использует перешифрование вместо ослепления для того, чтобы снизить количество возведений в степень [111]. Как и в практическом миксе, смешивание производится в несколько фаз и использует стойкость к повторениям для обнаружения изменений. Кроме того, на вход поступают два пустых собщения. Они деанонимизируются, после того как все миксы учитывают свои выходы для того, чтобы быть уверенными в том, что атаки, такие как [51] не работают. Митомо и Куросава тем не менее нашли атаку против оригинального флэш-микса, которую исправили путём внесения изменений в протокол снятия ослепляющих параметров [139].

Прорыв произошёл тогда, когда Фурукава и Сэко [83] и Нефф [146] предложили эффективные техники для универсальной проверямости корректности перемешивания шифртекстов Эль-Гамаля. Первые предложили доказательство того, что использованная матрица была матрицей перестановок, а второй использовал проверяемое секретное умножение экспоненты для улучшения эффективности этого.

Назад | Оглавление | Дальше