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

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

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

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

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


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


    Подготовительный этап

    Каждый участник (на рис.1 — А, B,...Z) генерирует пару ключей, открытый и закрытый. Назовем эти ключи персонализованными. Открытый ключ публикуется и подтверждается центром сертификации, в роли которого может выступать деканат института, отдел кадров предприятия или административный аппарат государства. Задача сертификата — подтвердить, что данный ключ действительно принадлежит указанному лицу, и что это лицо имеет право участвовать в коллективном подписании.


    Рис. 1. Схема сертификации открытых ключей

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

    Формирование голосов

    Каждый подписант генерирует еще одну пару ключей — т.н. анонимные ключи. При помощи закрытого ключа он подписывает сообщение, а открытый публикует анонимно. Электронная подпись (ЭЦП) и соответствующий открытый ключ составляют один голос.


    Рис. 2. Схема формирования голосов

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

    Проверка голоса

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


    Рис. 3. Схема первичной проверки голоса

    Верификация подписанта

    В дальнейшем производится проверка подписантов. Эта проверка может быть как выборочной, так и полной, в зависимости от числа подписантов и технических возможностей.

    Наблюдатель публикует запрос на проверку какого-либо конкретного голоса, используя в качестве идентификатора анонимный открытый ключ. Подписант, ключ которого опубликован в запросе (на рис.4 — А), генерирует случайное контрольное сообщение и публикует его анонимно. В принципе, это сообщение может сгенерировать и наблюдатель, присоединив его к запросу.

    Затем А подписывает контрольное сообщение своим анонимным закрытым ключом. Далее А выбирает некоторую группу лиц, включая себя (на рис.4 — А, B, C). Не имеет значения, является ли подписантом кто-то из группы, кроме А, к тому же, это невозможно установить. А разбивает ЭЦП контрольного сообщения на фрагменты, в соответствии с числом участников группы и распределяет эти фрагменты среди них.

    Разбиение на фрагменты на рисунке показано условно. Простое разрезание текста, даже с перестановкой символов — плохое решение. Лучше воспользоваться одним из алгоритмов разделения секрета.

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


    Рис. 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 за наводку!
    Поделиться публикацией

    Комментарии 37

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

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

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

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

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

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

              Также всем придётся постоянно мониторить некоторое информационное пространство в ожидании запроса на проверку или включения его в группу.

              Может проще просто случайным образом раздать всем по паре анонимных ключей (открытый-закрытый)? Если не знаем, кому какая подпись попала, то все ваши требования выполняются.
                0
                Чтобы «случайным образом раздать» нужна третья сторона, которй все доверяют, т.к. эта сторона знает, кто какой ключ получил.
                  +1
                  Кстати, хорошая идея, раздать случайно ключи. Можно попытаться прикрутить протокол «Покер по телефону».
                  Да и на хабре где-то была статья, как играть в покер втроем.

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

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

                        Нет, необязательно. С помощью слепой подписи можно обеспечить неотслеживаемую раздачу центром ключей: каждый участник сам подготавливает ключевую пару, а потом центр подписывает ее — но лишь один раз на участника.
                0
                Если все участники группы в сговоре против A, то они могут не откусывать подпись и хранить логи. Так что, постфактум у них будет электронно подписанное доказательство того, что A — инициатор.
                  0
                  Это не будет доказательством. Подписанные фрагменты после завершения верификации доступны всем, так что любой может сфабриковать логи с любой последовательностью прохождения фрагментов.
                    0
                    Если все участники группы в сговоре против A, они могут прервать процедуру, когда последний из них получит фрагменты. Потом С предъявляет фрагмент с подписью B, а B — с подписью A. Чтобы не оказаться крайним, A должен предъявить фрагмент с подписью C, чего он, естественно, сделать не может.

                    Но можно настроить софт таким образом, чтобы при прерывании процедуры все фрагменты уничтожались автоматически. Тогда заявление A, что у него нет такого фрагмента, т.к. он удален, будет вполне правдоподобно.
                +2
                По поводу вбросов. Многостаночника можно выявить, только если остальные участники — честны и проголосовали лишь один раз. Если каждый заведет себе две пары анонимных ключей, думая, что он единственный такой хитрый, — вся система провалится. Анонимных ключей-голосов будет гораздо больше, чем участников. Не очень хорошая петиция.
              0
              Не совсем понятно на счет группы.

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

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

                Тот, кто не состоит в группе, не может запистить цепочку подписания фрагментов, т.к. второй проверяет подпись первого, третий — второго и.т.д. Таким образом, если кто-то захочет подтвердить сразу два анонимных ключа, он должен состоять в обоих группах. А если таких ключей не 2, а скажем 1000 (число, сравнимое с количеством голосов в целом), то такого человека сразу видно, т.к. он будет состоять сразу в 1000 группах и это нельзя будет объяснить случайностью.
                  0
                  Стоп! Не понял. Что значит «знает анонимный закрытый ключ»? Знает кому принадлежит данный анонимный закрытый ключ? Тогда он будет знать и источник секрета. Если эта фраза означает не это, тогда что?
                    0
                    По порядку. A подал голос, у него есть соотв. закрытый анонимный ключ. Но этот факт никому, кроме A неизвестен. Наступает время верификации. A подписывает контрольное сообщение этим же закрытым ключом. Теперь любой, кто увидит эту ЭЦП, может сказать: «Да, её создал тот же человек, кто и поставил голос.» Но что этот человек — A, никто по-прежнему не знает.

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

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

                      Ваш вариант с группами имеет смысл только в двух случаях:
                      1. Когда разбивка на группы фиксирована.
                      2. Когда проверка производиться в глобальном масштабе — т.е. процедура проверки обязательна для всех голосов.
                        0
                        Группа нужна, чтобы не дать голосовать тем, у кого на это нет прав. То есть нет сертифицированных персональных ключей. У всех в группе такие ключи должны быть.

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

                        Если у A несколько анонимных ключей, то для подтверждения первого он выберет группу ABC, для второго — ADE, для третьего — AFG и т.д. Пересечение групп выдаст A. Если A будет хитрее и выберет группы ABC, ABD, ABE… то подозрение падает сразу на двоих: A и B. Можно не разбираться, кто из них голосовал многократно, а просто признать все эти голоса недействительными.
                0
                Идеальная схема фальсификаций. На этапе создания «персональных» ключей внести процентов 10 «мертвых душ», и дальше дело техники :)
                  0
                  Так можно только увеличить количество голосов, а это невыгодно администрации. Петицию-то подписывают обычно не «за», а «против».
                  0
                  Видимо я не до конца понял. Группа не знает приватный ключ А. А отправляет группе часть своего секрета, не подписывая его или подписывая своим персональным ключем. При этом каждый участник группы знает от кого пришла часть секрета. Они подписывают свою часть своим персональным ключем и отправляют эти части проверющему. При этом группа будет удостоверять анонимный ключ посредством части секрета.

                  Вот такой способ имеет смысл. Возможно, вы его и описываете, только либо вы неправильно его описываете, либо я его изначально неправильно понял.
                    0
                    Все именно так. А отправляет группе часть своего секрета, не подписывая его или подписывая своим персональным ключом. В качестве части секрета выступает контрольное сообщение, подписанное анонимным ключом A. Этого достаточно, чтобы подтвердить наличие у A анонимного ключа, но недостаточно, чтобы восстановить сам ключ.
                    0
                    — удалено, ошибся уровнем -----
                      +1
                      Может, проще разбивать не сообщение с верификацией, а непосредственно сообщение с «голосом» и выстраивать цепочку для него?

                      Пусть конкретный участник решает передать свой голос системе учета голосов.
                      Для этого он выбирает несколько цепочек отправителей, разделяет сообщение с голосом на количество таких цепочек, передает соответствующие сообщения участникам голосования. После чего сообщение, пройдя через цепочку голосующих, передается системе подсчета. После каждого этапа передачи происходит синхронизация: каждый участник в открытую передает системе количество пакетов, пропущенных через него и детальную разбивку: от кого пакет пришел и кому он ушел.
                      Система подсчета собирает изначальные сообщения и публикует результаты.
                      В общем случае фальсификатор сможет только помешать процедуре голосования и легко определяется (для этого необходимо заставить всех участников системы некоторое время хранить обмен).
                        0
                        В таком случае легко отследить инициатора цепочки, разве нет?
                        А еще для работы предложенной вами системы необходимо присутствие большинства участников, независимо от того, голосуют они или нет.
                          0
                          отследить инициатора цепочки в общем случае можно только при условии, что все участники одной из цепочек скомпроментированы.
                          учитывая то, что изначально цепочку строит голосующий, можно строить цепочки из возможно нескомпроментированных участников.
                            0
                            Это тот же принцип, по которому работает Tor? Тогда действительно, отследить начало цепочки будет сложно. Но замечание о необходимости присутствия в сети большинства участников остается в силе.
                            Предложенная мной система позволяет провести сбор подписей быстро, с минимальной затратой ресурсов и не привлекая дополнительных лиц, кроме голосующих. Затем можно провести выборочную верификацию, и если возникнут подозрения, проверять все большее и большее количество голосов, вплоть до 100%.
                              0
                              Да, идея похожа на Tor.
                              «Cложность» сбора подписей в Вашем варианте — 1 «проход»
                              В моем — N «проходов»
                              Сложность верификации, наоборот: в Вашем варианте — N, в моем — 1.
                              Так что затраты примерно одни и те же.
                              Но вместо сомнительной вероятностной верификации голосов появляется строгий механизм обнаружения нарушений и, при необходимости, нарушителя.
                              Ну и еще бы как минус я мог бы назвать обязательность присутствия участников онлайн на весь период голосования (хотя в Вашем случае есть обязательность присутствия онлайн во время верификации)
                        0
                        -
                          0
                          Интересно было бы придумать какой-то формальный язык, который бы описывал все криптографические протоколы. И еще какой-нибудь способ проверки, что нужные условия выполняются. Правда, я не представляю, как можно доказать, что некто X, зная Y не может из этого вычислить Z.
                          На сколько я понимаю, на данный момент для каждого такого протокола доказательство его свойств — сложная нетривиальная задача.
                          +2
                          Это действительно велосипед. Класс алгоритмов называется Group/Ring signatures. Это аналог Вашего «распределения фрагментов».

                          В случае, когда голосовать можно лишь раз, предлагается усовершенствованная схема, например traceable ring signature
                            0
                            Очень полезный алгоритм!
                            Такой можно применить в электронных системах голосования на государственном уровне!
                            Если я все правильно понимаю, такое голосование почти не возможно сфальсифицировать. И это очень круто!

                            Я думаю этот алгоритм еще один шаг к государству 2.0
                              +1
                              Алгоритмов электронного голосования существует много, и на хабре их неоднократно обсуждали. Здесь немного другая задача, основное отличие следующее:
                              При голосовании тайной является содержимое голоса, а список голосовавших открыт. У нас — наоборот, содержимое голоса тайны не составляет (фактически, один вариант: «поддержать петицию»), зато секретным должен быть список подписантов.
                              0
                              Второе предложение в статье. В википедии пишут надстрочную надпись курсивом: "Источник?"

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое