СХЕМА ПОСТКВАНТОВОЙ АГРЕГИРОВАННОЙ ПОДПИСИ С ЛЕНИВОЙ ПРОВЕРКОЙ НА ОСНОВЕ МНОГОМЕРНЫХ КВАДРАТИЧНЫХ МНОГОЧЛЕНОВ

Артём О. Макаров

Аннотация


Агрегированные подписи являются частным видом электронных подписей. Они позволяют объединять индивидуальные подписи, полученные различными подписантами для различных сообщений, в единую подпись. Такая подпись обеспечивает аутентичность, целостность и неотказуемость для всех подписанных сообщений. При этом длина полученной агрегированной подписи значительно меньше суммы длин исходных подписей. Последовательные агрегированные подписи – это подтип агрегированных подписей. С их помощью можно объединять индивидуальные подписи только в процессе подписания. Подписи данного типа могут быть использованы во множестве приложений, включая протоколы защищенной маршрутизации, защищенное журналирование, сенсорные сети, инфраструктуру открытых ключей, блокчейн. В данной статье представлена новая схема постквантовой агрегированной подписи с ленивой проверкой. Данная схема позволяет избавиться от необходимости проверки текущей последовательной агрегированной подписи при формировании новой, что расширяет её возможное применение по сравнению с существующими последовательными постквантовыми схемами. В качестве основы предлагаемой схемы подписи используется односторонняя подстановка с секретом HFEv-, являющаяся стойкой к квантовым атакам; а также обобщенная конструкция Гентри, О’Нила и Рейзина для получения ленивой верификации с применением идеального шифра, который может быть реализован с использованием сети Фейстеля и блочного шифра. Для представленной схемы приведены формальные доказательства её стойкости на основе игровой модели Белларе – Рогавея, заключающиеся в сведении стойкости схемы к стойкости односторонней подставки с секретом HFEv-, а также представлен набор параметров схемы для параметров стойкости в 80 и 120 бит.


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


электронная подпись, постквантовая криптография, агрегированная подпись, последовательная агрегированная подпись, ленивая проверка, квадратичные многочлены.

Полный текст:

PDF

Литература


1. Shor P.W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 1997, vol. 26, no. 5, p. 1484–1509.
DOI: https://doi.org/10.1137/S0097539795293172.

2. Patarin J. (1996). Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. In: Maurer, U. (eds) Advances in Cryptology – EUROCRYPT ’96. EUROCRYPT 1996. Lecture Notes in Computer Science, vol 1070. Springer, Berlin, Heidelberg.
DOI: https://doi.org/10.1007/3-540-68339-9_4.

3. Petzoldt A., Chen MS., Yang BY., Tao C., Ding J. (2015). Design Principles for HFEv- Based Multivariate Signature Schemes. In: Iwata, T., Cheon, J. (eds) Advances in Cryptology – ASIACRYPT 2015. ASIACRYPT 2015. Lecture Notes in Computer Science, vol 9452. Springer, Berlin, Heidelberg.
DOI: https://doi.org/10.1007/978-3-662-48797-6_14.

4. Given N. Gui: Revisiting Multivariate Digital Signature Schemes based on HFEv-. International Conference on the Theory and Application of Cryptology and Information Security, 2014.
URL: https://csrc.nist.gov/groups/ST/post-quantum-2015/papers/session1-ding-paper.pdf (дата обращения: 20.05.2023).

5. Makarov A. (2020). A Survey of Aggregate Signature Applications. In: Misyurin, S., Arakelian, V., Avetisyan, A. (eds) Advanced Technologies in Robotics and Intelligent Systems. Mechanisms and Machine Science,
vol. 80. Springer, Cham. DOI: https://doi.org/10.1007/978-3-030-33491-8_37. – EDN JWCIQD.

6. Makarov A. and Varfolomeev A.A. Extended Classification of Signature-only Signature Models. IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus), St. Petersburg, Moscow, Russia, 2021, p. 2385–2389. DOI: 10.1109/ElConRus51938.2021.9396682. – EDN ESOXBS.

7. Torres W.A.A., Steinfeld R., Sakzad A., Kuchta V. Post-Quantum Linkable Ring Signature Enabling Distributed Authorised Ring Confidential Transactions in Blockchain. IACR Cryptol. ePrint Arch., 2020. URL: https://eprint.iacr.org/2020/1121.pdf (дата обращения: 20.05.2023).

8. Молдовян А.А., Галанов А.И., Синев В.Е. Утверждаемая групповая подпись: новые протоколы. Вопросы Защиты Информации. Утверждаемая групповая подпись. 2016, № 2(113), с. 44–50. – EDN UCBMFU.

9. Fukumitsu, M., Hasegawa, S. (2020). A Lattice-Based Provably Secure Multisignature Scheme in Quantum Random Oracle Model. In: Nguyen, K., Wu, W., Lam, K.Y., Wang, H. (eds) Provable and Practical Security. ProvSec 2020. Lecture Notes in Computer Science, vol 12505. Springer, Cham.
DOI: https://doi.org/10.1007/978-3-030-62576-4_3.

10. Синев В.Е. Повышение уровня безопасности протокола групповой цифровой подписи, основанного на механизме маскирования открытых ключей. Известия СПбГЭТУ «ЛЭТИ». 2016, № 6, c. 21–25. – EDN WBOQXX.

11. Lysyanskaya A., Micali S., Reyzin L., Shacham H. (2004). Sequential Aggregate Signatures from Trapdoor Permutations. In: Cachin, C., Camenisch, J.L. (eds) Advances in Cryptology – EUROCRYPT 2004. EUROCRYPT 2004. Lecture Notes in Computer Science, vol 3027. Springer, Berlin, Heidelberg.
DOI: https://doi.org/10.1007/978-3-540-24676-3_5.

12. Gentry C., O’Neill A., Reyzin L. (2018). A Unified Framework for Trapdoor-Permutation-Based Sequential Aggregate Signatures. In: Abdalla, M., Dahab, R. (eds) Public-Key Cryptography – PKC 2018. PKC 2018. Lecture Notes in Computer Science, vol 10770. Springer, Cham. DOI: https://doi.org/10.1007/978-3-319-76581-5_2.

13. Neven G. Efficient Sequential Aggregate Signed Data. IEEE Transactions on Information Theory. 2011,
vol. 57, no. 3, p. 1803–1815. DOI: https://doi.org/10.1109/TIT.2010.2091434.

14. Brogle K., Goldberg S., Reyzin L. Sequential aggregate signatures with lazy verification from trapdoor permutations. Information and Computation. 2014, vol. 239, p. 356-376.
DOI: https://doi.org/10.1016/j.ic.2014.07.001.

15. El Bansarkhani, R., Mohamed, M.S.E., Petzoldt, A. (2016). MQSAS - A Multivariate Sequential Aggregate Signature Scheme. In: Bishop, M., Nascimento, A. (eds) Information Security. ISC 2016. Lecture Notes in Computer Science, vol 9866. Springer, Cham.
DOI: https://doi.org/10.1007/978-3-319-45871-7_25.

16. Макаров А. Схема пост-квантовой агрегированной подписи на основе теории алгебраического кодирования. Вопросы кибербезопасности. 2019, № 2(30), c. 69–76.
DOI: https://doi.org/10.21681/2311-3456-2019-2-69-76. – EDN TNKFZL.

17. Dara, S., Fluhrer, S. (2014). FNR: Arbitrary Length Small Domain Block Cipher Proposal. In: Chakraborty, R.S., Matyas, V., Schaumont, P. (eds) Security, Privacy, and Applied Cryptography Engineering. SPACE 2014. Lecture Notes in Computer Science, vol 8804. Springer, Cham. DOI: https://doi.org/10.1007/978-3-319-12060-7_10.

18. Rogaway, P. (2004). On the Role Definitions in and Beyond Cryptography. In: Maher, M.J. (eds) Advances in Computer Science – ASIAN 2004. Higher-Level Decision Making. ASIAN 2004. Lecture Notes in Computer Science, vol 3321. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/978-3-540-30502-6_2.

19. Bellare M., Rogaway P. The Game-Playing Technique. URL: https://cr.yp.to/bib/2004/bellare-games.pdf (дата обращения: 20.05.2023).

20. Coron, J.S., Patarin, J., Seurin, Y. (2008). The Random Oracle Model and the Ideal Cipher Model Are Equivalent. In: Wagner, D. (eds) Advances in Cryptology – CRYPTO 2008. CRYPTO 2008. Lecture Notes in Computer Science, vol 5157. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/978-3-540-85174-5_1.

21. Goldwasser S., Micali S., Rivest R.L. A "Paradoxical" Solution To The Signature Problem. 25th Annual Symposium on Foundations of Computer Science, 1984., Singer Island, FL, USA, 1984, p. 441–448.
DOI: http://dx.doi.org/10.1109/SFCS.1984.715946.

22. Dai, Y., Steinberger, J. (2016). Indifferentiability of 8-Round Feistel Networks. In: Robshaw, M., Katz, J. (eds) Advances in Cryptology – CRYPTO 2016. CRYPTO 2016. Lecture Notes in Computer Science, vol 9814. Springer, Berlin, Heidelberg.
DOI: https://doi.org/10.1007/978-3-662-53018-4_4.

23. Feigenbaum J. and. Fortnow L. On the random-self-reducibility of complete sets. Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, IL, USA, 1991, p. 124–132.
DOI: https://doi.org/10.1109/SCT.1991.160252.

24. Dodis, Y., Reyzin, L. (2003). On the Power of Claw-Free Permutations. In: Cimato, S., Persiano, G., Galdi, C. (eds) Security in Communication Networks. SCN 2002. Lecture Notes in Computer Science, vol. 2576. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/3-540-36413-7_5.




DOI: http://dx.doi.org/10.26583/bit.2023.3.02

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.