We propose a new approach to commutative watermarking-encryption (CWE). A permutation cipher is used to encrypt the multimedia data, which leaves the global statistics of the multimedia data intact. Therefore, any non-localized watermarking scheme that depends only on global statistics of the multimedia data can be combined with the permutation cipher to form a CWE scheme. We demonstrate this approach by giving a concrete implementation, which manipulates the global histogram to achieve watermark embedding/detection.