Атака на восстановление квантового ключа. Никита Шахулов

атака на SIMON описана в Anand et al. (2020c), где Ананд и др. представить квантовую схему алгоритма Гровера на вариантах SIMON и дать соответствующую оценку квантовых ресурсов, которая является общей квантовой атакой. Для дальнейшего изучения квантовой безопасности SIMON нам необходимо изучить специальные квантовые атаки SIMON. Примечательно, что при измерении сложности атаки все существующие квантовые специализированные атаки изучали сложность шифрования, в то время как в нашем исследовании мы впервые использовали стоимость ресурсов квантовой схемы в качестве меры сложности.

      Модель атаки Мы рассматриваем атаку выбранного открытого текста на SIMON32 / 64 в модели Q1, где злоумышленник может делать классические онлайн-запросы оракула шифрования и может выбирать пары случайных сообщений с входным дифференциалом x. Чтобы осуществить такую атаку, противнику необходимо осуществить трансформацию:

      qq

      язнак равно1 я= 1

      q

      → | mi |E |

      я= 1

      когда задано q пар классической пары открытый текст-зашифрованный текст в качестве входных данных. Мы полагаем, что этот процесс эффективен. Таким образом, мы можем игнорировать стоимость квантовых ресурсов этого процесса.

      Мой вклад В этой статье я изучаю атаку квантового восстановления ключа на SIMON32 / 64 с использованием квантового амплитудного усиления (QAA) в модели Q1. Наш вклад можно резюмировать в следующих двух аспектах.

      – Я повторно анализирую сложность квантовой схемы квантового поиска мастер-ключа на SIMON32 / 64. С одной стороны, я далаю более точный результат оценки количества ворот Клиффорда и уменьшенного количества ворот Т. Я уменьшаю количество операций процесса расширения ключа, что снижает количество вентилей NOT и CNOT. Кроме того, подсчет ворот Клиффорда, разложенных по воротам Тоффоли, на общее количество ворот Клиффорда, помог мне дать более точную оценку количества ворот Клиффорда. И я уменьшаю количество Т-вентилей, используя декомпозицию мультиуправляемых вентилей НЕ на вспомогательные кубиты. С другой стороны, я даю более тщательный анализ глубины схем. Глубина, на которой я здесь обращаю внимание, – это глубина таких квантовых схем, которые состоят только из вентилей Клиффорда + Т. Вносим некоторые модификации в код реализации SIMON32 / 64, что уменьшает Tdepth и полную глубину контуров. По сравнению с (Анандом

      и другие. 2020c), я даю более точный и тщательный анализ сложности квантовой схемы QMKS.

      – Я представляю мою атаку с квантовым циклическим восстановлением ключа на SIMON32 / 64 с 19 этапами в сочетании с CRKR в

      (Бирюков и др. 2014 г.). Я рассматриваю фазу частичного угадывания ключа и фазу исчерпывающего поиска как два экземпляра QAA по отдельности и проектируем соответствующую квантовую схему. Первый экземпляр QAA включает в себя четыре экземпляра суб-QAA, соответствующих четырем процессам восстановления ключа с использованием четырех дифференциалов. Затем оценим