Квантовая информатика - раздел современной науки, в котором изучаются общие принципы квантовых систем и алгоритмов. Моделью квантовых систем является универсальный квантовый компьютер, который на сегодняшний день существует только гипотетически - предложены теоретические основы для его построения и реализованы квантовые компьютеры, способные выполнять фиксированную задачу. Кроме того, квантовые системы устроены гораздо сложнее классических систем, и на сегодняшний день существует много трудностей в их реализации, но, несмотря на это, интерес к квантовым системам не угасает. Это связано с тем, что квантовые системы обладают уникальными свойствами, позволяющими решать вычислительно сложные задачи.
В современном мире огромное количество информации передается по различным каналам связи. Для безопасной передачи данных используют различные криптографические протоколы и системы шифрования, криптостойкость которых основана на вычислительной сложности задач факторизации и дискретного логарифмирования. Благодаря алгоритму Шора эти задачи являются эффективно вычислимыми на квантовом компьютере. Шор в своей работе показал, что для квантовых систем задача факторизации имеет вычислительную сложность, схожую со сложностью обычного умножения, поэтому так велик интерес к квантовой информатике - реализация данного алгоритма полностью исключит возможность применения ряда классических криптографических протоколов. Этот факт побуждает разрабатывать новые алгоритмы шифрования, пригодные для квантовых компьютеров.
В классической криптографии для работы алгоритмов часто применяют хеширование информации - преобразование произвольной входной строки в строку бит фиксированной длины. В результате исследований в этой области было выявлено, что для большинства хеш-функций существуют коллизии - два разных сообщения имеют одинаковые хеш-значения. Совсем иначе обстоят дела в квантовой информатике, здесь разработаны собственные подходы для построения хеш-функций. Квантовое хеширование, основанное на постулатах квантовой механики, является физически односторонним, кроме того здесь не существует коллизий в классическом понимании. Однако существуют так называемые “квантовые коллизии”, связанные с вероятностной природой самих квантовых вычислений, в связи с чем и способы их разрешения также существенно отличаются от классических.
В данной работе будет исследована криптоустойчивость квантового хеширования для циклической группы и разработаны методы повышения его устойчивости к квантовым коллизиям. Поскольку минимизация коллизий при квантовом хешировании связана с некоторой задачей оптимизации относительно числовых параметров данной функции, будут рассмотрены различные методы построения множества параметров квантового хеширования и проведен сравнительный анализ данных алгоритмов.
В работе была исследована криптоустойчивость квантового хеширования для циклической группы и разработаны методы повышения его устойчивости к квантовым коллизиям. Поскольку минимизация коллизий при квантовом хешировании связана с задачей оптимизации некоторой целевой функции, были рассмотрены различные методы построения множества параметров, гарантирующих 5-устойчивость к коллизиям квантового хеширования, и проведен сравнительный анализ данных алгоритмов.
В результате эксперимента установлено, точность вычислений эвристических методов значительно выше точности конструктивного алгоритма, но, в силу экспоненциальной сложности, они неприменимы при большой размерности задачи. Конструктивный алгоритм не требует сложных вычислений и мгновенно находит решения при любых условиях, отсюда можно сделать вывод, что применение конструктивного построения эффективно только при больших значениях входных параметров.
Также в рамках данной работы был проведен подробный анализ эвристических алгоритмов, в результате которого было установлено, при каких значениях d (d< 1024) эффективнее применять тот или иной эвристический метод построения параметров квантового хеширования.
