This paper proposes a method to apply BPCS-Steganography that we have already proposed for gray scale images to palette-based images which consists of a palette storing color vector information and an index image whose pixel value is corresponding to a index in the palette. A palette-based images can be represented by combining R G and B color component images. We embed secret information into the G images. A number of color vectors in a palette after embedding by BPCS would be over the maximum number, which is usually 256. In order to reduce the number of colors, the rest two component images are then changed in a way that minimizes the square error. The idea behind the color quantization is that the degrading of images manipulated to reduce color is worse than the degrading which occurs with the embedding.