Broadcast encryption scheme with personalized messages (BEPM) is a new primitive that allows a broadcaster to encrypt both a common message and individual messages. BEPM is necessary in applications where individual messages include information related to user's privacy. Recently, Fujii et al. suggested a BEPM that is extended from a public key broadcast encryption (PKBE) scheme by Boneh, Gentry, and Waters. In this paper, we point out that 1) Conditional Access System using Fujii et al.'s BEPM should be revised in a way that decryption algorithm takes as input public key as well, and 2) performance analysis of Fujii et al.'s BEPM should be done depending on whether the public key is transmitted along with ciphertext or stored into user's device. Finally, we propose a new BEPM that is transmission-efficient, while preserving O(1) user storage cost. Our construction is based on a PKBE scheme suggested by Park, Kim, Sung, and Lee, which is also considered as being one of the best PKBE schemes.