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