A certificateless signature (CLS) scheme with short signature
size is proposed in this paper. Our scheme is as efficient as BLS
short signature scheme in both communication and computation, and
therefore turns out to be more efficient than other CLS schemes proposed
so far. We provide a rigorous security proof of our scheme in the
random oracle model. The security of our scheme is based on the k-CAA
hard problem and a new discovered hard problem, namely, modified k-
CAA problem. Our scheme can be applied to systems where signatures
are typed in by human or systems with low-bandwidth channels and/or
low-computation power, such as PDAs or cell phones.