ON THE NUMBER OF MESSAGES WHICH CANNOT BE CONCEALED IN LUC

Recently, Smith and Lennon proposed a new public key cryptosystem, cal led LUC, which uses the Lucas function as the one-way function in thei r cryptographic mechanisms instead of using the exponentiation functio n. They conjectured that LUC is cryptographically stronger than RSA in 1993. Since then, many weaknesses of LUC have been discovered, e.g., similar to RSA, LUC also suffers from the chosen-message attacks and t he evaluation in LUC is slightly less efficient than that in RSA. In t his paper, we analyze another possible weakness of LUC that was not po inted out before. We show that the number of messages which cannot be concealed in LUC is at least as the same as that in RSA regardless of the choice of public keys. In particular, in many cases, the number of messages which cannot be concealed in LUC is greater than that in RSA . This implies that the choice of public keys in LUC needs more limita tions than that used in RSA. Our results are useful to designers who c onsider to use LUC type systems.