Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
6. Поиграем в «кубики». Протоколы голосованияВ этом разделе мы займемся бессмысленными вещами, а именно, обсудим, как помочь «массе дурачья» избрать «неразумное правительство», т. е. рассмотрим протоколы голосования. У читателя, ознакомившегося с предшествующими разделами, могло сложиться впечатление, что криптографические протоколы — в общем-то не такая уж и сложная вещь. Но дело в том, что до сих пор мы выбирали именно такие протоколы, конструкции которых, на наш взгляд, наиболее просто понять при первом знакомстве с предметом. К тому же изложение велось на полуформальном уровне, чтобы основные идеи не затуманивались обилием технических деталей. Большинство же типов прикладных криптографических протоколов достаточно сложны, и хорошим примером здесь служат протоколы голосования. Как отмечалось во введении, примитивные криптографические протоколы используются как своеобразные «строительные блоки» или «кубики», из которых складывается прикладной протокол. В данном разделе мы рассмотрим не столько конструкцию каждого отдельного «кубика», сколько процесс сборки. Пусть в голосовании участвуют I избирателей 1) голосование должно быть тайным; 2) должна быть обеспечена правильность подсчета голосов. Как уже отмечалось в предыдущем разделе, протоколы голосования можно рассматривать как частный случай протоколов конфиденциального вычисления. В начальный момент у каждого участника Остается второй путь — создание центра подсчета голосов (в дальнейшем для краткости будем называть его просто центр). Сначала предположим, что центр честный и пользуется безусловным доверием всех избирателей. В такой ситуации напрашивается следующее решение. Центр выбирает секретный х и открытый у — ключи некоторой криптосистемы с открытым ключом — и публикует у. Каждый избиратель Уже в этой простой схеме есть «подводный камень». Если каждый избиратель просто шифрует свой бит так называемой семантической стойкостью. Это — своего рода аналог шенноновской абсолютной стойкости, но относительно противника, работающего за полиномиальное время. Мы рассмотрим в качестве примера один из вариантов криптосистемы Эль-Гамаля [20], основанной на задаче дискретного логарифмирования. В обозначениях из раздела 2 пусть
Вернемся к протоколу голосования. Пусть В такой схеме голосование, по существу, не может быть тайным, поскольку центр знает, как голосовал каждый избиратель. Но с правильностью подсчета голосов ситуация иная. Предположим, что для проведения голосования создано табло — хранилище информации, в котором для каждого избирателя выделена отдельная строка. Эта строка содержит, например, полные паспортные данные избирателя, и в эту строку он помещает свой бюллетень. Предполагается, что табло доступно на чтение всем участникам голосования, а также сторонним наблюдателям. По истечении срока подачи голосов табло «закрывается», т. е. фиксируется его состояние. После этого выделяется некоторое время, в течение которого каждый избиратель проверяет содержимое своей строки на табло. Все претензии разбираются, при необходимости вносятся соответствующие изменения и, когда все избиратели удовлетворены, содержимое табло фиксируется окончательно. После этого центр вычисляет
Обозначим знает значение В и не может самостоятельно выяснить, верно ли, что
|
1 |
Оглавление
|