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

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

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

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

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

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

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

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

Два возможных результата: да или нет . Мы представим эти результаты численно +1 и -1 соответственно.
Число органов k , которые будут подсчитывать голоса.
Число избирателей n , которые подадут голоса.

Заранее каждый орган власти генерирует общедоступный числовой xk _ключ .
Каждый избиратель кодирует свой голос в полиноме p _n в соответствии со следующими правилами: Полином должен иметь степень k - 1 , его постоянный член должен быть либо +1, либо -1 (что соответствует голосованию «за» или голосованию «нет»), а другие его коэффициенты должны генерироваться случайным образом.
Каждый избиратель вычисляет значение своего полинома p _n каждого органа власти по открытому ключу x _k .
- В результате получается k баллов, по одному за каждый авторитет.
- Эти k точек представляют собой «части» голоса: если вы знаете все точки, вы можете вычислить полином p _n (и, следовательно, вы можете выяснить, как проголосовал избиратель). Однако, если вы знаете только некоторые точки, вы не сможете вычислить полином. (Это потому, что вам нужно n точек для определения полинома степени ( n − 1) . Две точки определяют линию, три точки определяют параболу и т. д.)
Избиратель отправляет каждому органу власти значение, полученное с использованием ключа органа власти.
Каждый авторитет собирает ценности, которые он получает. Поскольку каждый орган власти получает только одно значение от каждого избирателя, он не может определить полином какого-либо конкретного избирателя. Более того, он не может предсказать, как изменение представленных материалов повлияет на голосование.
После того как избиратели подали свои голоса, каждый орган k вычисляет и объявляет сумму A _k всех полученных им значений.
Имеется k сумм, A _k ; когда они объединяются вместе, они определяют уникальный полином P ( x ) – в частности, сумму всех полиномов избирателей: P ( x ) = p ₁ ( x ) + p ₂ ( x ) + ... + p _n ( Икс ).
- Постоянный член P ( x ) на самом деле является суммой всех голосов, потому что постоянный член P ( x ) представляет собой сумму постоянных членов отдельного p _n .
- Таким образом, постоянный член P ( x ) дает совокупный результат выборов: если он положительный, больше людей проголосовали за +1, чем за -1; если он отрицательный, за -1 проголосовало больше людей, чем за +1.

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

Этот протокол работает до тех пор, пока не все k органов власти коррумпированы — если бы они были коррумпированы, то они могли бы сотрудничать, чтобы восстановить P ( x ) для каждого избирателя, а также впоследствии изменить результаты голосов.

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

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

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

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

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

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

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

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

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

^ Шенмейкерс, Берри (1999). «Простая публично проверяемая схема обмена секретами и ее применение к электронному голосованию». Достижения криптологии — КРИПТО' 99 . Конспекты лекций по информатике. Том. 1666. стр. 148–164. CiteSeerX 10.1.1.102.9375 . дои : 10.1007/3-540-48405-1_10 . ISBN 978-3-540-66347-8 .

[1] Шенмейкерс, Берри (1999). «Простая публично проверяемая схема обмена секретами и ее применение к электронному голосованию». Достижения криптологии — КРИПТО' 99 . Конспекты лекций по информатике. Том. 1666. стр. 148–164. CiteSeerX 10.1.1.102.9375 . дои : 10.1007/3-540-48405-1_10 . ISBN 978-3-540-66347-8 .

[1]