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

За последнее десятилетие исследованиям легковесных блочных шифров было уделено много внимания. Исследователи предложили несколько легких примитивов, чтобы назвать некоторые из них, SIMON (Beaulieu et al.2015 г.), SPECK (Beaulieu et al. 2015 г.), СКИННИ (Beierle et al. 2016 г.), НАСТОЯЩЕЕ (Богданов и др. 2007 г.). Чтобы подготовиться к будущему с крупномасштабными квантовыми компьютерами, необходимо изучить квантовую безопасность легких блочных шифров. Было предпринято несколько попыток изучить общие квантовые атаки на некоторые легкие блочные шифры (Anand et al.2020c; Jang et al.2020 г.; Ананд и др.2020b). В этой статье мы сосредоточимся на квантовой безопасности SIMON. Семейство алгоритмов SIMON (Beaulieu et al.2015 г.) – это легкий блочный шифр, предложенный NSA в 2013 году и обладающий выдающейся производительностью аппаратной реализации. В классической обстановке было много специализированных атак, направленных на SIMON. Однако в квантовой ситуации единственная квантовая атака на 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, соответствующих четырем процессам восстановления ключа с использованием четырех дифференциалов. Затем оценим

Текст предоставлен ООО «ЛитРес».

Прочитайте эту книгу целиком, на ЛитРес.

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.