Abstract
Recently, a new rank metric code, namely LRPC-Kronecker Product codes was proposed in APKC 2018 Workshop, and adapted into a construction of a new cryptosystem, namely the LRPC-Kronecker cryptosystem. The LRPC-Kronecker cryptosystem has compact key size, with their parameters achieve 256-bit security with key size (9,768 bits) smaller than the RSA’s key size (15,360 bits). It was also shown that the LRPC-Kronecker cryptosystem is CCA2-secured via the Kobara-Imai conversion. In this paper, we point out some errors in the original LRPC-Kronecker cryptosystem and suggest a reparation for the errors. We show that the LRPC-Kronecker cryptosystem in fact is equivalent to the LRPC cryptosystem. With this equivalence shown, we suggest alternative encryption and decryption, namely AKron for the LRPC-Kronecker cryptosystem. Furthermore, we show that there exists design weakness in the LRPC-Kronecker cryptosystem. We exploit this weakness and successfully cryptanalyze all the suggested parameters for \(k_1 = n_1\). We are able to recover secret key for all the proposed parameters within the claimed security level.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.-P.: A new algorithm for solving the rank syndrome decoding problem. In: Proceedings of IEEE International Symposium on Information Theory (ISIT 2018), pp. 2421–2425 (2018)
Augot, D., Loidreau, P., Robert, G.: Generalized Gabidulin codes over fields of any characteristic. Des. Codes Crypt. 86(8), 1807–1848 (2018)
Faugère, J.-C., Levy-dit-Vehel, F., Perret, L.: Cryptanalysis of MinRank. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 280–296. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_16
Gabidulin, E.M.: Theory of codes with maximum rank distance. Probl. Peredachi Informatsii 21(1), 3–16 (1985)
Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. IEEE Trans. Inf. Theory 62(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., Zémor, G.: On the hardness of the decoding and the minimum distance problems for rank codes. IEEE Trans. Inf. Theory 62(12), 7245–7252 (2016)
Goubin, L., Courtois, N.T.: Cryptanalysis of the TTM cryptosystem. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 44–57. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44448-3_4
Horlemann-Trautmann, A., Marshall, K., Rosenthal, J.: Extension of overbeck’s attack for Gabidulin based cryptosystems. Des. Codes Crypt. 86(2), 319–340 (2018)
Kim, J.-L., Galvez, L., Kim, Y.-S., Lee, N.: A new LRPC-Kronecker product codes based public-key cryptography. In: Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop (APKC 2018), pp. 25–33 (2018)
Kobara, K., Imai, H.: Semantically secure McEliece public-key cryptosystems -conversions for McEliece PKC. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 19–35. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_2
Levy-dit-Vehel, F., Perret, L.: Algebraic decoding of rank metric codes. In: Proceedings of Yet Another Conference on Cryptography (YACC 2006), pp. 142–152 (2006)
Lau, T.S.C., Tan, C.H.: A new technique in rank metric code-based encryption. Cryptography 2, 32 (2018)
Lau, T.S.C., Tan, C.H.: A new Gabidulin-like code and its application in cryptography. In: Carlet, C., Guilley, S., Nitaj, A., Souidi, E.M. (eds.) C2SI 2019. LNCS, vol. 11445, pp. 269–287. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-16458-4_16
McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. The Deep Space Network Progress Report 42-44, pp. 114–116. Jet Propulsion Laboratory, Pasedena, CA (1978)
Ourivski, A.V., Johansson, T.: New technique for decoding codes in the rank metric and its cryptography applications. Probl. Inf. Transm. 38(3), 237–246 (2002)
Acknowledgments
The authors would like to thank the Galvez et al. (the authors of [10]) for their feedback on our identification of the errors in the original proposal.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Lau, T.S.C., Tan, C.H. (2019). Cryptanalysis on CCA2-Secured LRPC-Kronecker Cryptosystem. In: Jang-Jaccard, J., Guo, F. (eds) Information Security and Privacy. ACISP 2019. Lecture Notes in Computer Science(), vol 11547. Springer, Cham. https://doi.org/10.1007/978-3-030-21548-4_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-21548-4_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-21547-7
Online ISBN: 978-3-030-21548-4
eBook Packages: Computer ScienceComputer Science (R0)