The large size of video data makes it desirable to be stored and processed in the cloud. To provide security and privacy for the data in the cloud, the video data must be stored in encrypted form. It is also necessary to perform data hiding to avoid the leakage of video content. This paper proposes a novel method of embedding additional data in H.264/AVC video bit streams to meet the privacy preserving requirements of cloud data management. This method proposes three processes namely: H.264/AVC video encryption, Embedding of encrypted data and extraction of original data. Depending upon the property of H.264/AVC codec, the code words of I-frames and P-frames are encrypted with stream ciphers. The data to be embedded into the encrypted video is also encrypted by Chaos encryption technique and hidden into the video by bit replacement method. Data extraction is done both in encrypted domain and in decrypted domain. Experimental results show that the proposed method preserves file size, whereas degradation in video quality caused by data embedding is less.