№13 - Бесконечные группы и алгоритмические проблемы. Алгебраическое шифрование

Алгебраическое шифрование

Сравнительно недавно (лет 15 назад) появилось новое направление в криптографии, при котором в качестве платформы шифрования используют бесконечные некоммутативные группы (Group-based cryptography). Очень важен выбор класса абстрактных групп, используемых в качестве платформы. Ясно, что группы должны быть наделены каноническими формами записи и элементов, кроме того процесс переписки произвольного элемента, записанного в виде группового слова от порождающих элементов в каноническую форму должен быть эффективным.

Криптостойкость должна основываться на каких-то трудноразрешимых задачах в этих группах.

Бесконечные группы и алгоритмические проблемы

Рассмотрим постановку алгоритмических проблем для групп, хотя аналогих этих проблем можно сформулировать и для других алгебраических систем.

Пусть имеется теоретико-групповое свойство $P$, которое может относиться как к отдельным элементам, так и к наборам элементов, к погруппам или подмножествам групп или к различным группам.
Требуется определить, обладают ли свойством $P$ указанные объекты или нет, а именно: существует ли алгоритм, определяющий за конченое число шагов удовлетворяет ли объект $Q$ свойству $P$, или нет?

Говорят, что проблема алгоритмически разрешима, если такой алгоритм существует и не зрашеима в противном случае.

При постановке алгоритмической проблемы предполагается, что группа, её элементы, подгруппы, подмножества или другие объекты, для которых ставится проблема, заданны каким-либо эффективным образом.

Классические алгоритмические проблемы теории групп сфорулированы Максом Деном в начале прошлого столетия. Они ставились им для класса конечно определенных групп.

Это означает, что группа $G$, для которой ставится проблема, задана своим конечным представлением вида:

$(1) G=gp<x_{1},\dots,x_{n}|r_{1},\dots,r_{m}>$
($G$ изоморфна фактор-группе свободной группы по нормальной подгруппе порожденной элементами $r_{1},\dots,r_{n}$)

Классические алгоритмические поблемы Дена формулируются следующим образом:
1 - Проблема равенства. Определить по двум групповым словам от порождающих элементов, т.е. оределить по этим двум словам: $g=g(x_{1},\dots,x_{n})$ $f=f(x_{1},\dots,x_{n)}$ записывают ли они один и тот же элемент группы $G$, заданной своим конечным представлением $(1)$.
Другими словами верно ли, что в группе $G$ справедливо равенство $f=g$.
Рассмотрение проблемы равенства может быть сведено к случаю, когда один из элементов равен единице.
(как же это проверить? просто рассмотреть $g^{-1}f=1$)
Также это равенство может быть перенесено в группе $F_{n}$, поскольку равенство $g=1$ в группе $G$ равносильно тому, что слово $g(x_{1},\dots,x_{n})$ как элемент свободной группы $F_{n}$ принадлежит нормальной подгруппе $R=gp<r_{1},\dots r_{m}>$

Примеры конечно определенных групп с неразрешимой проблемой равенства были построены в 50-е годы прошлого столетия П.С. Новиковых.

2 - Проблема сопряженности. Определить, задают ли два групповых слова $g=g(x_{1},\dots,x_{n})$ и $f=f(x_{1},\dots,x_{n)}$ сопряженныеэлементы группы $G$. Другими словами, существует ли элементы $h \in G; hgh^{-1}=g^h=f$ .
Разрешимость проблемы сопряженности в группе $G$, влечет за собой разрешимость в $G$ проблемы равенства. Действительно $g \in G$ равен единице $\iff g$ сопряжен с $1$.
Обратное утверждение в общем случае неверно. Существуют конечно определенные группы, в которых проблема равенства разрешима, а проблема сопряженности неразрешима.

3 - Проблема вхождения. Определить для произвольного элемента $g$ данные конечно определенной группы $G$ и произвольной её конечно порожденной подгруппы $H$, принадлежит ли элемент $g$ подгруппе $H$, или нет. Проблема вхождения часто называют обобщенной проблемой равенства. Разрешимость проблемы вхождения влечет разрешимость проблемы равенства т.к. в качестве $H$ можно взять подгруппы, состоящую из одной единицы.