Алгебраическая криптография: новые конструкции и их надёжность относительно доказуемого взлома

Известно не так уж много схем криптографических примитивов, основанных на идеях некоммутативной алгебры. Каждая новая схема представляет существенный интерес, поскольку для неабелевых конструкций многие стандартные атаки не работают. С другой стороны, в криптографии не известны доказательства надёжности, которые бы позволяли транслировать надёжность того или иного примитива в утверждения о сложностных классах. Поэтому представляют интерес исследования более слабых понятий надёжности.
В этой работе мы представляем новые конструкции криптографических примитивов на основе теории инвариантов групп и предлагаем возможные варианты их усложнения для практического применения. Кроме того, введено новое понятие взлома с доказательством, представляющее собой ослабленную версию обычного криптографического взлома, в котором взломщик должен представить доказательство того, что он действительно правильно расшифровал сообщение. Доказано, что криптосистемы, основанные на инвариантах матричных групп, а также вариант протокола согласования ключа Аншель–Аншеля–Голдфельда для модулярных групп, являются устойчивыми относительно взлома с доказательством, если $\mathrm{NP}\not\subseteq\mathrm{RP}$.