Атака на восстановление квантового ключа. Никита Шахулов
Читать онлайн книгу.
внимания. Однако существующие квантовые атаки на легкие блочные шифры сосредоточены только на квантовом исчерпывающем поиске, в то время как квантовые атаки в сочетании с классическими методами криптоанализа изучены недостаточно. В этой статье мы изучим атаку квантового восстановления ключа на SIMON32 / 64 с использованием алгоритма квантового амплитудного усиления в модели Q1. Сначала я повторно проанализирую сложность квантовой схемы квантового исчерпывающего поиска на SIMON32 / 64. Я более точно оценю количество ворот Клиффорда и уменьшаем количество Т-ворот. Кроме того, T-образная и полная глубина уменьшены из-за наших незначительных изменений. Затем, используя в качестве отличителя четыре дифференциала, данные Бирюковым в FSE 2014, я проверю атаку восстановления квантового ключа на 19-раундовой SIMON32 / 64. Я рассматриваю две фазы атаки восстановления ключа как два экземпляра QAA по отдельности, а первый экземпляр QAA состоит из четырех экземпляров sub-QAA. Затем я проектирую квантовую схему этих двух экземпляров QAA и оцениваю соответствующую им сложность квантовой схемы. Я пришёл к выводу, что квантовая схема моей атаки с квантовым восстановлением ключа ниже, чем квантовый исчерпывающий поиск. Моя работа в первую очередь изучает квантовую специализированную атаку на SIMON32 / 64. И это первая работа по изучению сложности квантовых специализированных атак с точки зрения сложности квантовых схем, которая представляет собой более детальный анализ сложности квантовых специализированных атак. Я проектирую квантовую схему этих двух экземпляров QAA и оцениваю соответствующую им сложность квантовой схемы. Я пришёл к выводу, что квантовая схема моей атаки с квантовым восстановлением ключа ниже, чем квантовый исчерпывающий поиск. Моя работа в первую очередь изучает квантовую специализированную атаку на SIMON32 / 64. И это первая работа по изучению сложности квантовых специализированных атак с точки зрения сложности квантовых схем, которая представляет собой более детальный анализ сложности квантовых специализированных атак. мы проектируем квантовую схему этих двух экземпляров QAA и оцениваем соответствующую им сложность квантовой схемы. Я пришёл к выводу, что квантовая схема моей атаки с квантовым восстановлением ключа ниже, чем квантовый исчерпывающий поиск. Моя работа в первую очередь изучает квантовую специализированную атаку на SIMON32 / 64. И это первая работа по изучению сложности квантовых специализированных атак с точки зрения сложности квантовых схем, которая представляет собой более детальный анализ сложности квантовых специализированных атак.
Ключевые слова: Квантовый криптоанализ, Легкие блочные шифры, Квантовое усиление амплитуды, Дифференциальный криптоанализ, Атака восстановления ключа, SIMON32 / 64
Вступление
Развитие квантовых вычислений представляет угрозу для классических криптосистем. Алгоритм Шора (Shor1994 г.) может нарушить безопасность криптосистем с открытым ключом, основанных на целочисленной факторизации и дискретном логарифме, что приводит к постквантовой криптографии. Что касается симметричных криптосистем, до алгоритма Саймона (Simon1997 г.) применяется в квантовом криптоанализе, есть только алгоритм Гровера (Grover 1997 г.), что помогает получить квадратичное ускорение.
Квантовому криптоанализу блочных шифров в последние годы уделяется много внимания. Следуя представлениям о
Безопасность PRF в квантовых условиях, предложенная Zhandry et al. (Жандры2012 г.), в квантовом криптоанализе существуют две модели защиты от блочных шифров, которые Каплан и др. назвали моделью Q1 и моделью Q2. в (Kaplan et al.2016b).
Модель Q1: Злоумышленнику разрешено только выполнять классические онлайн-запросы и выполнять квантовые автономные вычисления.
Модель Q2: Злоумышленник может выполнять квантовые вычисления в автономном режиме и делать запросы квантовой суперпозиции в режиме онлайн. То есть злоумышленник может запросить оракулу в состоянии суперпозиции и получить состояние суперпозиции в качестве результата запроса.
Мы можем заметить, что модель Q1 более реалистична, чем модель Q2, по той причине, что оракул должен разрешить доступ к суперпозиции. Тем не менее, по-прежнему имеет смысл изучить модель Q2, чтобы подготовиться к будущему с высокоразвитой технологией квантовой связи.
Фактически, квантовый криптоанализ в модели Q2 существует уже давно. В 2010 году Кувакадо и Мори построили квантовый различитель на 3-круговой структуре Фейстеля (Kuwakado and Morii2010 г.) с использованием алгоритма Саймона в модели Q2. Затем они также восстановили ключ Even-Mansour, также используя алгоритм Саймона в 2012 году (Kuwakado and Morii2012 г.). На Crypto2016 Каплан и др. расширили результат в (Kuwakado and Morii2010 г.; 2012 г.) и применил алгоритм Саймона для атаки на ряд режимов шифрования и аутентифицированного шифрования, таких как CBC-MAC, PMAC, OCB (Kaplan et al. 2016a). В модели Q2 алгоритм Саймона может быть объединен с алгоритмом Гровера для применения в квантовом криптоанализе против блочных шифров. Леандер и Мэй (2017 г.) впервые использовал эту идею для атаки на FX-конструкцию в модели Q2. Вдохновленные этой работой, Донг и др. (2020a) дала атаку квантового восстановления ключа на полный цикл ГОСТ также в модели Q2. Кроме того, алгоритм Бернштейна-Вазарани (BV) (Bernstein and Vazirani1997 г.)