Post-quantum signature proposal for standardisation | Applied Discrete Mathematics. Supplement. 2020. № 13. DOI: 10.17223/2226308X/13/14

Post-quantum signature proposal for standardisation

In this paper, we propose an algebraic lattice-based signature scheme. The design of the proposal follows the Fiat - Shamir paradigm. Our scheme is proved secure in the quantum random oracle model and achieves security against UF - sCMA adversaries. The concrete parameters to instantiate the scheme that achieves 100 bits of security are proposed. Thanks to the algebraic structure of the construction, the scheme is flexible in security levels so that we can achieve trade-offs between speed and security. Our proposal may serve as the basis for a standard of lattice-based schemes.

Download file

Counter downloads: 96

Keywords

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

Authors

Name	Organization	E-mail
Kirshanova E. A.	Immanuel Kant Baltic Federal University	elenakirshanova@gmail.com
Kolesnikov N. S.	Immanuel Kant Baltic Federal University	nikolesnikov1@kantiana.ru
Malygina E. S.	Immanuel Kant Baltic Federal University	emalygina@kantiana.ru
Novoselov S. A.	Immanuel Kant Baltic Federal University	snovoselov@kantiana.ru

Всего: 4

References

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.