Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Техника [ править ]

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

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

Примеры [ править ]

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

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

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

Особенности [ править ]

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

Протокол требует т + 1 власти должны быть завершены, поэтому в случае , если есть N> т + 1 власти, Nt-1 власти могут быть повреждены, что дает НАСТОЯЩЕГО ПРОТОКОЛА определенную степень надежности.

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

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

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

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

Уязвимости [ править ]

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

См. Также [ править ]

Ссылки [ править ]

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