Рейтинг:1

Степень вложения кривых характеристики 2 и переноса ЭПДРП

флаг ru

Известно, что мы можем передать экземпляр ECDLP по кривой $Е$ определяется над $\mathbb{F}_p$ для премьер $р$, в экземпляр дискретного журнала в $\mathbb{F}_{p^k}$ для некоторых $к$. Он упоминается как степень вложения, и является наименьшим целым числом $к$ такой, что порядок кривой делит $p^k-1$.

(Один из способов сделать это — использовать пары.)

Меня интересуют бинарные кривые, например. определяется над $\mathbb{F}_{2^m}$ и хочу сделать что-то подобное, но я не могу найти информацию о степени вложения в этом случае (например, в базах данных кривых нет упоминания о степени вложения для бинарных кривых, например https://neuromancer.sk/std/secg/sect233k1). Возможно, какой-то алгебраический аргумент не работает, но я не понимаю, почему.

Контекст: Я хочу доказать утверждение в ЗК о двух дискретных бревнах на разных кривых. Я думал, что если одна кривая определена в $\mathbb{F}_{2^m}$ а другой в $\mathbb{F}_{2^n}$, то если я смогу перенести два экземпляра в конечные поля $\mathbb{F}_{2^{км}}, \mathbb{F}_{2^{ln}}$ куда $к,л$ являются степенями вложения, я могу рассматривать это как расширение поля и использовать арифметику.

Рейтинг:1
флаг ru

Хотя перенос существует для бинарных кривых, степени вложения обычно слишком велики, чтобы их можно было использовать с вычислительной точки зрения.В удобных для сопряжения кривых конструкция специально создает чрезвычайно низкую степень встраивания, но обычно мы ожидаем, что степень вложения будет $O(\ell)$ куда $\ell$ это порядок группы.

Можно вычислить степень вложения, если можно факторизовать $\ell-1$. Один просто вычисляет порядок 2 по модулю $\ell$ (в частности, если 2 — первообразный корень по модулю $\ell$ тогда его порядок $\ell-1$). Если мы напишем $д$ для порядка 2 и эллиптической кривой, если брать по полю $\mathbb F_{2^m}$ тогда степень вложения будет $md/\mathrm{НОД}(м,д)$.

crypcrypcryp avatar
флаг ru
Даже если это нецелесообразно, я хочу работать с $F_{2^km}$ для логического шага в моем доказательстве, поэтому, если спаривание существует, это нормально. Иначе узнали бы вы, существуют ли кривые, удобные для спаривания, на полях характеристики 2?
Daniel S avatar
флаг ru
Я не знаю никаких конструкций для (несуперсингулярных) бинарных кривых с необычно низкой степенью вложения.Существуют конструкции для троичных кривых со степенью вложения 6 (см. Харрисон, Пейдж и Смарт «Программная реализация конечных полей характеристики три для использования в криптосистемах на основе пар»), НО ТАКИЕ КРИВЫЕ НЕ ПОДХОДЯТ ДЛЯ КРИПТОГРАФИИ из-за недавних атак на дискретные журналы в небольших полях характеристик по Granger, Joux et al.

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

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