RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и анализ // Архив

Алгебра и анализ, 2008, том 20, выпуск 6, страницы 119–147 (Mi aa542)

Эта публикация цитируется в 4 статьях

Статьи

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

Д. Ю. Григорьевa, А. Кожевниковb, С. И. Николенкоb

a IRMAR, Université de Rennes, Rennes, France
b С.-Петербургское отделение Математического института им. В. А. Стеклова РАН

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

MSC: 94A60, 68P25, 11T71


 Англоязычная версия: St. Petersburg Mathematical Journal, 2009, 20:6, 937–953

Реферативные базы данных:


© МИАН, 2024