Развитие современной криптографии и исследования по квантовой криптографии

Масаюки Абэ

Аннотация

Основа современной криптографии, разработанная в 1976 году, рассматривала безопасность путем моделирования противников как полиномиальных машин Тьюринга. Однако последние достижения в разработке универсального квантового компьютера оказали значительное влияние на современную криптографию, потому что они опровергают модель безопасности. Исследования NTT в области криптографии направлены на предоставление технологий для обеспечения безопасности современных информационных систем и создания приложений, когда квантовые компьютеры станут распространенными. В этой статье рассматриваются 40 лет криптологических исследований в NTT и описываются наши текущие усилия.

Ключевые слова: основы криптографии, постквантовая криптография, квантовая криптография.

1. Криптографические исследования в NTT

Исследования NTT по криптографии, которые начались в 1982 году с инцидента с подделкой банковских карт с участием сотрудника Nippon Telegraph и Telephone Public Corporation, продолжаются более 40 лет. В 1992 году исследовательская группа по криптографии, которая изначально включала только трех участников, стала официальной исследовательской группой из восьми участников в рамках лабораторий информационных и коммуникационных сетей. Вместе с появлением веб-браузера Mosaic в 1993 году Интернет взорвался, что привело к признанию важности информационной безопасности. В ответ на эти события группа была реорганизована в Проект Информационной Безопасности в 1999 году, а затем в NTT Secure Platform Laboratories в 2012 году. Сегодня технологии информационной безопасности стали товаром массового спроса, поддерживающим повседневную жизнь. Теперь известная как NTT Social Informatics Laboratories, исследовательская группа продолжает заниматься широким спектром исследований по криптографии и информационной безопасности.

Передовые сети позволили функционировать различным системам распространения информации. Сфера криптографии расширилась от базовой оборонительной позиции, сосредоточенной на сокрытии и аутентификации, до наступательной позиции создания приложений для криптовалюты, облачных вычислений и других новых областей. С возросшей вероятностью достижения универсальных квантовых компьютеров также стало ясно, что используемые в настоящее время системы шифрования с открытым ключом будут быстро скомпрометированы. Следовательно, теперь необходимы новые меры для оборонных целей. Создание криптографических приложений, которые активно используют универсальные квантовые компьютеры, и установление фундаментальных теорий, лежащих в их основе, вероятно, станут реальностью.

В этой статье обсуждается современная криптография, в которой как пользователи системы, так и атакующие используют доступные в настоящее время классические компьютеры; квантово-устойчивая криптография, в которой только атакующие используют квантовые компьютеры; и квантовая криптография, в которой и пользователи, и атакующие используют квантовые компьютеры (Рис. 1). Предоставлен обзор тем, в основном связанных с криптографией с открытым ключом, и их связи с исследованиями криптографической теории NTT. Другая важная тема исследований, симметричная криптография, обсуждается с точки зрения квантово-устойчивой криптографии.

2. Достижения современной криптографии

Рис. 1. Развитие от современной к квантовой криптографии.

Безопасные и эффективные криптографические схемы строятся на основе вычислительных предположений, что в среднем трудно решить определенный класс проблем с вероятностной машиной Тьюринга. Однако, поскольку алгоритмы и аппаратное обеспечение, доступные противникам, становятся более продвинутыми, отдельные проблемы можно решить за меньшее время, чем раньше. Когда это происходит, криптографические схемы, основанные на этом классе проблем, потребуют больших ключей для безопасности, таким образом, ухудшая производительность. Шифрование Ривеста--Шамира--Эдлмана (RSA) в 1977 году, шифрование Рабина в 1978 году и система ESIGN (Efficient Digital Signature), разработанная NTT в 1990 году, используют сложность проблемы факторизации простых чисел. Открытый ключ RSA считался безопасным при 512 битах во время его разработки, но сейчас рекомендуется не менее 3072 бит [1]. Обмен ключами Диффи--Хеллмана в 1976 году, шифрование Эль-Гамаля в 1985 году и подпись DSA (Digital Signature Algorithm) в 1993 году, которые также являются новаторскими криптографическими техниками, изначально были построены с использованием проблемы дискретного логарифма над мультипликативными группами, но перешли в реализации, основанные на проблеме дискретного логарифма на эллиптических кривых (такие как подпись ECDSA (Elliptic Curve Digital Signature Algorithm) в 2005 году), что позволяет использовать меньший открытый ключ при том же уровне безопасности.

По мере развития сетей появились передовые криптографические приложения, такие как облачные вычисления. Криптография эволюционировала от технологий для традиционных целей, таких как сокрытие информации и аутентификация, до более ценных технологий для построения продвинутых сервисов обмена информацией. Билинейное отображение (спаривание) над группами эллиптических кривых было впервые использовано для безопасной генерации ключей Калиски-младшим в 1987 году. Оно стало широко известным благодаря анализу безопасности криптографии на эллиптических кривых (MOV (Менезес--Окамото--Ванстон) редукция) Тацуаки Окамото из NTT и со-исследователей в 1991 году. С тех пор оно широко использовалось для криптографии в ID-базированном обмене ключами (Огиши и др., 2000) и ID-базированной криптографии (Бонех и др., 2001), и породило множество практических приложений на сегодняшний день. В частности, неинтерактивные доказательства с нулевым разглашением, практическая ценность которых была ограничена до того времени, быстро расширились с конструкциями на основе спариваний (Грот и др., 2008). В NTT также прогрессируют исследования по структура-сохраняющей криптографии (Абэ и др., 2009), которая позволяет расширенные функции путем свободного комбинирования криптографических схем над группами спаривания. Технология спаривания внесла значительный вклад в реализацию передовой концепции вычислительно звукового доказательства (Микали, 2000), которая позволяет эффективно проверять сложные утверждения с коротким доказательством, в форме Zero-Knowledge Succinct Non-interactive Argument of Knowledge (zk-SNARK) (Геннаро и др., 2012). Поскольку короткие доказательства highly demanded в приложениях блокчейна, zk-SNARK, кажется, станет фундаментальной технологией для эры Web3. Его полезность быстро улучшается с разработкой фронтенд-компиляторов, которые переводят утверждения на языках высокого уровня, таких как C++, в NP-полный (недетерминированное полиномиальное время) промежуточный язык, который бэкенд zk-SNARK может обрабатывать.

С развертыванием криптографии в различных информационных системах и усовершенствованием функциональности криптографии, понятие безопасности также стало более изощренным. Доказательства, основанные на относительно простых понятиях безопасности, таких как неразличимость, обычно демонстрировались простой редукцией к предположению о сложности; это включает генератор псевдослучайных чисел Блюма--Микали, основанный на проблеме дискретного логарифма в 1982 году, и шифрование Рабина, основанное на проблеме факторизации целых чисел в 1986 году. Более высокие уровни безопасности усложнили доказательства безопасности и конструкции. В хорошоизвестном понятии безопасности неразличимости против адаптивных атак на шифротекст по выбору (IND-CCA) безопасность (Белларе и Рогвей, 1991), противнику разрешается более активно участвовать во вводе и выводе криптосистем. Парадигма случайного оракула, введенная Белларе и др. в 1993 году, которая идеализировала хэш-функции, внесла значительный вклад в упрощение конструкции и доказательств безопасности. Различные схемы шифрования и приложения, продемонстрированные как безопасные в модели случайного оракула, были предложены с конца 1990-х до 200-х годов, что привело к распространению парадигмы доказуемой безопасности. В NTT, преобразование Фудзисаки--Окамото (FO) в 1998 году, PSEC-KEM (Provably Secure Elliptic Curve encryption with Key Encapsulation Mechanism) в 1999 году, и схема подписи с восстановлением сообщения ECAOS (Elliptic Curve Abe--Okamoto--Suzuki signature) в 2008 году были разработаны в модели случайного оракула. Однако многие исследования были проведены для поиска эффективных, доказуемо безопасных конструкций, которые не полагаются на случайные оракулы.

Криптографические техники, разработанные для сегодняшних компьютеров и сетей, будут продолжать передаваться как основы, обеспечивая понимание построения безопасной криптографии даже в пост-квантовом компьютерном мире, как обсуждается ниже.

3. От современной криптографии к постквантовой криптографии

Полагают, что пройдет considerable amount of time, прежде чем противники смогут использовать универсальные квантовые компьютеры. Однако, поскольку большая часть present информации в обращении собирается и накапливается, криптографические технологии, развертываемые сейчас, должны выдерживать будущие атаки с использованием универсальных квантовых компьютеров, чтобы обеспечить конфиденциальность накопленной информации. Проблемы на основе решеток являются перспективными в качестве базовых предположений о сложности, используемых при построении пост-квантово безопасной криптографии. Использование проблемы решетки в криптографии началось с построения односторонней функции Айтаи в 1996 году. Впоследствии, основанное на решетках, конкретно эффективное N-степенное шифрование Усеченных полиномиальных Колец (NTRU) было предложено в 1998 году. Для цифровых подписей, конструкции на основе многомерных полиномов и хэш-функций также являются перспективными вариантами для достижения постквантовой безопасности.

В Конкурсе Пост-Квантовой Криптографии (PQC), запущенном Национальным институтом стандартов и технологий США (NIST) в 2017 году, были сделаны открытые призывы квантово-компьютерно-безопасных систем шифрования с открытым ключом и цифровых подписей, и финальные кандидаты были объявлены в 2022 году. Это означает, что постквантовая криптография быстро приближается к практическому применению. Она станет новым стандартом к 2024 году и ожидается, что заменит текущие к 2030 году. NTT внесла вклад в конкурс как сторонник шифрования NTRU и в оценку многих кандидатов. Поскольку квантовые компьютеры могут работать над суперпозиционными состояниями, и вычислительные принципы противников отличаются, техники для доказательств безопасности были перестроены для соответствия квантовым компьютерам. Вышеупомянутое FO преобразование также было пересмотрено так, чтобы безопасность могла быть установлена в квантовой модели случайного оракула, которая выполняет вычисления в квантовом состоянии. FO преобразование используется для того, чтобы сделать CRYSTALS-Kyber, криптографическую схему, принятую в конкурсе NIST PQC, IND-CCA безопасной.

Криптография на основе решеток является фундаментальной для разработки передовых криптосистем, помимо being квантово-безопасной. Полностью гомоморфное шифрование, которое позволяет выполнять сложение и умножение на зашифрованном открытом тексте, является essential криптографической техникой с широким спектром приложений, включая облачные вычисления. NTT занималась анализом безопасности криптографии на основе решеток и исследованиями полностью гомоморфного шифрования с 2013 года.

Удваивая или утраивая длину ключа и размер блока, симметричная криптография, такая как блочные шифры и хэш-функции, может быть защищена от атак поиска ключа, которые используют универсальные квантовые алгоритмы независимо от их внутренних структур. Таким образом, в отличие от криптографии с открытым ключом, основанной на теоретико-числовых предположениях, считается, что они невосприимчивы к фатальным последствиям таких атак. Атаки квантовых компьютеров также представляют новый риск для симметричной криптографии, потому что было показано, что они эффективны против specific хорошоизвестных структур. Тематическая статья в этом выпуске под названием "Security of Hash Functions against Attacks Using Quantum Computers" [2] объясняет безопасность хэш-функций против атак с использованием квантовых компьютеров, в частности, квантовую устойчивость SHA2.

Хотя исследования по постквантовым доказательствам с нулевым разглашением и криптографическим протоколам также продвигаются, необходимые дальнейшие исследования для своевременной замены текущих технологий. Например, в анонимном электронном голосовании, размер одного голоса в традиционной классической криптографии расширится с нескольких килобайт до нескольких сотен килобайт в квантово-безопасных системах голосования. Эти технологии essential для перехода к квантово-устойчивой безопасности систем распространения информации, основанных на текущих технологиях шифрования, и ожидается, что они разовьются на ранней стадии.

4. На пути к квантовой криптографии

Значительное увеличение вычислительной мощности периферийных устройств сделало возможным variety приложений. Когда квантовые компьютеры будут широко использоваться не только противниками, но и обычными пользователями, какие технологии и приложения будут возможны? Квантовый физик Стивен Виснер описал идею применения потери квантовых состояний при наблюдении для создания неподделываемых квантовых денег в 1969 году. (Текущая защита от подделки криптовалют и электронных денег полагается на онлайн-верификацию реестрами транзакций, последующее обнаружение с помощью криптографии, или устойчивость к взлому в доверенной среде выполнения.) Хотя текущие цифровые технологии могут доказать, что информация сохранена, они не могут доказать, что она была удалена. Это делает утилизацию информации неопределенной и создает риск утечки информации. Тематическая статья под названием "Functional Encryption Enabling Secure Leasing of Private Keys" [3] представляет исследование для доказательства того, что криптографические закрытые ключи были удалены. Теперь, когда квантовые компьютеры стали общей темой, не только ищутся новые приложения, но и проводятся исследования по интеграции квантовой физики, квантовой обработки информации и криптографии с целью установления основных теорий. Тематическая статья под названием "Quantum Algorithms with Potential for New Applications" [4] представляет исследование, демонстрирующее квантовое превосходство, т.е., как вычислительная мощность квантовых компьютеров превосходит текущие компьютеры для определенных задач.

5. Заключение

В этой статье был представлен обзор исследований NTT по криптографии с точки зрения развития квантовых компьютеров. NTT Social Informatics Laboratories будет продолжать проводить исследования по variety тем, от основ криптографии, которые будут продолжать быть важными как основа информационного обмена, до захватывающих приложений в далеком будущем. В дальнейшем мы будено продолжать развертывать технологии, которые будут способствовать распространению информации в настоящем, а также в будущем.

Ссылки

1. Cryptography Research and Evaluation Committees, "CRYPTREC Ciphers List," https://www.cryptrec.go.jp/en/list.html

2. A. Hosoyamada, "Security of Hash Functions against Attacks Using Quantum Computers," NTT Technical Review, Vol. 21, No. 7, pp. 43--47, July 2023. https://ntt-review.jp/archive/ntttechnical.php?contents=ntr202307fa4.html

3. R. Nishimaki, "Functional Encryption Enabling Secure Leasing of Private Keys," NTT Technical Review, Vol. 21, No. 7, pp. 33--37, July 2023. https://ntt-review.jp/archive/ntttechnical.php?contents=ntr202307fa2.html

4. T. Yamakawa, "Quantum Algorithms with Potential for New Applications," NTT Technical Review, Vol. 21, No. 7, pp. 38--42, July 2023. https://ntt-review.jp/archive/ntttechnical.php?contents=ntr202307fa3.html