Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 11478))
Included in the following conference series:
2424Accesses
Abstract
We describe a variation of the Schnorr-Lyubashevsky approach to devising signature schemes that is adapted to rank based cryptography. This new approach enables us to obtain a randomization of the signature, which previously seemed difficult to derive for code-based cryptography. We provide a detailed analysis of attacks and an EUF-CMA proof for our scheme. Our scheme relies on the security of the Ideal Rank Support Learning and the Ideal Rank Syndrome problems and a newly introduced problem: Product Spaces Subspaces Indistinguishability, for which we give a detailed analysis. Overall the parameters we propose are efficient and comparable in terms of signature size to the Dilithium lattice-based scheme, with a signature size of 4 kB for a public key of size less than 20 kB.
N. Aragon—This work was partially funded by French DGA.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 11439
- Price includes VAT (Japan)
- Softcover Book
- JPY 14299
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aguilar Melchor, C., et al.: HQC 2017. NIST Round 1 submission for Post-Quantum Cryptography (2017)
Aguilar Melchor, C., et al.: RQC 2017. NIST Round 1 submission for Post-Quantum Cryptography (2017)
Aguilar Melchor, C., Gaborit, P., Schrek, J.: A new zero-knowledge code based identification scheme with reduced communication. In: Proceedings of the IEEE ITW (2011)
Aragon, N., et al.: BIKE 2017. NIST Round 1 submission for Post-Quantum Cryptography (2017)
Aragon, N., Gaborit, P., Hauteville, A., Ruatta, O., Zémor, G.: Low rank parity check codes: new decoding algorithms and application to cryptography. IEEE Trans. Inf. Theory (2019, submitted)
Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.-P.: A new algorithm for solving the rank syndrome decoding problem. In: Proceedings of the IEEE ISIT (2018)
Courtois, N.T., Finiasz, M., Sendrier, N.: How to achieve a McEliece-based digital signature scheme. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 157–174. Springer, Heidelberg (2001).https://doi.org/10.1007/3-540-45682-1_10
Debris-Alazard, T., Sendrier, N., Tillich, J.-P.: The problem with the surf scheme. Preprint (2017).https://arxiv.org/abs/1706.08065
Debris-Alazard, T., Tillich, J.-P.: Two attacks on rank metric code-based schemes: Ranksign and an identity-based-encryption scheme. In: ASIACRYPT (2018)
Faugère, Je.-C., Gauthier, V., Otmani, A., Perret, L., Tillich, J.-P.: A distinguisher for high rate McEliece cryptosystems. IEEE Trans. Inf. Theory IT59(10), 6830–6844 (2013)
Fukushima, K., Sarathi Roy, P., Xu, R., Kiyomoto, S., Morozov, K., Takagi, T.: RaCoSS. NIST Round 1 submission for Post-Quantum Cryptography (2017)
Gaborit, P., Hauteville, A., Phan, D.H., Tillich, J.-P.: Identity-based encryption from codes with rank metric. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 194–224. Springer, Cham (2017).https://doi.org/10.1007/978-3-319-63697-9_7
Gaborit, P., Murat, G., Ruatta, O., Zémor, G.: Low rank parity check codes and their application to cryptography. In: Proceedings of the WCC (2013)
Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. IEEE Trans. Inf. Theory IT62(2), 1006–1019 (2016)
Gaborit, P., Ruatta, O., Schrek, J., Zémor, G.: New results for rank-based cryptography. In: Pointcheval, D., Vergnaud, D. (eds.) AFRICACRYPT 2014. LNCS, vol. 8469, pp. 1–12. Springer, Cham (2014).https://doi.org/10.1007/978-3-319-06734-6_1
Gaborit, P., Ruatta, O., Schrek, J., Zémor, G.: RankSign: an efficient signature algorithm based on the rank metric. In: Mosca, M. (ed.) PQCrypto 2014. LNCS, vol. 8772, pp. 88–107. Springer, Cham (2014).https://doi.org/10.1007/978-3-319-11659-4_6
Gaborit, P., Schrek, J., Zémor, G.: Full cryptanalysis of the chen identification protocol. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 35–50. Springer, Heidelberg (2011).https://doi.org/10.1007/978-3-642-25405-5_3
Gaborit, P., Zémor, G.: On the hardness of the decoding and the minimum distance problems for rank codes. IEEE Trans. Inf. Theory IT62(12), 7245–7252 (2016)
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC (2008)
Goldwasser, S., Micali, S., Rivest, R.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput.17(2), 281–308 (1988)
Håstad, J., Impagliazzo, R., Levin, L., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput.28(4), 1364–1396 (1999)
Hauteville, A., Tillich, J.-P.: New algorithms for decoding in the rank metric and an attack on the LRPC cryptosystem. In: Proceedings of the IEEE ISIT (2015)
Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J., Whyte, W.: NTRUSign: digital signatures using the NTRU lattice. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 122–140. Springer, Heidelberg (2003).https://doi.org/10.1007/3-540-36563-X_9
Lee, W., Kim, Y.-S., Lee, Y.-W., No, J.-S.: pqsigRM 2017. NIST Round 1 submission for Post-Quantum Cryptography (2017)
Loidreau, P.: On cellular code and their cryptographic applications. In: Proceedings of ACCT (2014)
Lyubashevsky, V.: Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 598–616. Springer, Heidelberg (2009).https://doi.org/10.1007/978-3-642-10366-7_35
Lyubashevsky, V.: Lattice signatures without trapdoors. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 738–755. Springer, Heidelberg (2012).https://doi.org/10.1007/978-3-642-29011-4_43
Lyubashevsky, V., et al.: CRYSTALS-DILITHIUM 2017. NIST Round 1 submission for Post-Quantum Cryptography (2017)
Persichetti, E.: Improving the efficiency of code-based cryptography. Ph.D. thesis, The University of Auckland (2012).https://persichetti.webs.com/Thesis%20Final.pdf
Schnorr, C.-P.: Efficient signature generation by smart cards. J. Cryptol.4, 161–174 (1991)
Stern, J.: A new identification scheme based on syndrome decoding. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 13–21. Springer, Heidelberg (1994).https://doi.org/10.1007/3-540-48329-2_2
Acknowledgements
This work has been supported in part by the French ANR projects CBCRYPT (ANR-17-CE39-0007) and ID-FIX (ANR-16-CE39-0004). The authors would like to thank Alain Couvreur for his insightful comments.
Author information
Authors and Affiliations
XLIM-DMI, University of Limoges, 123 Avenue Albert Thomas, 87060, Limoges Cedex, France
Nicolas Aragon, Olivier Blazy, Philippe Gaborit & Adrien Hauteville
Université de Bordeaux, Institut de Mathématiques, UMR 5251, 351 cours de la Libération, 33400, Talence, France
Gilles Zémor
- Nicolas Aragon
You can also search for this author inPubMed Google Scholar
- Olivier Blazy
You can also search for this author inPubMed Google Scholar
- Philippe Gaborit
You can also search for this author inPubMed Google Scholar
- Adrien Hauteville
You can also search for this author inPubMed Google Scholar
- Gilles Zémor
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toAdrien Hauteville.
Editor information
Editors and Affiliations
Technion, Haifa, Israel
Yuval Ishai
COSIC Group, KU Leuven, Heverlee, Belgium
Vincent Rijmen
Rights and permissions
Copyright information
© 2019 International Association for Cryptologic Research
About this paper
Cite this paper
Aragon, N., Blazy, O., Gaborit, P., Hauteville, A., Zémor, G. (2019). Durandal: A Rank Metric Based Signature Scheme. In: Ishai, Y., Rijmen, V. (eds) Advances in Cryptology – EUROCRYPT 2019. EUROCRYPT 2019. Lecture Notes in Computer Science(), vol 11478. Springer, Cham. https://doi.org/10.1007/978-3-030-17659-4_25
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-17658-7
Online ISBN:978-3-030-17659-4
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative