Cryptanalysis on CCA2-Secured LRPC-Kronecker Cryptosystem

摘要

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.