Рейтинг:2

Эль-Гамаля с эллиптическими кривыми и семантической безопасностью

флаг ng

Чтобы зашифровать элемент группы $P$ с открытым ключом $К$ и случайность $г$ используя Эль-Гамаля на эллиптических кривых с базовой точкой $G$ мы делаем следующее $(c_1, c_2) = (r\cdot G; P+r\cdot K)$.

Когда мы хотим зашифровать сообщение в свободной форме $м$, мы должны преобразовать его в элемент группы $P$ первый. Для этого мы можем либо использовать скалярное умножение $P=m\cdotG$ (аддитивно гомоморфно) или сопоставьте сообщение $P = карта (м) $ (мультипликативный гомоморфный). Первый дает не просто точка, а элемент группы. Последнее сложнее.

Все методы, которые я нашел, сопоставляют сообщение с точкой кривой (Подход Коблица, его вариант, инъективная кодирующая статья). Однако нет гарантии, что полученная точка принадлежит циклической группе (т.е. имеет правильный порядок).

Итак, используя кодирование только в точку EC приводит к семантически не защищающий Эль-Гамаля. Это в основном похоже на утечку, если сообщение является квадратичным остатком или нет при использовании $G_q$ над конечными полями с $p = 2q+1$ и сообщения от $Z_p^*$ без кодирования (подробности о том, почему происходит утечка, см. здесь или же здесь).

Есть ли способ закодировать случайное сообщение в точку EC правильного порядка (т.е.групповой элемент)? Есть ли способ преобразовать точку EC в элемент группы?

fgrieu avatar
флаг ng
Кодирование $P=m\cdot G$ имеет недостаток: оно делает расшифровку трудновыполнимой с вычислительной точки зрения.
kelalaka avatar
флаг in
[Эллигатор 1 и Эллигатор 2] (https://elligator.cr.yp.to/)
pintor avatar
флаг ng
@fgrieu, правда. Он работает только для очень небольшого пространства сообщения, плюс требует предварительного вычисления таблицы для расшифровки или многих итераций, чтобы "восстановить" $m$ из $m\cdot G$, т.е. сломать dlog. Но пока я не вижу другого способа получить семантически безопасный ElGamal, сохранив при этом его гомоморфные свойства.
pintor avatar
флаг ng
@kelalaka, спасибо! Я посмотрю поближе. На первый взгляд это кажется усовершенствованием инъективного кодирования Фуке и др. др. Таким образом, я боюсь, что это снова кодирование в точку кривой, а не в ее большую подгруппу простого порядка (т.е. правильный порядок точек не гарантируется).
pintor avatar
флаг ng
@kelalaka, к сожалению, Эллигатор не всегда дает очки в правильном порядке. Похоже на открытую проблему в ECC

Ответить или комментировать

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