For the video stream copyright issues of high efficiency video coding (HEVC), a new zero-watermarking algorithm with robustness to re-quantization transcoding is proposed. Firstly, from statistics analysis about re-quantization transcoding, it is found that Coding Unit (CU) depths have strong stability and only a fraction of the depths would shift and almost shift to adjacent depths. Then, in order to increase the robustness of the depth characteristic, the CU depths are divided into two groups and mapped into two values ‘0’ and ‘1’. Finally, ‘xor’ operation is performed between the binary information encrypted and the copyright information scrambled by using the chaotic algorithm, the outcome with the timestamp acts as the ultimate registered zero-watermarking. Experimental results show that the proposed algorithm has strong robustness to re-quantization transcoding and other common signal attacks.