id: Гость   вход   регистрация
текущее время 09:14 19/03/2024
Владелец: unknown (создано 01/06/2010 14:42), редакция от 10/06/2010 12:49 (автор: unknown) Печать
Категории: анонимность
http://www.pgpru.com/Библиотека/Статьи/SAC/4Устойчивыеипроверяемыемикс-конструкции
создать
просмотр
редакции
ссылки

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


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


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


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


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


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


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


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


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


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


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


Даже если предложенные выше техники более эффективны, чем все ранее известные, они всё ещё неэффективны для того, чтобы масштабировать выборы на миллионы участников. По этой причины Голль и др. [95] предложили оптимистическое смешивание, которое работает быстро, если не обнаруживается никакой атаки, но не даёт никаких результатов если возникают ошибки. В случае ошибок оно обеспечивает механизм аварийного переключения на использование более стойких техник (таких как в [146]). Каждый микс в цепочке даёт на выходе "доказательство" перемешивания, которое может быть сфальсифицировано или подвергнуто намеренному изменению с шифртекстом. Но это определяется за счёт использования шифрования с известным открытым текстом. Второе расшифрование, показывающее голоса, выполняется только если все выходы получены от смешивания проведённого должным образом. Дуглас Викстрём нашёл серию атак против этой схемы [195, 197]. Первые две атаки близко связаны с атаками в [160], упомянутыми выше и могут разрушать анонимность любого пользователя. Другая атака, имеет отношение к [51] и может разрушить анонимность всех пользователей и компрометировать устойчивость. Наконец, также применимы атаки, основанные на неправильно проверяемых элементах Эль-Гамаля и впоследствии исследованые в [196].


Серьёзным недостатком традиционного устойчивого микс-каскада является то, что в каждом миксе требуется ожидание выхода предыдущего микса перед обработкой сообщений. Это означает, что задержки увеличиваются в зависимости от числа миксов и большую часть времени миксы не проводят никаких вычислений. В [93] Голль и Жуль представили технику, которая позволяет осуществить универсальное параллельное смешивание за четыре шага коммуникации и эквивалентно двум шагам смешивания. Эта техника резко снижает задержки при смешивании, но как показал Борисов, когда противнику известно много входящих сообщений, анонимность, предоставляемая этой техникой далека от оптимальной [21].


Фундаментально новый способ рассмотрения стойких микс-протоколов представлен в [3]: смешивание рассматривается как вычисление, предоставленное третьей стороне (аутсорсинг). Разумеется, эта треться сторона не должна получить никакой информации об актуальном смешивании. Было предложено два протокола, которые могут выполнить этот алгоритм, основанные на Пэйлье и BGN гомоморфном шифровании. Третья сторона принимает серию шифртекстов и разделяет в обфусцированном алгоритме смешения для получения перешифрованного и перемешанного множества выходов. Поскольку используется только открытый ключ, никто — ни третья сторона, ни наблюдатель, не смогут связать входы и выходы.


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


 
Комментариев нет [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3