Многомерная криптография или многомерная криптография открытого ключа — это общий термин, описывающий асимметричные криптографические схемы, построенные на решениях уравнений, основанных на многомерных полиномах над конечным полем .
Безопасность многомерной криптографии основывается на предположении, что решения системы квадратичных многочленов над конечным полем , в общем случае, является NP-полной задачей в сильном смысле или просто NP-полной. Вот почему эти схемы часто считаются хорошими кандидатами для постквантовой криптографии. [1]
Первая попытка построения криптографической схемы на основе многомерных квадратичных полиномов была сделана Онгом, Шнором и Шамиром [2], где они предлагали схему подписи, основанную на сложности решения уравнения: ;
Однако безопасность этой схемы по-прежнему основана на сложности факторизации и поэтому эта схема неустойчива к атакам при помощи квантовых компьютеров. Разработка многомерных криптографических схем в современном смысле началась в 1988 году со схемы С* Системы Матцумото-Имаи[3].
Мацумото и Имаи использовали биективное отображение над степенью полем расширения из формы:
.
Чтобы убедиться, что это преобразование обратимо, необходимо выбрать таким образом, что . Уравнение выше даёт, благодаря каноническому изоморфизму между и векторным пространством систему многомерных квадратичных уравнений на полем , объясняется это Эндоморфизмом Фробениуса. Для того чтобы спрятать структуру Мацумото и Имай использовали два аффинных преобразования и . Таким образом, они представили открытый ключ в форме:
.
Эта конструкция называемая биполярной. Она по-прежнему является стандартным методом построения многомерных криптосистем с открытым ключом. [4]
Многомерная криптография была активной областью исследований, однако, до сих пор отсутствуют многомерные схемы, такие как: протоколы обмена ключами и схемы подписи со специальными свойствами[5].
Достижения в области теории чисел привели к снижению эффективности вычислений, поэтому размеры параметров должны быть увеличены в соответствии с требованиями безопасности.[1]
Если можно построить достаточно большие квантовые компьютеры, алгоритм Шора сделает текущие системы полностью небезопасными. Поэтому важно искать альтернативные системы, которые способствуют эффективной и безопасной связи.[1]
Многомерная криптография с открытым ключом — одна из возможных альтернатив нынешних реализаций алгоритмов шифрования с открытым ключом. В 2003 году система подписи Sflash стала окончательным выбором проекта NESSIE (Новые европейские схемы подписи, целостности и шифрования) [7]. Первая книга о многомерной криптографии, написанная Дингом, Гауэром и Шмидтом, была опубликована в 2006 году [5]. Существует также международный воркшоп, PQCrypto, который посвящен вопросам постквантовой криптографии, в том числе многомерной криптографии.[8]
Основной идеей стандартного построения многомерной криптографии является выбор системы (центральное преобразование) из многомерных квадратичных многочленов от переменных, которые могут быть легко инвертированы. [9] После этого выбираются два случайных аффинных обратимых преобразования и для того, чтобы скрыть структуру центрального преобразования в открытом ключе.
[10]
Открытый ключ криптосистемы — составное квадратичное преобразование , которое, как предполагается, вряд ли отличается от случайного и поэтому его трудно инвертировать.
Закрытый ключ состоит из , , и следовательно, это позволяет инвертировать .
Чтобы зашифровать сообщение или необходимо вычислить . Шифротекст полученного сообщения есть или . [6]
Расшифрование
Что бы расшифровать шифротекст рекурсивно вычисляется: , и .
— это открытый текст шифротекста . Так как , то отображение из в , а следовательно, и результирующий открытый текст являются уникальными. [6]
Или другими словами, если дан шифротекст , необходимо найти такой, что
.
Обычно является инъекцией в криптографических системах, поэтому дешифровка выполняется при помощи вычисления .
Цифровая подпись
Для того, что бы подписать документ , используется хеш-функция для вычисления значения .
Затем необходимо вычислить , и . Здесь означает один, возможно, много прообраз для центрального отображения . Так как , то такое отображение существует. Таким образом каждое сообщение может быть подписано.
[6]
Проверка цифровой подписи
Чтобы проверить подлинность документа, необходимо просто вычислить и значение хеш-функции от документа. Если , то подпись принимается, в противном случае отклоняется. [6]
Безопасность алгоритмов многомерной криптографии опирается на следующее:
Сложность решения квадратичных многомерных систем уравнений над конечными полями.
Дана система из нелинейных полиномиальных уравнений с переменными . Необходимо найти значения такие, что .
Решение случайной многомерной квадратичной системы над конечным полем является NP-полной задачей в сильном смысле или просто NP-полной. Сложность решения этой задачи препятствует злоумышленику вычислить закрытый ключ, зная открытый ключ.
[11]
Патарин и соавторы показали, что трудность решения этой проблемы по крайней мере такая же, как и изоморфизм графов[13]
Скорость
Системы, построенные на алгоритмах многомерной криптографии достаточно быстры, особенно для подписи документов. Есть много предпосылок, что они могут быть быстрее, чем классические криптографические схемы с открытыми ключами, например RSA. [14][15]
Скромные требования к вычислительным ресурсам
Математические операции, выполняемые многомерными схемами, обычно очень просты: большинству схем требуется только сложение и умножение по небольшим конечным полям. Поэтому многомерные схемы требуют скромных вычислительных ресурсов, что делает их привлекательными для использования на недорогих устройствах, таких как RFID чипы и смарт-карты, без необходимости наличия криптографического сопроцессора.
Вариант схемы С*, называемый SFLASH, был предложен Европейской комиссией в качестве стандарта для схем подписи на недорогих устройствах.
[16][17]
В системе SFLASH [1] используется конечное поле также определяется отображение . Обозначение указывает, что уравнений были удалены из функции , которая построена следующим образом: . Здесь и — два обратимых линейных преобразования. Функция имеет вид:.
Таким образом, открытый ключ состоит из квадратичных полиномов c переменными коэффициентами в . Каждый квадратичный полином будет иметь коэффициентов. Для этого требуется КБ памяти, если каждый коэффициент хранится в одном байте, также его можно уменьшить до КБ, если использовать только бит для каждого коэффициента
Повторная линеаризация
Атака релинеризации направлена на решение переопределенных систем многомерных квадратичных уравнений. Пусть - система из квадратичных уравнений по переменным . Основная идея заключается в введении новой переменной для каждого квадратичного одночлена . Таким образом, получается система линейных уравнений, если число уравнений достаточно велико, можно использовать метод Гаусса.
Нужно удостовериться, действительно ли полученное таким образом решение является решением квадратичного система, при условии, что .
Для решения системы квадратичных уравнений по переменным этим методом необходимо уравнений.
Таким образом атака методом повторной линеаризации позволяет уменьшить количество неизвестных переменных в закрытом ключе т.е уменьшить его размерность. [18]
XL алгоритм
Пусть — множество всех многочленов из степени .
XL-алгоритм: Входные данные: множество квадратичных многочленов . Выходные данные: вектор такой, что .
for to do
Фиксируется целое число .
Формируются все многочлены:, где и .
Необходимо воспользоваться методом Гауса для уравнений, полученных на предыдущем шаге, чтобы сгенерировать одно уравнение, содержащее только .
Если на предыдущем шаге получился, по крайней мере один одномерный многочлен от , то его необходимо решить, например при помощи алгоритма Берлекэмпа.
Необходимо упростить уравнения путем замены значения .
end for
return
Атака при помощи XL-алгритма позволяет уменьшить размерность закрытого ключа при помощи сведения системы уравнений к инварианту в некоторой переменной. Таким образом при помощи XL-алгоритма возможно проводить атаку на открытый ключ. [4]
JINTAI DING, DIETER SCHMIDT.Reuleaux Triangle(англ.).MULTIVARIABLE PUBLIC–KEY CRYPTOSYSTEMS.Дата обращения: 18 декабря 2017.Архивировано 9 августа 2016 года.
H. Ong, C.-P. Schnorr and A. Shamir Efficient signature schemes based on polynomial equations. In CRYPTO, volume 196 of Lecture Notes in Computer Science // Springer: journal. — 1984, pages 37–46.
T. Matsumoto and H. Imai EPublic quadratic polynomial-tuples for efficient signature verifi- cation and message-encryption. In EUROCRYPT, volume 330 of Lecture Notes in Computer Science // Springer: journal. — 1988, pages 419–553
NESSIE.Reuleaux Triangle(англ.).NESSIE: New European Schemes for Signatures, Integrity, and Encryption. NESSIE project announces final selection of crypto algorithms.Information Society Technologies Programme of the European Commission (IST-1999-12324).Дата обращения: 3 декабря 2017.Архивировано 12 июня 2018 года.
Jacques Patarin, Louis Goubin, and Nicolas Courtois.Reuleaux Triangle(англ.).Improved Algorithms for Isomorphisms of Polynomials (1998).Springer.Дата обращения: 21 декабря 2017.Архивировано 16 июля 2017 года.
I.-T. Chen, M.-S. Chen, T.-R. Chen, C.-M. Cheng, J. Ding, E. L.-H. Kuo, F. Y.-S. Lee and B.-Y. Yang SSE implementation of multivariate PKCs on modern x86 CPUs. In CHES, volume 5747 of Lecture Notes in Computer Science // Springer: journal. — 2009, pages 33–48
A. Bogdanov, T. Eisenbarth, A. Rupp and C. Wolf Time-area optimized public-key engines: MQ-cryptosystems as replacement for elliptic curves? // Springer: CHES, volume 5154 of Lecture Notes in Computer Science. — 2008, pages 45–61
J. Patarin, N. Courtois and L. Goubin Flash, a fast multivariate signature algorithm // Springer: In CT-RSA, volume 2020 of Lecture Notes in Computer Science. — 2001, pages 298–307
Harriet Fell and Whitfield Diffie Analysis of a public key approach based on polynomial substitution. In Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif.) // Springer: journal. — 1986. — volume 218, pages 340–349.
T. Matsumoto and H. Imai Public quadratic polynomial-tuples for efficient signature verification and message encryption. In C. G. Guenther, editor, Advances in cryptology – EUROCRYPT ’88 // Springer: journal. — 1988. — volume 330, pages 419–453.
Jacques Patarin, Louis Goubin, and Nicolas Courtois C∗−+ and HM: variations around two schemes of T. Matsumoto and H. Imai. In K. Ohta and D. Pei,editors, ASIACRYPT’98 // Springer: journal. — 1998. — volume 1514, pages 35–50.
Multivariate Public Key Cryptography
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.