Geodesic
Post-quantum signature proposal for standardisation
Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 44-51.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $\mathsf{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.
Keywords: signature scheme, lattice-based cryptography, post-quantum cryptography
Mots-clés : Fiat — Shamir transform. 
@article{PDMA_2020_13_a13,
     author = {E. A. Kirshanova and N. S. Kolesnikov and E. S. Malygina and S. A. Novoselov},
     title = {Post-quantum signature proposal for standardisation},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {44--51},
     publisher = {mathdoc},
     number = {13},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2020_13_a13/}
}
TY  - JOUR
AU  - E. A. Kirshanova
AU  - N. S. Kolesnikov
AU  - E. S. Malygina
AU  - S. A. Novoselov
TI  - Post-quantum signature proposal for standardisation
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2020
SP  - 44
EP  - 51
IS  - 13
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2020_13_a13/
LA  - ru
ID  - PDMA_2020_13_a13
ER  - 
%0 Journal Article
%A E. A. Kirshanova
%A N. S. Kolesnikov
%A E. S. Malygina
%A S. A. Novoselov
%T Post-quantum signature proposal for standardisation
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2020
%P 44-51
%N 13
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2020_13_a13/
%G ru
%F PDMA_2020_13_a13
E. A. Kirshanova; N. S. Kolesnikov; E. S. Malygina; S. A. Novoselov. Post-quantum signature proposal for standardisation. Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 44-51. http://geodesic.mathdoc.fr/item/PDMA_2020_13_a13/

[1] Alkim E., Ducas L., Pöppelmann T., Schwabe P., “Post-quantum key exchange: A new hope”, USENIX Conf. Security Symposium, 2016, 327–343

[2] Adeline L., Stehlé S., “Worst-case to average-case reductions for module lattices”, Des. Codes Cryptography, 75:3 (2015), 565–599 | DOI | MR | Zbl

[3] Kirshanova E., Kolesnikov N., Malygina E., Novoselov S., Proekt standartizatsii post-kvantovoi tsifrovoi podpisi (polnaya versiya), https://crypto-kantiana.com/main_papers/main_Signature.pdf

[4] Fiat A., Shamir A., “How to prove yourself: Practical solutions to identification and signature problems”, CRYPTO'86, LNCS, 263, 1987, 186–194 | MR | Zbl

[5] Lyubashevsky V., “Fiat — Shamir with aborts: Applications to lattice and factoring-based signatures”, ASIACRYPT'2009, LNCS, 5912, 2009, 598–616 | MR | Zbl

[6] Bai S., Galbraith S. D., “An improved compression technique for signatures based on learning with errors”, Topics in Cryptology — CT-RSA 2014, LNCS, 8366, 2014, 28–47 | MR | Zbl

[7] 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, 238–268 | DOI | MR

[8] Alkim E., Bindel N., Buchmann J., et al., “Revisiting TESLA in the quantum random oracle model”, PQCrypto 2017, LNCS, 10346, 2017, 143–162 | MR | Zbl

[9] D'Anvers J.-P., Karmakar A., Roy S. S., Vercauteren F., “Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM”, Progress in Cryptology, AFRICACRYPT 2018, Springer, 2018, 282–305 | MR | Zbl

[10] Banerjee A., Peikert C., Rosen A., “Pseudorandom functions and lattices”, Ann. Intern. Conf. Theory and Appl. of Cryptographic Techniques, Springer, 2012, 719–737 | MR | Zbl

[11] Regev O., “On lattices, learning with errors, random linear codes, and cryptography”, J. ACM, 56:6 (2005), 84–93 | MR

[12] Bogdanov A., Guo S., Masny D., et al., “On the hardness of learning with rounding over small modulus”, Theory of Cryptography, LNCS, 9562, 2016, 209–224 | MR | Zbl

[13] Ajtai M., “Generating hard instances of lattice problems (extended abstract)”, Proc. 28th Ann. ACM Symp. Theory Computing, 1996, 99–108 | MR | Zbl

[14] Kiltz E., Lyubashevsky V., Schaffner C., “A concrete treatment of Fiat — Shamir signatures in the quantum random-oracle model”, Adv. Cryptology, EUROCRYPT 2018, Springer, 2018, 552–586 | MR | Zbl

[15] Albrecht M. R., Göpfert F., Virdia F., Wunderer T., “Revisiting the expected cost of solving uSVP and applications to LWE”, ASIACRYPT 2017, LNCS, 10624, 2017, 297–322 | MR | Zbl

[16] Albrecht M. R., Curtis B. R., Deo A., et al., Estimate all the $\{$LWE, NTRU$\}$ schemes!, SCN 2018, LNCS, 11035, 2018, 351–367 | MR | Zbl