О нестойкости двух симметричных гомоморфных криптосистем, основанных на системе остаточных классов

Одной из наиболее актуальных задач, связанных с защитой облачных вычислений, является анализ криптостойкости гомоморфных шифров. Данная статья посвящена изучению вопроса о защищенности двух недавно предложенных гомоморфных криптосистем, которые, в связи с их высокой вычислительной эффективностью, могут быть использованы для шифрования данных на облачных серверах. Обе криптосистемы основаны на системах остаточных классов, что позволяет рассмотреть их с единых позиций. Именно использование систем остаточных классов делает применение этих криптосистем в реальных приложениях заманчивым с точки зрения эффективности по сравнению с другими гомоморфными шифрами, так как появляется возможность легко распараллелить вычисления. Однако их криптостойкость не была в достаточной мере изучена в литературе и нуждается в анализе.
Отметим, что ранее предшественниками была рассмотрена криптосистема похожая на один из шифров, криптостойкость которого исследуется. Была предложена идея адаптивной атаки по выбранным открытым текстам на эту конструкцию и дана оценка необходимого для раскрытия ключа количества пар «открытый текст, шифртекст». Здесь проводится анализ этой атаки и показываем, что иногда она может работать некорректно. Также описывается более общий алгоритм атаки с известными открытыми текстами. Приводятся теоретические оценки вероятности успешного раскрытия секретного ключа с его помощью и практические оценки этой вероятности, полученные в ходе вычислительного эксперимента.
Защищенность второй криптосистемы не была исследована ранее в литературе. Изучена её стойкость к атаке с известными открытыми текстами. Проанализирована зависимость необходимого для взлома количества пар «открытый текст, шифртекст» от параметров криптосистемы и даны рекомендации, которые могут помочь улучшить криптостойкость.
Итог проведенного анализа заключается в том, что обе криптосистемы являются уязвимыми к атаке с известными открытыми текстами. Поэтому использовать их для шифрования конфиденциальных данных может быть небезопасно.
Основным алгоритмом, используемым в предложенных атаках на криптосистемы, является алгоритм поиска наибольшего общего делителя. Как следствие, время, необходимое для реализации атак, является полиномиальным от размера входных данных.