Concerning the problem of key collision and the storage space of matrices of seeded-key in Combined Public Key (CPK), a method of coefficient remapping was proposed and the rules of selecting the elements of seeded matrices were designed. Firstly, in the phase of identification mapping, the binary bit streams were produced, and they were divided into coefficient sequence and row sequence. Then the coefficient sequence was remapped according to the remapping rules, which could avoid that the coefficient was zero. So the storage space of the matrices was reduced by the coefficient remapping. Secondly, in the generation step of seeded-key matrix, based on the coefficient remapping, some rules were specified to choose elements to create matrices of seeded-key to ensure that the generated keys were exclusive. Finally, the elements of the matrices were selected according to the row sequence and the increasing column sequence. Then the public key and the private key were generated on the basis of the coefficient sequence and the selected elements. The theoretical analysis results suggest that the proposed scheme can optimize the storage of matrices and solve the key collision problem.