Implicit Polynomial Recovery and Cryptanalysis of a Combinatorial Key Cryptosystem

摘要

A public key cryptosystem based on factoring and a combinatorial problem of matrices over ?_ N proposed in 2010 is analyzed in this paper. We propose an efficient partial private key recovery attack on it by solving a problem of recovering implicit polynomials with small coefficients given their large roots and deriving the large roots from the public key. From the partial information of private key, we can decrypt any ciphertext of the cryptosystem by a simple computation. Our implicit polynomial recovery is an application of lattice basis reduction.