Comments 37
Если ключи публикуются анонимно, как гарантировать, что одному человеку принадлежит один анонимный ключ?
Кажется по времени публикации можно точно определить второго в цепочке. или под публикацией имелось в виду что-то еще?
Кажется по времени публикации можно точно определить второго в цепочке. или под публикацией имелось в виду что-то еще?
1. Это можно выяснить во время верификации. Если несколько анонимных ключей будут принадлежать одному человеку, то этот человек неминуемо будет присутствовать в каждой группе, что сразу выдает многостаночника. Конечно, один человек может попасть в несколько групп и случайно, но вероятность этого легко подсчитать (при истинно случайном выборе групп). Все, что сильно выходит за рамки теоретической вероятности — скорее всего, вброс голосов.
2. Порядок следования людей в цепочке не представляет секрета (его знают все участники группы). Но цепочка закольцована, и никто, кроме инициатора, не знает, где у нее начало. Если можно установить, кто второй, то будет ясно, и кто первый, и кто десятый. Чтобы это нельзя было установить, и вводится случайная задержка перед публикацией. Например, в 12:00 стартует процедура обмена фрагментами, в 13:00 она заканчивается, с 13:00 до 15:00 участники публикуют подписанные фрагменты, кто когда хочет.
2. Порядок следования людей в цепочке не представляет секрета (его знают все участники группы). Но цепочка закольцована, и никто, кроме инициатора, не знает, где у нее начало. Если можно установить, кто второй, то будет ясно, и кто первый, и кто десятый. Чтобы это нельзя было установить, и вводится случайная задержка перед публикацией. Например, в 12:00 стартует процедура обмена фрагментами, в 13:00 она заканчивается, с 13:00 до 15:00 участники публикуют подписанные фрагменты, кто когда хочет.
Не должно быть отдельного ПО, обеспечивающего эту систему. То есть все операции должны быть осуществимы при помощи стандартных уже имеющихся средств. после того как А выберет группу соучастников, как он оповестит их о составе группы и последовательности обработки, не раскрыв информацию о себе?
Алгоритм действий членов группы при проверке достаточно сложен. Нужно подпись чужую удалить, другому переслать, подождать и опубликовать. Для большой группы людей такой процесс сложно контроллировать. Кстати, как определить какой фрагмент кому подписывать? Вдруг третий подпишет тот же фрагмент, что и первый.
Алгоритм действий членов группы при проверке достаточно сложен. Нужно подпись чужую удалить, другому переслать, подождать и опубликовать. Для большой группы людей такой процесс сложно контроллировать. Кстати, как определить какой фрагмент кому подписывать? Вдруг третий подпишет тот же фрагмент, что и первый.
Да, согласен, система довольно сложная получилась. Если кто сможет придумать проще, будет отлично.
> как он оповестит их о составе группы и последовательности обработки, не раскрыв информацию о себе?
Например, он публикует анонимное широковещательное сообщение: «Сегодня, в 12:00 GMT стартует обмен фрагментами. Участники: A, B, C». Затем все участники (включая самого A) публикуют подтверждение. В указанное время они ждут пересылок.
> как определить какой фрагмент кому подписывать?
Следующий за уже подписанным. Допустим, очередной участник получил 10 фрагментов, из которых подписан пятый. Он проверяет и откусывает эту подпись, затем подписывает шестой фрагмент. Тот, кто получил подписанный 10-й, подписывает первый фрагмент.
> как он оповестит их о составе группы и последовательности обработки, не раскрыв информацию о себе?
Например, он публикует анонимное широковещательное сообщение: «Сегодня, в 12:00 GMT стартует обмен фрагментами. Участники: A, B, C». Затем все участники (включая самого A) публикуют подтверждение. В указанное время они ждут пересылок.
> как определить какой фрагмент кому подписывать?
Следующий за уже подписанным. Допустим, очередной участник получил 10 фрагментов, из которых подписан пятый. Он проверяет и откусывает эту подпись, затем подписывает шестой фрагмент. Тот, кто получил подписанный 10-й, подписывает первый фрагмент.
«он публикует анонимное широковещательное сообщение» — то есть нужен механизм анонимной публикации. При этом любой аноним может парализовать работу механизма, публикуя недостоверные сообщения.
Также всем придётся постоянно мониторить некоторое информационное пространство в ожидании запроса на проверку или включения его в группу.
Может проще просто случайным образом раздать всем по паре анонимных ключей (открытый-закрытый)? Если не знаем, кому какая подпись попала, то все ваши требования выполняются.
Также всем придётся постоянно мониторить некоторое информационное пространство в ожидании запроса на проверку или включения его в группу.
Может проще просто случайным образом раздать всем по паре анонимных ключей (открытый-закрытый)? Если не знаем, кому какая подпись попала, то все ваши требования выполняются.
Чтобы «случайным образом раздать» нужна третья сторона, которй все доверяют, т.к. эта сторона знает, кто какой ключ получил.
Кстати, хорошая идея, раздать случайно ключи. Можно попытаться прикрутить протокол «Покер по телефону».
Да и на хабре где-то была статья, как играть в покер втроем.
Да и на хабре где-то была статья, как играть в покер втроем.
Идея о случайной раздаче ключей мне нравится всем, кроме одного: перед подписанием все (или почти все) участники системы должны обменяться ключами. Это приемлемо для систем электронного голосования, когда явка составляет больше половины и стремится к 100%, но не годится для наших целей, когда число подписантов может составлять доли процента от общего числа участников.
Еще одно отличие от покера по телефону в том, что там набор карт не представляет секрета, секретным является только порядок. А у нас секретным является и порядок анонимных ключей, и их содержание. Но эту проблему, думаю, можно легко решить.
Еще одно отличие от покера по телефону в том, что там набор карт не представляет секрета, секретным является только порядок. А у нас секретным является и порядок анонимных ключей, и их содержание. Но эту проблему, думаю, можно легко решить.
Если случайный обмен ключами делается централизованно, то владелец этой системы обмена ключей может всех заложить. Сами люди для такого обмена не согранизуются вдостаточно больших количествах.
Раздать случайным образом можно, но тогда не гарантировать, что каждый получит ровно один ключ.
Раздать случайным образом можно, но тогда не гарантировать, что каждый получит ровно один ключ.
Если случайный обмен ключами делается централизованно, то владелец этой системы обмена ключей может всех заложить.
Нет, необязательно. С помощью слепой подписи можно обеспечить неотслеживаемую раздачу центром ключей: каждый участник сам подготавливает ключевую пару, а потом центр подписывает ее — но лишь один раз на участника.
Если все участники группы в сговоре против A, то они могут не откусывать подпись и хранить логи. Так что, постфактум у них будет электронно подписанное доказательство того, что A — инициатор.
Это не будет доказательством. Подписанные фрагменты после завершения верификации доступны всем, так что любой может сфабриковать логи с любой последовательностью прохождения фрагментов.
Если все участники группы в сговоре против A, они могут прервать процедуру, когда последний из них получит фрагменты. Потом С предъявляет фрагмент с подписью B, а B — с подписью A. Чтобы не оказаться крайним, A должен предъявить фрагмент с подписью C, чего он, естественно, сделать не может.
Но можно настроить софт таким образом, чтобы при прерывании процедуры все фрагменты уничтожались автоматически. Тогда заявление A, что у него нет такого фрагмента, т.к. он удален, будет вполне правдоподобно.
Но можно настроить софт таким образом, чтобы при прерывании процедуры все фрагменты уничтожались автоматически. Тогда заявление A, что у него нет такого фрагмента, т.к. он удален, будет вполне правдоподобно.
По поводу вбросов. Многостаночника можно выявить, только если остальные участники — честны и проголосовали лишь один раз. Если каждый заведет себе две пары анонимных ключей, думая, что он единственный такой хитрый, — вся система провалится. Анонимных ключей-голосов будет гораздо больше, чем участников. Не очень хорошая петиция.
Не совсем понятно на счет группы.
Те, кто подписывает часть секрета своей персональной подписью, должны знать что A является источником этого секрета? Если нет, то вся эта процедура бессмысленна.
Я так понимаю, что именно на группу ложится обязанность проверять что данный проверяемый не имеет дублированных анонимных ключей? В общем логично. Но что помешает проверяемому иметь несколько ключей и для их проверки использовать несколько разных не пересекающихся групп?
Те, кто подписывает часть секрета своей персональной подписью, должны знать что A является источником этого секрета? Если нет, то вся эта процедура бессмысленна.
Я так понимаю, что именно на группу ложится обязанность проверять что данный проверяемый не имеет дублированных анонимных ключей? В общем логично. Но что помешает проверяемому иметь несколько ключей и для их проверки использовать несколько разных не пересекающихся групп?
Никто в группе не знает, кто источник подтверждаемого секрета. Группа подтверждает, что кто-то из них знает анонимный закрытый ключ (им подписано контрольное сообщение).
Тот, кто не состоит в группе, не может запистить цепочку подписания фрагментов, т.к. второй проверяет подпись первого, третий — второго и.т.д. Таким образом, если кто-то захочет подтвердить сразу два анонимных ключа, он должен состоять в обоих группах. А если таких ключей не 2, а скажем 1000 (число, сравнимое с количеством голосов в целом), то такого человека сразу видно, т.к. он будет состоять сразу в 1000 группах и это нельзя будет объяснить случайностью.
Тот, кто не состоит в группе, не может запистить цепочку подписания фрагментов, т.к. второй проверяет подпись первого, третий — второго и.т.д. Таким образом, если кто-то захочет подтвердить сразу два анонимных ключа, он должен состоять в обоих группах. А если таких ключей не 2, а скажем 1000 (число, сравнимое с количеством голосов в целом), то такого человека сразу видно, т.к. он будет состоять сразу в 1000 группах и это нельзя будет объяснить случайностью.
Стоп! Не понял. Что значит «знает анонимный закрытый ключ»? Знает кому принадлежит данный анонимный закрытый ключ? Тогда он будет знать и источник секрета. Если эта фраза означает не это, тогда что?
По порядку. A подал голос, у него есть соотв. закрытый анонимный ключ. Но этот факт никому, кроме A неизвестен. Наступает время верификации. A подписывает контрольное сообщение этим же закрытым ключом. Теперь любой, кто увидит эту ЭЦП, может сказать: «Да, её создал тот же человек, кто и поставил голос.» Но что этот человек — A, никто по-прежнему не знает.
Теперь собралась группа {A, B, C}, они распределили между собой фрагменты ЭЦП и подписали своими персонализованными ключами. Тем самым подтверждая, что один из них — тот, кто эту ЭЦП создал, а значит, и тот, чей голос.
Теперь собралась группа {A, B, C}, они распределили между собой фрагменты ЭЦП и подписали своими персонализованными ключами. Тем самым подтверждая, что один из них — тот, кто эту ЭЦП создал, а значит, и тот, чей голос.
Т.к. проверки будут выборочными, а не глобальными, при второй проверке ничто не помешает А выбрать группа A, D, C для проверки второго анонимного ключа. И так до бесконечности. Т.е. принцип «один человек» — «один анонимный ключ» не соблюдается.
Кстати, в таком случае вообще непонятно зачем нужна группа. Проверющий просто получает от А весь секрет подписанный его анонимным ключем. Это так-же будет означать что «это сообщение отправил тот-же человек, который оставил свой голос». Но что это докажет? По моему, ничего.
Ваш вариант с группами имеет смысл только в двух случаях:
1. Когда разбивка на группы фиксирована.
2. Когда проверка производиться в глобальном масштабе — т.е. процедура проверки обязательна для всех голосов.
Кстати, в таком случае вообще непонятно зачем нужна группа. Проверющий просто получает от А весь секрет подписанный его анонимным ключем. Это так-же будет означать что «это сообщение отправил тот-же человек, который оставил свой голос». Но что это докажет? По моему, ничего.
Ваш вариант с группами имеет смысл только в двух случаях:
1. Когда разбивка на группы фиксирована.
2. Когда проверка производиться в глобальном масштабе — т.е. процедура проверки обязательна для всех голосов.
Группа нужна, чтобы не дать голосовать тем, у кого на это нет прав. То есть нет сертифицированных персональных ключей. У всех в группе такие ключи должны быть.
В идеале проверки должны быть глобальными, но на практике все упрется в техническую возможность. Верификация — довольно ресурсоемкий процесс. При «оффлайнововм» сборе голосов, насколько мне известно, тоже проверяется не каждая подпись.
Если у A несколько анонимных ключей, то для подтверждения первого он выберет группу ABC, для второго — ADE, для третьего — AFG и т.д. Пересечение групп выдаст A. Если A будет хитрее и выберет группы ABC, ABD, ABE… то подозрение падает сразу на двоих: A и B. Можно не разбираться, кто из них голосовал многократно, а просто признать все эти голоса недействительными.
В идеале проверки должны быть глобальными, но на практике все упрется в техническую возможность. Верификация — довольно ресурсоемкий процесс. При «оффлайнововм» сборе голосов, насколько мне известно, тоже проверяется не каждая подпись.
Если у A несколько анонимных ключей, то для подтверждения первого он выберет группу ABC, для второго — ADE, для третьего — AFG и т.д. Пересечение групп выдаст A. Если A будет хитрее и выберет группы ABC, ABD, ABE… то подозрение падает сразу на двоих: A и B. Можно не разбираться, кто из них голосовал многократно, а просто признать все эти голоса недействительными.
Идеальная схема фальсификаций. На этапе создания «персональных» ключей внести процентов 10 «мертвых душ», и дальше дело техники :)
Видимо я не до конца понял. Группа не знает приватный ключ А. А отправляет группе часть своего секрета, не подписывая его или подписывая своим персональным ключем. При этом каждый участник группы знает от кого пришла часть секрета. Они подписывают свою часть своим персональным ключем и отправляют эти части проверющему. При этом группа будет удостоверять анонимный ключ посредством части секрета.
Вот такой способ имеет смысл. Возможно, вы его и описываете, только либо вы неправильно его описываете, либо я его изначально неправильно понял.
Вот такой способ имеет смысл. Возможно, вы его и описываете, только либо вы неправильно его описываете, либо я его изначально неправильно понял.
Все именно так. А отправляет группе часть своего секрета, не подписывая его или подписывая своим персональным ключом. В качестве части секрета выступает контрольное сообщение, подписанное анонимным ключом A. Этого достаточно, чтобы подтвердить наличие у A анонимного ключа, но недостаточно, чтобы восстановить сам ключ.
— удалено, ошибся уровнем -----
Может, проще разбивать не сообщение с верификацией, а непосредственно сообщение с «голосом» и выстраивать цепочку для него?
Пусть конкретный участник решает передать свой голос системе учета голосов.
Для этого он выбирает несколько цепочек отправителей, разделяет сообщение с голосом на количество таких цепочек, передает соответствующие сообщения участникам голосования. После чего сообщение, пройдя через цепочку голосующих, передается системе подсчета. После каждого этапа передачи происходит синхронизация: каждый участник в открытую передает системе количество пакетов, пропущенных через него и детальную разбивку: от кого пакет пришел и кому он ушел.
Система подсчета собирает изначальные сообщения и публикует результаты.
В общем случае фальсификатор сможет только помешать процедуре голосования и легко определяется (для этого необходимо заставить всех участников системы некоторое время хранить обмен).
Пусть конкретный участник решает передать свой голос системе учета голосов.
Для этого он выбирает несколько цепочек отправителей, разделяет сообщение с голосом на количество таких цепочек, передает соответствующие сообщения участникам голосования. После чего сообщение, пройдя через цепочку голосующих, передается системе подсчета. После каждого этапа передачи происходит синхронизация: каждый участник в открытую передает системе количество пакетов, пропущенных через него и детальную разбивку: от кого пакет пришел и кому он ушел.
Система подсчета собирает изначальные сообщения и публикует результаты.
В общем случае фальсификатор сможет только помешать процедуре голосования и легко определяется (для этого необходимо заставить всех участников системы некоторое время хранить обмен).
В таком случае легко отследить инициатора цепочки, разве нет?
А еще для работы предложенной вами системы необходимо присутствие большинства участников, независимо от того, голосуют они или нет.
А еще для работы предложенной вами системы необходимо присутствие большинства участников, независимо от того, голосуют они или нет.
отследить инициатора цепочки в общем случае можно только при условии, что все участники одной из цепочек скомпроментированы.
учитывая то, что изначально цепочку строит голосующий, можно строить цепочки из возможно нескомпроментированных участников.
учитывая то, что изначально цепочку строит голосующий, можно строить цепочки из возможно нескомпроментированных участников.
Это тот же принцип, по которому работает Tor? Тогда действительно, отследить начало цепочки будет сложно. Но замечание о необходимости присутствия в сети большинства участников остается в силе.
Предложенная мной система позволяет провести сбор подписей быстро, с минимальной затратой ресурсов и не привлекая дополнительных лиц, кроме голосующих. Затем можно провести выборочную верификацию, и если возникнут подозрения, проверять все большее и большее количество голосов, вплоть до 100%.
Предложенная мной система позволяет провести сбор подписей быстро, с минимальной затратой ресурсов и не привлекая дополнительных лиц, кроме голосующих. Затем можно провести выборочную верификацию, и если возникнут подозрения, проверять все большее и большее количество голосов, вплоть до 100%.
Да, идея похожа на Tor.
«Cложность» сбора подписей в Вашем варианте — 1 «проход»
В моем — N «проходов»
Сложность верификации, наоборот: в Вашем варианте — N, в моем — 1.
Так что затраты примерно одни и те же.
Но вместо сомнительной вероятностной верификации голосов появляется строгий механизм обнаружения нарушений и, при необходимости, нарушителя.
Ну и еще бы как минус я мог бы назвать обязательность присутствия участников онлайн на весь период голосования (хотя в Вашем случае есть обязательность присутствия онлайн во время верификации)
«Cложность» сбора подписей в Вашем варианте — 1 «проход»
В моем — N «проходов»
Сложность верификации, наоборот: в Вашем варианте — N, в моем — 1.
Так что затраты примерно одни и те же.
Но вместо сомнительной вероятностной верификации голосов появляется строгий механизм обнаружения нарушений и, при необходимости, нарушителя.
Ну и еще бы как минус я мог бы назвать обязательность присутствия участников онлайн на весь период голосования (хотя в Вашем случае есть обязательность присутствия онлайн во время верификации)
-
Интересно было бы придумать какой-то формальный язык, который бы описывал все криптографические протоколы. И еще какой-нибудь способ проверки, что нужные условия выполняются. Правда, я не представляю, как можно доказать, что некто X, зная Y не может из этого вычислить Z.
На сколько я понимаю, на данный момент для каждого такого протокола доказательство его свойств — сложная нетривиальная задача.
На сколько я понимаю, на данный момент для каждого такого протокола доказательство его свойств — сложная нетривиальная задача.
Это действительно велосипед. Класс алгоритмов называется Group/Ring signatures. Это аналог Вашего «распределения фрагментов».
В случае, когда голосовать можно лишь раз, предлагается усовершенствованная схема, например traceable ring signature
В случае, когда голосовать можно лишь раз, предлагается усовершенствованная схема, например traceable ring signature
Очень полезный алгоритм!
Такой можно применить в электронных системах голосования на государственном уровне!
Если я все правильно понимаю, такое голосование почти не возможно сфальсифицировать. И это очень круто!
Я думаю этот алгоритм еще один шаг к государству 2.0
Такой можно применить в электронных системах голосования на государственном уровне!
Если я все правильно понимаю, такое голосование почти не возможно сфальсифицировать. И это очень круто!
Я думаю этот алгоритм еще один шаг к государству 2.0
Алгоритмов электронного голосования существует много, и на хабре их неоднократно обсуждали. Здесь немного другая задача, основное отличие следующее:
При голосовании тайной является содержимое голоса, а список голосовавших открыт. У нас — наоборот, содержимое голоса тайны не составляет (фактически, один вариант: «поддержать петицию»), зато секретным должен быть список подписантов.
При голосовании тайной является содержимое голоса, а список голосовавших открыт. У нас — наоборот, содержимое голоса тайны не составляет (фактически, один вариант: «поддержать петицию»), зато секретным должен быть список подписантов.
Второе предложение в статье. В википедии пишут надстрочную надпись курсивом: "Источник?"
Не хотелось бы скатываться в политику, но пару примеров приведу:
— Открытие кафедры теологии в МИФИ.
«Подписи за то, чтобы убрать крест, собирали на входе в МИФИ <...> Были контрмеры по отношению к преподавателям и студентам, вплоть до угроз об отчислении из института.»
— В Брянской области угрожают депутатам, поддержавшим кандидата от «Справедливой России».
«В адрес сразу трех депутатов муниципальных советов поступили угрозы с требованием отозвать подпись в поддержку кандидата на должность губернатора Брянской области <...>»
— Открытие кафедры теологии в МИФИ.
«Подписи за то, чтобы убрать крест, собирали на входе в МИФИ <...> Были контрмеры по отношению к преподавателям и студентам, вплоть до угроз об отчислении из института.»
— В Брянской области угрожают депутатам, поддержавшим кандидата от «Справедливой России».
«В адрес сразу трех депутатов муниципальных советов поступили угрозы с требованием отозвать подпись в поддержку кандидата на должность губернатора Брянской области <...>»
Sign up to leave a comment.
Алгоритм анонимной коллективной подписи