Гомоморфное разделение секретов - Homomorphic secret sharing

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

Техника

Гомоморфное разделение секрета используется для передачи секрета нескольким получателям следующим образом:

  1. Преобразуйте «секрет» с помощью гомоморфизма. Это часто превращает секрет в форму, которой легко манипулировать или хранить. В частности, может существовать естественный способ «разбить» новую форму, как того требует шаг (2).
  2. Разделите преобразованный секрет на несколько частей, по одной для каждого получателя. Секрет должен быть разделен таким образом, чтобы его можно было восстановить, только когда все или большинство частей объединены. (Увидеть секретный обмен )
  3. Раздайте по частям секрета каждому из получателей.
  4. Объедините каждую из частей получателя, чтобы восстановить преобразованный секрет, возможно, в указанное время.
  5. Обратить гомоморфизм, чтобы восстановить исходный секрет.

Пример: децентрализованный протокол голосования

Предположим, сообщество хочет провести выборы, но оно хочет убедиться, что счетчики голосов не лгут о результатах. Используя тип гомоморфного разделения секрета, известный как Секретный обмен Шамиром, каждый член сообщества может добавить свой голос в форму, которая разделена на части, каждая часть затем отправляется на другой счетчик голосов. Фигуры спроектированы таким образом, что счетчики голосов не могут предсказать, как любые изменения в каждой части повлияют на целое, таким образом, препятствуя счетчикам голосов вмешиваться в свои части. Когда все голоса получены, счетчики голосов объединяют их, позволяя восстановить совокупные результаты выборов.

Более подробно, предположим, что у нас есть выборы с:

  • Два возможных исхода либо да или нет. Мы представим эти результаты в числовом виде как +1 и -1 соответственно.
  • Ряд органов власти, k, кто будет подсчитывать голоса.
  • Количество избирателей, п, кто подаст голоса.
  1. Заранее каждый орган генерирует общедоступный цифровой ключ, Иксk.
  2. Каждый избиратель кодирует свой голос в полином пп по следующим правилам: многочлен должен иметь степень к-1, его постоянный член должен быть либо +1 или -1 (соответствует голосованию «за» или голосованию «против»), а другие его коэффициенты должны генерироваться случайным образом.
  3. Каждый избиратель вычисляет значение своего многочлена. пп на открытом ключе каждого органа Иксk.
    • Это производит k баллы, по одному на каждый авторитет.
    • Эти k баллы - это «кусочки» голосования: если вы знаете все баллы, вы можете вычислить многочлен пп (а значит, вы можете выяснить, как проголосовал избиратель). Однако, если вы знаете только некоторые из точек, вы не сможете вычислить многочлен. (Это потому, что вам нужно k баллы для определения степеник-1 полином. Две точки определяют линию, три точки определяют параболу и т. Д.)
  4. Избиратель отправляет каждому органу власти значение, полученное с использованием ключа органа.
  5. Каждый авторитет собирает ценности, которые он получает. Поскольку каждый орган власти получает только одно значение от каждого избирателя, он не может обнаружить какой-либо заданный полином избирателя. Более того, он не может предсказать, как изменение представленных материалов повлияет на голосование.
  6. После того, как избиратели подали свои голоса, каждый орган k вычисляет и объявляет сумму Аk всех ценностей, которые он получил.
  7. Есть k суммы, Аk; когда они объединяются вместе, они определяют уникальный полином Р (х)--- в частности, сумма всех полиномов избирателя: P (x) = p1(х) + р2(x) +… + pп(Икс).
    • Постоянный срок Р (х) фактически является суммой всех голосов, потому что постоянный член P (x) - это сумма постоянных членов индивидуального пп.
    • Таким образом, постоянный член Р (х) предоставляет совокупный результат выборов: если он положительный, за +1 проголосовало больше людей, чем за -1; если отрицательный, то за -1 проголосовало больше людей, чем за +1.
Таблица, иллюстрирующая протокол голосования
Иллюстрация протокола голосования. В каждом столбце представлены результаты голосования конкретного избирателя. Каждая строка представляет фигуры, полученные от определенного авторитета.

особенности

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

В протокол требует завершения t + 1 полномочий, поэтому, если имеется N> t + 1 полномочий, N-t-1 полномочий может быть поврежден, что придает протоколу определенную степень устойчивости.

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

При предположениях о t:

  1. Невозможно вернуть бюллетень по идентификатору, поэтому конфиденциальность избирателей сохраняется.
  2. Избиратель не может доказать, как он проголосовал.
  3. Подтвердить голосование невозможно.

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

Уязвимости

  • Избиратель не может быть уверен, что его голос записан правильно.
  • Власти не могут быть уверены, что голоса были законными и равными, например, избиратель может выбрать значение, которое не является допустимым вариантом (т.е. не в {-1, 1}), например -20, 50, что изменит результаты в их пользу.

Смотрите также

использованная литература

  1. ^ Schoenmakers, Берри (1999). «Простая публично проверяемая схема разделения секретов и ее применение в электронном голосовании». Достижения в криптологии. 1666: 148–164. CiteSeerX  10.1.1.102.9375.