Проект стандартизации постквантовой цифровой подписи | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/14

Проект стандартизации постквантовой цифровой подписи

Предлагается цифровая подпись, безопасность которой основана на задачах MLWR и MSIS в алгебраических решётках. Конструкция подписи основана на парадигме Фиата - Шамира. Доказывается безопасность схемы в квантовой модели безопасности и описываются конкретные параметры, при которых схема достигает уровня безопасности в 100 бит. Благодаря модульной структуре решёток, уровень безопасности легко изменить в большую или меньшую стороны. Наше предложение может служить основой проекта по стандартизации постквантовых примитивов на решётках.

Post-quantum signature proposal for standardisation.pdf Введение Криптографические примитивы на решётках - одно из самых обещающих направлений современной криптографии не только ввиду стойкости этих примитивов к атакам на квантовом компьютере, но и вследствие большого спектра конструкций (гомоморфное шифрование, электронные голосования, различные типы подписей), а также их надёжности по отношению к классическим атакам. Криптографические конструкции на решётках не только элегантны в теории, но и значимы на практике, поэтому в достаточно скором будущем будут стандартизированы. Пробные версии обмена ключами New Hope уже тестированы в TLS-соединениях для браузера Google Chrome [1]. Процесс стандартизации постквантовых схем доступен по адресу https://csrc.nist.gov/projects/post-quantum-cryptography. В этой работе мы предлагаем схему цифровой подписи, основанную на алгебраических решётках, конструкция которой удовлетворяет следующими основным свойствам: 1) безопасность схемы основана на задачах «в среднем», а именно на задачах LWR (Learning With Rounding) и SIS (Shortest Integer Solution) - классических трудных задачах на решётках, определения которых даны в п. 1); 2) для эффективности схемы используется так называемый модульный вариант задач, а именно module-LWR, module-SIS [2], что не только позволяет уменьшить размеры параметров схемы и время операций, но и даёт возможность легко варьировать уровни безопасности схемы; 3) стойкость схемы доказана в квантовой модели QROM (Quantum Random Oracle Model) для «сильного» атакующего, а именно для атаки вида UF - sCMA; доказательство можно найти в [3]; 4) в процессе генерации ключей и подписи вместо нормального распределения используется равномерное распределение из интервала, что уменьшает риск сторонних атак; 5) предлагается конкретный набор параметров схемы с битовой оценкой сложности атак на предложенные параметры (см. п. 3). Представленная здесь схема основана на парадигме Фиата - Шамира [4, 5] и по идеологии продолжает серию работ, предлагающих конкретные схемы подписи [6-8]. Основное отличие нашей схемы от ранее предложенных заключается в том, что безопасность ключей основана на задаче LWR (а не на задаче LWE (Learning With Errors)). Мы считаем, что такой подход упрощает описание и потенциально ускоряет вычисления. 1. Предварительные сведения 1.1. О б о з н а ч е н и я Будем обозначать ZjqZ кольцо целых по чётному модулю q, результат z mod q представляем в интервале {0,... ,q - 1}; R, Rq и Rp - кольца многочленов Z[x] j(xn+1), ZjqZ[x] j(xn+1) и ZjpZ[x] j(xn+1) соответственно. Векторы будем обозначать жирными строчными буквами (например, x), матрицы - прописными (например, A), константы - обычными строчными; I - единичная матрица. Элементы кольца Z[x] j(xn+1) будем понимать как векторы-коэффициенты многочленов. Векторы по умолчанию являются вектор-столбцами. Евклидова (или t2) норма вектора x определяется как ||x|| = ||x||2 = /£ x2, а £те-норма -как ||x|| = max |x^|. V i i Многочленам из кольца R ставим в соответствие векторы-коэффициенты длины n, поэтому произведение векторов x • y надо понимать как произведение соответствующих многочленов. Элементу a Е Rq ставим в соответствие матрицу rot(a) Е (ZjqZ)nxn, i-я строка которой - коэффициенты многочлена xi-1 • a. Такая матрица задаёт произведение любого элемента из Rq на многочлен a. Для конечного множества S запись s ^ S обозначает, что s выбрано в соответствии со случайным равномерным распределением на S. Через S^ обозначим множество векторов длины £, каждый коэффициент которого взят в соответствии с равномерным распределением из множества {-в,..., в} . Для любого x Е Q запись Round(x) Е Z означает взятие ближайшего целого, где 1 j2 округляется до 1. Для целого x функция MSB(x, d) (соответственно LSB(x, d)) означает взятие d старших (соответственно младших) бит. Все операции распространяются на векторы и матрицы покоэффициентно. В нашей схеме мы будет использовать два модуля: q = 2V и p = 2м. «Конвертирование» элемента x Е ZjqZ в x' Е ZjpZ происходит по правилу x' = Round(x • pjq). Так как модули - степени двойки, этот же результат можно получить, добавив к x константу h = 2V-M-1 и взяв ^ старших бит: x' = MSB(x + h,y). Такое представление операции Round использовано, например, в [9]. Вектор, каждая координата которого равна h, обозначим h. Для всякого целого w > 0 положим Bw = {x Е R : ||x|| = 1, ||x|| = Vw} С R. 1.2. Синтаксис и модели безопасности цифровых подписей Определение 1. Цифровая подпись - примитив, состоящий из трёх алгоритмов: - вероятностный алгоритм генерации ключевой пары KeyGen(par), возвращающий секретный ключ sk и ключ верификации vk; - вероятностный алгоритм генерации подписи Sign(sk, m), который для сообщения те M возвращает подпись а; - детерминированный алгоритм Verify(m, а, vk), который возвращает либо «Accept» (подпись а корректна для (m,vk)), либо «Reject» (подпись а не корректна для (m, vk)). Цифровая подпись корректна с долей ошибки е, если для всех пар (sk, vk) е е KeyGen(par) и всех сообщений те M имеем P [Verify(m, Sign (sk, т), vk) = «Accept»] ^ 1 - е. 1.3. Сложные задачи на решётках Безопасность нашей подписи основывается на двух «сложных в среднем» задачах. Первая - задача Обучения с Округлением (Learning With Rounding (LWR)) [10] - детерминированная версия задачи Обучения с Ошибками (Learning With Errors (LWE)) [11]. В основе безопасности ключей подписи лежит трудность этой модульной версии задачи над фактор-кольцом iq [2]. Все вычисления производятся в фактор-кольце iq, матрица A формируется как блочная матрица из k ■ £ элементов из iq, где каждый блок - матрица rot(a). Для предлагаемой схемы, в отличие от классических задач LWR и LWE, где матрица A берётся случайным образом из будем требовать, чтобы хотя бы один из k ■ £ многочленов был обратим в iq. Будем обозначать такую матрицу через A. Это требование не влияет на безопасность схемы, поскольку, как минимум, константное число многочленов обратимы в Rq 1. Значит, если атакующий имеет непренебрежимо малую вероятность успеха для A, этот же атакующий имеет непренебрежимо малую вероятность успеха для A ^ Rq. Определение 2 (задача обучения с округлением (MLWR)). Пусть q ^ p ^ 1, k,£ ^ 1 -целые числа. MLWR-распределение для вектора s ^ R есть множество пар вида ^A, Round ^-q ■ A ■ s^, где A ^ i^. Задача поиска: для заданного произвольным образом большого числа выборок из MLWR-распределения для вектора s ^ R восстановить s. Задача различения распределений: для заданного произвольным обраkx^ ok q x Rp ыми для вектора s ^ Rq. Обе версии задачи эквивалентны (то есть, имея оракул, решающий одну задачу, можно решить другую за полиномиальное от n время) [12]. В доказательстве безопасности схемы подписи нам понадобится вторая версия. Безопасность подписи основана на задаче нахождения Короткого Целочисленного Решения (Short Integer Solution (SIS) problem) [13]. Нам потребуется модульная версия этой задачи. Определение 3 (задача нахождения Короткого Целочисленного Решения (MSIS)) Зафиксируем b е N и пусть A ^ Модульная задача нахождения короткого це лочисленного решения, параметризованная посредством b > 0, заключается в нахождении «короткого» ненулевого прообраза y ^ в решётке, определяемой A, т. е. _У = 0, [I|A] ■ y = 0 и ||у||те ^ b. 1 Вероятность обратимости случайного многочлена в Rq, где q - степень двойки, не столь тривиальна (и не столь велика), как в случае простого q. Случайный многочлен a е Rq обратим тогда и только тогда, когда rot(a) -обратимая матрица в Z/qZnxn, что, в свою очередь, верно тогда и только тогда, когда det(rot(a)) -обратимый элемент в Z/qZ. В случае q = 2V имеем |Z*| = 2V-1, а значит, случайный элемент из Z/qZ обратим с вероятностью |Z*|/q = 1/2. зом большого числа выборок из iR^ x R определить, являются ли они равномерно распределёнными или MLWR-распределёнными для вектора s ^ Rq. Для доказательства безопасности схемы потребуется вариант задачи SIS, так называемый SelfTargetSIS, предложенный в [14]. В этой же работе описана редукция от SIS к SelfTargetSIS. Определение 4 (задача SelfTargetSIS). Пусть H : {0,1}* ^ Bw - криптографическая хэш-функция. Зададим случайным образом A ^ Rlqxi и доступ к квантовому случайному оракулу H(-). Для исходного сообщения M G {0,1}* задача SelfTargetSIS сводится к нахождению y =[r, c]T, где 0 ^ ||у||те ^ y, H([A|I] ■ y, M) = c. 2. Описание схемы Цифровая подпись (алгоритмы 1-3) зависит от следующих параметров: q = 2V, p = 2м, v > Используется криптографическая хэш-функция H : {0,1}* ^ Bw [7]. Параметры k,t отвечают за размерности ключей; s, y задают интервалы для коэффициентов многочленов в процессе генерации ключей или подписи; d, в отвечают за корректность и безопасность схемы. Подпись формируется для сообщений M Е {0,1}*. Конкретные значения параметров заданы в п. 3. Алгоритм 1. Генерация ключей Вход: t > k > 1, q > p, s. Выход: A, t. 1: A ^ Rkqxl; 2: s ^ SS; 3: t := Round ^p ■ As^J . // ||t - As||^ ^ 2V-M 4: Вернуть sk = s, vk = (A, t). Алгоритм 2. Генерация подписи Вход: q = 2V, p = 2м, t > 1, M, A, t, s, d, H, в, Y, w. Выход: (z, c). 1: У ^ SY-ь 2: c := H (MSB(A ■ y,d),M); 3: z := у + sc; 4: w := Az - t ■ 2V-M ■ c; 5: Если (||LSB(w, v - d)||^ ^ 2v-d - w ■ 2V-м+1) или (||z||^ ^ y - в), то restart. 6: Вернуть (z, c). Алгоритм 3. Проверка подписи Вход: M, z, c, A, t, d, H, в, Выход: «Accept» или «Reject». w := Az - t ■ 2V-M ■ c; c' := H(MSB(w, d)),M); Если c' = c и ||z||^ ^ y - в, то Вернуть «Accept», иначе Вернуть «Reject». 2.1. Корректность Поскольку w = A ■ z - t ■ 2V-M ■ c, z = y + s ■ c и t = Round ( p ■ As ), то q w = A ■ (y + s ■ c) - c ■ 2V-M ■ Round ^p ■ As^ = Ay + Asc - c ■ 2V~^ ■ Round ^p ■ As Согласно введённым обозначениям, Round ( - ■ As ) = MSB(As + h, p), где h - вектор, q каждая координата которого равна h = 2V м 1. Тогда w = Ay + Asc - c ■ 2V-M ■ MSB(As + h,p) = Ay + Asc - c (As + h + LSB(As + h, v - p)). Раскрывая скобки, окончательно получаем w = Ay - c (h + LSB(As + h, v - p)) , (1) где ||c (h + LSB(As + h,v - p))||^ < w^2v-^+1, поскольку c e Bw и ||LSB(As,v - p) < < 2V-M. Рассматривая LSB(w,v - d) в алгоритме 2 на шаге 5 и учитывая ошибку c (h + LSB(As + h, v - p)), получаем, что при ||LSB(w,v - d)||^ > 2V-d - w ■ 2v-^+1 алгоритм отклоняет значение w. Так как c (h + LSB(As + h, v - p)) -малый вектор ошибки, то из равенства (1) очевидно, что MSB(w,d) = MSB(Ay,d). Следовательно, вычисление c' на шаге 2 алгоритма 3 совпадает со значением вектора c на шаге 2 алгоритма 2. 2.2. О числе итераций в процедуре Sign В процессе вычисления подписи алгоритм 2 на шаге 5 проверяет, попадают ли коэффициенты вектора z в интервал { - (y - в - 1),... , Y - в - 1}. Для фиксированного ключа s вероятность этого события зависит от | y| , выбранного на шаге 1. Вычислим эту вероятность. Пусть z = y + v такой, что z e S^-/3-1. Обозначим в = ||cs||^. Так как ||s||^ ^ s и c e Bw, то в < ws. Отсюда ||v||^ ^ в. Для каждого коэффициента Vj вектора v соответствующий коэффициент zj лежит в интервале { -(y - в - 1),... , Y - в - 1}. Поскольку y = z - v, то y e S^-1 и соответствующий коэффициент yj лежит в интер S^-e-1 L/2y-2в -1\\ в \\nt' ( впЛ вале { -(y - 1),..., Y - 1}. Следовательно, Ve-1 -1= [||z|L

Ключевые слова

цифровая подпись, криптография на решётках, постквантовая криптография, парадигма Фиатa - Шамира, signature scheme, Fiat-Shamir transform, lattice-based cryptography, post-quantum cryptography

Авторы

ФИООрганизацияДополнительноE-mail
Киршанова Елена АлексеевнаБалтийский федеральный университет им. И.КантаPh. D., доцентelenakirshanova@gmail.com
Колесников Никита СергеевичБалтийский федеральный университет им. И.Кантааспирантnikolesnikov1@kantiana.ru
Малыгина Екатерина СергеевнаБалтийский федеральный университет им. И.Кантакандидат физико-математических наук, доцентemalygina@kantiana.ru
Новоселов Семен АлександровичБалтийский федеральный университет им. И.Кантаассистентsnovoselov@kantiana.ru
Всего: 4

Ссылки

Alkim E., Ducas L., Poppelmann T. , and Schwabe P. Post-quantum key exchange: A new hope // USENIX Conf. Security Symposium. 2016. P. 327-343.
Adeline L. and Stehle S. Worst-case to average-case reductions for module lattices // Des. Codes Cryptography. 2015. V.75. No.3. P. 565-599.
Kirshanova E., Kolesnikov N., Malygina E., and Novoselov S. Проект стандартизации постквантовой цифровой подписи (полная версия). https://crypto-kantiana.com/main_ papers/main_Signature.pdf.
Fiat A. and Shamir A. How to prove yourself: Practical solutions to identification and signature problems // CRYPTO'86. LNCS. 1987. V.263. P. 186-194.
Lyubashevsky V. Fiat - Shamir with aborts: Applications to lattice and factoring-based signatures // ASIACRYPT'2009. LNCS. 2009. V. 5912. P. 598-616.
Bai S. and Galbraith S. D. An improved compression technique for signatures based on learning with errors // Topics in Cryptology - CT-RSA 2014. LNCS. 2014. V. 8366. P. 28-47.
Ducas L., Kiltz E., Lepoint T., et al. CRYSTALS-Dilithium: A lattice-based digital signature scheme // IACR Trans. Cryptographic Hardware and Embedded Systems. 2018. No. 1. P. 238268.
Alkim E., Bindel N., Buchmann J., et al. Revisiting TESLA in the quantum random oracle model // PQCrypto 2017. LNCS. 2017. V. 10346. P. 143-162.
D'Anvers J.-P., Karmakar A., Roy S.S., and Vercauteren F. Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM // Progress in Cryptology - AFRICACRYPT 2018. Springer, 2018. P. 282-305.
Banerjee A, Peikert C., and Rosen A. Pseudorandom functions and lattices // Ann. Intern. Conf. Theory and Appl. of Cryptographic Techniques. Springer, 2012. P. 719-737.
Regev O. On lattices, learning with errors, random linear codes, and cryptography //J. ACM. 2005. V. 56. No. 6. P. 84-93.
Bogdanov A., Guo S., Masny D., et al. On the hardness of learning with rounding over small modulus // Theory of Cryptography. LNCS. 2016. V.9562. P. 209-224.
Ajtai M. Generating hard instances of lattice problems (extended abstract) // Proc. 28th Ann. ACM Symp. Theory Computing. 1996. P. 99-108.
Kiltz E., Lyubashevsky V., and Schaffner C., A concrete treatment of Fiat - Shamir signatures in the quantum random-oracle model // Adv. Cryptology - EUROCRYPT 2018. Springer, 2018. P. 552-586.
Albrecht M. R., Gopfert F., Virdia F., and Wunderer T. Revisiting the expected cost of solving uSVP and applications to LWE // ASIACRYPT 2017. LNCS. 2017. V. 10624. P. 297-322.
Albrecht M. R., Curtis B. R., Deo A., et al. Estimate all the {LWE, NTRU} schemes! // SCN 2018. LNCS. 2018. V. 11035. P. 351-367.
 Проект стандартизации постквантовой цифровой подписи | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/14

Проект стандартизации постквантовой цифровой подписи | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/14