We present an improvement to the existing steganography-based bandwidth extension scheme. Enhanced WB (wideband) speech quality is achieved by embedding multiple highband spectral gains into a G.711 bitstream. The number of spectral gains is selected by optimizing the quantity of the embedding data with respect to the quality of the extended WB speech. Compared to the existing method, the proposed scheme improves the WB PESQ (Perceptual Evaluation of Speech Quality) score by 0.334 with negligible degradation of the embedded narrowband speech.