Proceedings of TUSUR University / Archive / Issue of Journal № 2, t. 28, 2025 / Lattice-Based Threshold Signature Scheme with Newton Interpolation

Lattice-Based Threshold Signature Scheme with Newton Interpolation

DOI: 10.21293/1818-0442-2025-28-2-166-171

Download article in PDF format

JATS xml

Abstract: This paper presents a novel threshold digital signature scheme that combines lattice-based cryptography with interpolation methods. The scheme is built upon the Learning with Rounding (LWR) problem and can be applied to secure IoT devices, where the combination of computational efficiency and quantum resistance is particularly valuable. The proposed approach utilizes Newton interpolation, which demonstrates advantages over classical Lagrange interpolation in terms of performance and flexibility when working with dynamic participant groups.

Keywords: threshold signature, lattice-based cryptography, Newton interpolation, LWR, SIS, post-quantum cryptography, secret sharing

Funding: The work was carried out within the framework of a state assignment (project FSER-2025–0003).

For citation:
Kustov E. F., Bezzateev S. V. Lattice-Based Threshold Signature Scheme with Newton Interpolation. Doklady Tomskogo gosudarstvennogo universiteta sistem upravleniya i radioelektroniki, 2025, vol. 28, no. 2, pp. 166–171. DOI: 10.21293/1818-0442-2025-28-2-166-171

Authors and copyright holders:

Kustov E. F. , ITMO University (St. Petersburg, Russia)
Bezzateev S. V. , ITMO University (St. Petersburg, Russia), State University of Aerospace Instrumentation (St. Petersburg, Russia)

1. Shor P.W. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings 35th annual symposium on foundations of computer science. Santa Fe, NM, USA: IEEE, 1994, pp. 124–134.
2. Dehkordi M.H., Farahi S.T., Mashhadi S. LWE-based verifiable essential secret image sharing scheme ((t, s, k, n)- VESIS). IET Image Processing. Stevenage, UK: IET, 2024, vol. 18, no. 4, pp. 1053–1072.
3. Çalkavur S., Öztöprak Z., Yayla O. Code Based Secret Sharing Schemes: Applied Combinatorial Coding Theory. Singapore: World Scientific, 2022. 212 p.
4. Boneh D., Komlo C. Threshold signatures with private accountability. Annual International Cryptology Conference. Zurich, Switzerland: Springer Nature Switzerland, 2022, pp. 551–581.
5. Baird L. et al. Threshold signatures in the multiverse. 2023 IEEE Symposium on Security and Privacy (SP). San Francisco, CA, USA: IEEE, 2023, pp. 1454–1470.
6. Fischlin M., Mitrokotsa A., Tomy J. BUFFing Threshold Signature Schemes. IACR International Conference on Public-Key Cryptography. Lyon, France: Springer, Cham, 2025, pp. 137–168.
7. Duc A., Tramer F., Vaudenay S. Better algorithms for LWE and LWR. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Sofia, Bulgaria: Springer Berlin Heidelberg, 2015, pp. 173–202.
8. Bezzateev S., Davydov V., Ometov A. On secret sharing with Newton's polynomial for multi-factor authentication. Cryptography, 2020, vol. 4, no. 4, pp. 34.
9. Shamir A. How to share a secret. Communications of the ACM, 1979, vol. 22, pp. 612–613.
10. Blakley G.R. Safeguarding cryptographic keys. Managing requirements knowledge, international workshop on, IEEE Computer Society, 1979, p. 313.
11. Shoup V. Practical threshold signatures. Advances in Cryptology-EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques. Bruges, Belgium: Springer Berlin Heidelberg, 2000, pp. 207–220.
12. Banerjee A., Peikert C., Rosen A. Pseudorandom functions and lattices // Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cambridge, UK: Springer Berlin Heidelberg, 2012, pp. 719–737.
13. Jiang T., Fang H., Wang H. Blockchain-based internet of vehicles: Distributed network architecture and performance analysis. IEEE Internet of Things Journal, 2018, vol. 6, no. 3, pp. 4640–4649.
14. Damgård I. et al. Two-round n-out-of-n and multi-signatures and trapdoor commitment from lattices. Journal of Cryptology, 2022, vol. 35, no. 2, pp. 14.
15. Kiltz E., Lyubashevsky V., Schaffner C. A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. Advances in Cryptology-EUROCRYPT 2018. Tel Aviv, Israel: Springer International Publishing, 2018, pp. 552–586.
16. Kirshanova E.A. et al. Proekt Standartizatsii Postkvantovoj Tsifrovoj Podpisi [Project for Standardization of Post-Quantum Digital Signatures] Prikladnaya Diskretnaya Matematika. Supplement, 2020, no. 13, pp. 44–51 (in Russ.).