Асимметричные криптосистемы, основанные на кривых помимо эллиптических кривых

Криптография на эллиптических кривых (ECC) в последнее время набирает большую популярность из-за своей безопасности. Я склонен находить процесс кодирования открытого текста с использованием ECC особенно интересным, поэтому мне было интересно, было ли доказано/опровергнуто, что можно найти другие кривые, на основе которых можно создавать криптосистемы? Если доказано, что это так, то какие кривые?

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

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

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

Гиперэллиптическая кривая рода $г$ над конечным полем $\mathbb{F}_q$ можно описать уравнением вида $$ C: y^2 + h(x)y = f(x) $$ куда $ф(х)$ является унитарным полиномом степени $2г+1$, $ч(х)$ является полиномом степени не выше $г$ с некоторыми дополнительными условиями.

Эллиптические кривые можно рассматривать как гиперэллиптические кривые рода $г=1$, вы можете вспомнить, что эллиптическая кривая в форме Вейерштрасса задается выражением $ у ^ 2 = х ^ 3 + топор + б $, где вы видите, что степень полинома в $х$ действительно $2г +1 = 3$.

Здесь я хотел бы сосредоточиться на гиперэллиптических кривых рода $2$. В конце я объясню, почему этот конкретный случай является интересной альтернативой ECC. Если характеристика конечного поля $\mathbb{F}_q$ не является $2$, то ГЭК рода $2$ дается уравнением $$ y^2 = x^5 + b_4x^4 + b_3x^3 +b_2x^2 + b_1x + b_0, \quad b_i \in \mathbb{F}_q .$$ Есть ли у нас групповая структура относительно точек на кривой? Ответ - нет. Но грубо говоря, мы можем описать структуру группы, используя «пары точек» на кривой.

На приведенном выше рисунке синяя кривая — это уникальный кубик, проходящий через $P_1, P_2, Q_1, Q_2$ (определяется с помощью интерполяции).

Здесь вы можете задать себе следующие вопросы:

1. Что гарантирует, что прямая пересекает эллиптическую кривую в трех точках?
2. Сколько точек пересечения имеет прямая с гиперэллиптической кривой рода $2$?

Ответ кроется в теореме Безу для плоских алгебраических кривых. Чтобы понять групповую структуру, связанную с гиперэллиптическими кривыми (известную как якобиан гиперэллиптических кривых), вам также потребуется некоторое понимание алгебраической геометрии. Здесь является хорошей отправной точкой для гиперэллиптических кривых.

ГЭК рода $2$ наиболее интересны для криптографических приложений, основанных на задаче дискретного журнала, поскольку для кривых более высокого рода у вас есть атаки индексного исчисления, которые можно использовать для решения DLP.

Видеть Эта бумага для эффективной арифметики на HEC рода $2$.

В вопросе ложная посылка, то есть:

Произвольные кривые могут быть полезны в криптографии. Что я делаю из цитаты в вопросе:

доказано/опровергнуто, что можно найти другие кривые, на основе которых можно создавать криптосистемы

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

Так что теперь, если мы хотим показать, что неэллиптические кривые можно использовать в криптографии с открытым ключом, мы должны либо показать, что

1. они также образуют группу с не большей слабостью, чем ECC, или
2. они могут использоваться по-разному и допускают не худшую основу безопасности, чем ECC.

И в идеале они более эффективны, чем ECC.

Помимо эллиптических кривых, конические сечения (над подходящим конечным полем $\mathbb F_p$) также обеспечивают групповую структуру.

Поэтому их можно использовать при обмене ключами Диффи-Хеллмана. Обратите внимание, однако, что эти кривые не кажутся безопасными для использования в криптографии, поскольку проблема дискретного логарифма кажется легко решаемой в группе точек над этими кривыми. Как правило, DLP можно свести к основному полю.

Для конкретного примера: это бумага изучает кривую с уравнением $x^2 ​​- Dy^2 = 1$, для правильного выбора $Д$. другими словами, это множество решений этого уравнения над $\mathbb F_p$. Показано, что дискретный лог прост.