Palette images are widely used in multimedia and internet applications for several purposes. I happened to go through a magazine which quoted the use of palette images in a rather interesting way. They had studied the various ways and means of using palette images. A new method for data hiding in palette images with security protection by color ordering and mapping, as well as parameter randomization, was proposed. First image pixels are classified as data embeddable or nonembeddable, and only the former ones are used to embed secret data. The proposed idea of data hiding is based on the use of a new type of color-ordering relationship, from which a color-mapping function is defined with binary values as output.