10 декабря 2012 в 12:12

Алгоритм анонимной коллективной подписи

Одним из способов протеста является подача и коллективное подписание разного рода петиций. Но поскольку список подписавших петицию открыт, нередко возникают ситуации, когда несогласные с «курсом партии» подвергаются угрозам и репрессиям со стороны администрации.

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

Постановка задачи

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

1. Есть возможность удостовериться, что каждый подписант принадлежит к указанному кругу лиц.
2. Есть возможность проверить, что большинство подписей принадлежат разным лицам.
3. Нет возможности определить, кому именно принадлежит та или иная подпись.
4. Нет возможности определить, оставляло ли данное конкретное лицо свою подпись или нет.
5. Любой подписант может по своему желанию поставить вместо анонимной подписи персонализованную.
6. Любой анонимный подписант может впоследствии по своему желанию предоставить доказательства того, что именно он поставил подпись.

Система основана на асимметричной криптографии, алгоритмах цифровой подписи и сертификации ключей.
алгоритмов разделения секрета.

Каждый из членов группы (включая самого А) подписывает свой фрагмент своим персонализованным закрытым ключом и затем публикует.


Рис. 4. Схема верификации подписанта

Таким образом, наблюдатель получает доказательство того, что голос сформировал кто-то из группы {A,B,C}, но кто именно — сказать нельзя. Это сильно затрудняет применение репрессий к подписантам со стороны администрации. Размер группы можно выбирать произвольно, чем он выше, тем выше надежность, но тем сложнее (технически) организовать распределение фрагментов. Необходимо запретить повторную верификацию голоса, иначе появляется возможность вычислить подписанта, ища пересечения групп, участвовавших в каждой верификации. Либо требовать, чтобы при повторной верификации состав группы не менялся.

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

Остановимся подробнее на алгоритме распределения фрагментов. К нему предъявляются следующие требования:

1. Никто из членов группы и сторонних наблюдателей не должен иметь возможности узнать, кто инициировал процедуру.
2. Даже если все члены группы, кроме А, в сговоре, у них не должно быть возможности доказать, что именно А — инициатор.
3. У лица, не входящего в группу, не должно быть возможности инициировать процедуру.

Последнее требование делает непригодной простую анонимную рассылку фрагментов. Ведь тогда появляется возможность лицу «со стороны» сгенерировать голос и пройти верификацию, разослав фрагменты остальным и не подписываясь своим персонализованным ключом.

Схема распределения фрагментов показана на рис.6. Допустим, А — инициатор. Он подписывает своим закрытым персонализованным ключом случайный фрагмент, а затем пересылает все фрагменты B. Первым делом B проверяет подпись А по сертифицированному открытому ключу, и, удостоверившись, что А — тот, за кого себя выдает, публикует подписанный фрагмент.

Затем B удаляет из сообщения подпись А, подписывает своим закрытым персонализованным ключом следующий фрагмент и посылает все фрагменты С. Аналогично, С проверяет подпись B, публикует этот фрагмент и подписывает следующий.

В конце цепочки сообщение опять пересылается А, который проверяет подпись последнего участника (C) и публикует последний фрагмент.


Рис. 5. Схема распределения и подписания фрагментов

Для каждого участника, кроме инициатора, процедура выглядит совершенно одинаково и нет возможности определить, где начало цепочки и где ее конец. Даже если B и C сговорятся и определят последовательность пересылок, А сможет утверждать, что он находится в цепочке после C (соответственно, B — инициатор), и у B с C не будет способа доказать обратное.

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

Завершение верификации

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


Рис. 6. Схема завершающего этапа верификации

Все операции, выполненные наблюдателем, может повторить любая другая сторона, так как исходные данные (голос, контрольное сообщение и подписанные фрагменты) публикуются в открытом доступе.

Заключение

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

Благодарю за внимание!

UPD.

Я действительно изобрел велосипед. Для решения данной задачи предназначен класс алгоритмов Group / Ring signatures. Спасибо grich за наводку!

Если ключи публикуются анонимно, как гарантировать, что одному человеку принадлежит один анонимный ключ?
Кажется по времени публикации можно точно определить второго в цепочке. или под публикацией имелось в виду что-то еще?

1. Это можно выяснить во время верификации. Если несколько анонимных ключей будут принадлежать одному человеку, то этот человек неминуемо будет присутствовать в каждой группе, что сразу выдает многостаночника. Конечно, один человек может попасть в несколько групп и случайно, но вероятность этого легко подсчитать (при истинно случайном выборе групп). Все, что сильно выходит за рамки теоретической вероятности — скорее всего, вброс голосов.

2. Порядок следования людей в цепочке не представляет секрета (его знают все участники группы). Но цепочка закольцована, и никто, кроме инициатора, не знает, где у нее начало. Если можно установить, кто второй, то будет ясно, и кто первый, и кто десятый. Чтобы это нельзя было установить, и вводится случайная задержка перед публикацией. Например, в 12:00 стартует процедура обмена фрагментами, в 13:00 она заканчивается, с 13:00 до 15:00 участники публикуют подписанные фрагменты, кто когда хочет.

Не должно быть отдельного ПО, обеспечивающего эту систему. То есть все операции должны быть осуществимы при помощи стандартных уже имеющихся средств. после того как А выберет группу соучастников, как он оповестит их о составе группы и последовательности обработки, не раскрыв информацию о себе?

Алгоритм действий членов группы при проверке достаточно сложен. Нужно подпись чужую удалить, другому переслать, подождать и опубликовать. Для большой группы людей такой процесс сложно контроллировать. Кстати, как определить какой фрагмент кому подписывать? Вдруг третий подпишет тот же фрагмент, что и первый.

Да, согласен, система довольно сложная получилась. Если кто сможет придумать проще, будет отлично.

> как он оповестит их о составе группы и последовательности обработки, не раскрыв информацию о себе?
Например, он публикует анонимное широковещательное сообщение: «Сегодня, в 12:00 GMT стартует обмен фрагментами. Участники: A, B, C». Затем все участники (включая самого A) публикуют подтверждение. В указанное время они ждут пересылок.

> как определить какой фрагмент кому подписывать?
Следующий за уже подписанным. Допустим, очередной участник получил 10 фрагментов, из которых подписан пятый. Он проверяет и откусывает эту подпись, затем подписывает шестой фрагмент. Тот, кто получил подписанный 10-й, подписывает первый фрагмент.

Не совсем понятно на счет группы.

Те, кто подписывает часть секрета своей персональной подписью, должны знать что A является источником этого секрета? Если нет, то вся эта процедура бессмысленна.

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

2.2.8. Электронно-цифровая подпись - Научная библиотека

На втором этапе, собственно, реализуется шифрование сообщений, при котором ... Реализация схемы ЭЦП связана с вычислением хэш-функции ( дайджеста) ... Регистрация каждой ЭЦП осуществляется на основе заявления, ... http://sernam.ru/ss_228.php

Никто в группе не знает, кто источник подтверждаемого секрета. Группа подтверждает, что кто-то из них знает анонимный закрытый ключ (им подписано контрольное сообщение).

Тот, кто не состоит в группе, не может запистить цепочку подписания фрагментов, т.к. второй проверяет подпись первого, третий — второго и.т.д. Таким образом, если кто-то захочет подтвердить сразу два анонимных ключа, он должен состоять в обоих группах. А если таких ключей не 2, а скажем 1000 (число, сравнимое с количеством голосов в целом), то такого человека сразу видно, т.к. он будет состоять сразу в 1000 группах и это нельзя будет объяснить случайностью.

Стоп! Не понял. Что значит «знает анонимный закрытый ключ»? Знает кому принадлежит данный анонимный закрытый ключ? Тогда он будет знать и источник секрета. Если эта фраза означает не это, тогда что?

По порядку. A подал голос, у него есть соотв. закрытый анонимный ключ. Но этот факт никому, кроме A неизвестен. Наступает время верификации. A подписывает контрольное сообщение этим же закрытым ключом. Теперь любой, кто увидит эту ЭЦП, может сказать: «Да, её создал тот же человек, кто и поставил голос.» Но что этот человек — A, никто по-прежнему не знает.

Теперь собралась группа {A, B, C}, они распределили между собой фрагменты ЭЦП и подписали своими персонализованными ключами. Тем самым подтверждая, что один из них — тот, кто эту ЭЦП создал, а значит, и тот, чей голос.

Программирование алгоритма цифровой подписи ГОСТ Р 34.10 ...

Основные алгоритмы реализации электронной цифровой подписи. ... Особенности криптографической системы с открытым ключом, этапы шифровки. http://allbest.ru/k-2c0b65625b3ad68b5d43b89421216d37.html

Т.к. проверки будут выборочными, а не глобальными, при второй проверке ничто не помешает А выбрать группа A, D, C для проверки второго анонимного ключа. И так до бесконечности. Т.е. принцип «один человек» — «один анонимный ключ» не соблюдается.

Кстати, в таком случае вообще непонятно зачем нужна группа. Проверющий просто получает от А весь секрет подписанный его анонимным ключем. Это так-же будет означать что «это сообщение отправил тот-же человек, который оставил свой голос». Но что это докажет? По моему, ничего.

Ваш вариант с группами имеет смысл только в двух случаях:
1. Когда разбивка на группы фиксирована.
2. Когда проверка производиться в глобальном масштабе — т.е. процедура проверки обязательна для всех голосов.

Может, проще разбивать не сообщение с верификацией, а непосредственно сообщение с «голосом» и выстраивать цепочку для него?

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