Криптографический анализ аналога схемы Диффи–Хеллмана, использующего сопряжение и возведение в степень, на матричной платформе

Доказано, что смешанный обобщённый вариант протокола Диффи–Хеллмана на матричной платформе, использующий одновременное возведение в степень и сопряжение фиксированной матрицы, в генерическом случае допускает вычисление разделённого ключа за полиномиальное время, если соответствующая кратная задача дискретного логарифма решается за полиномиальное время. Алгоритм вычисления использует разработанный автором метод линейного разложения, позволяющий находить разделённый ключ без решения задачи поиска сопрягающих элементов, и подход Менезеса с соавт., сводящий вычисление степени матрицы к решению кратной задачи дискретного логарифма. Комбинация этих двух подходов не может использоваться напрямую. Доказательство основного утверждения требует анализа содержаний мономиальных матриц в смежных классах по перестановочным подгруппам группы матриц. Это, в свою очередь, требует изучения аналогичного вопроса для групп подстановок. Последнее облегчается тем, что имеется ряд известных утверждений на эту тему.