# Watermarking Protocols: A Short Guide for Beginners
## 3 Security Primitives
### Homomorphic Encryption  
Homomorphic encryption is defined as follows. Let \(\mathcal{M}\) be a set of plaintexts, and let \(\mathcal{C}\) be a set of ciphertexts corresponding to \(\mathcal{M}\). An encryption scheme \(E\) is said to be _homomorphic_ if it satisfies the following condition for any encryption key \(k\):  
\[\forall m_{1},m_{2}\in\mathcal{M},\quad E(m_{1}\odot_{\mathcal{M}}m_{2}) \gets E(m_{1})\odot_{\mathcal{C}}(m_{2})\]  
where \(\odot_{\mathcal{M}}\) and \(\odot_{\mathcal{C}}\) denote some operators in \(\mathcal{M}\) and in \(\mathcal{C}\), respectively, and \(\leftarrow\) means \"can be directly computed from\", that is, without any intermediate decryption [27]. The homomorphic encryption schemes used in watermarking protocols usually assume that both content and watermark can be represented in a block-wise form, \(X=\{x_{1},x_{2},\ldots x_{l}\}\) and \(W=\{w_{1},w_{2},\ldots w_{t}\}\), respectively. In particular, the elements of \(X\) can be either the original host signal samples or the features of the host signal computed by transforms such as, for instance, the discrete Fourier transform or the discrete cosine transform (DCT). The elements of \(W\) are usually binary values representing a fingerprinting anti-collusion code [5; 28; 29; 30; 31]. The watermarking protocols also assume that the encryption is a block-wise function \(E\) so that the encryption of a content \(X=\{x_{1},x_{2}\ldots x_{l}\}\) under the key \(k\) can be calculated as [7; 8]:  
\[E_{k}(X)=E_{k}(x_{1},x_{2}\ldots x_{l})=(E_{k}(x_{1}),E_{k}(x_{2})\ldots E_{k} (x_{l}))\]  
Likewise, they assume that watermark insertion can be expressed in the form:  
\[X\oplus W=\{x_{1}\oplus w_{1},x_{2}\oplus w_{2},\ldots x_{l}\oplus w_{l}\}=\hat {X}\]in which the symbol \(\oplus\) represents, in principle, an arbitrary function [4]. However, in practice, it is sufficient to consider only the asymmetric homomorphic encryption schemes that support addition and multiplication operations since such operations are functionally complete sets over finite sets [32]. In addition, such schemes also have to be \"probabilistic\" and \"semantically secure\". This ensures that the knowledge of a ciphertext does not provide any useful information on the plaintext to an adversary having only a reasonably restricted computational power represented by polynomial resources [27; 32]. The result is, therefore, represented by the so-called multiplicatively and additively homomorphic encryption schemes. The former ensure that [33]  
\[\forall m_{1},m_{2}\in\mathcal{M},\quad E(m_{1}\cdot m_{2})=E(m_{1})\cdot E(m _{2})\]  
whereas the latter ensure that [34; 35]  
\[\forall m_{1},m_{2}\in\mathcal{M},\quad E(m_{1}+m_{2})=E(m_{1})\cdot E(m_{2})\]  
Such schemes can be used to apply a watermark, for a fixed key \(k\), according to the following expression:  
\[E_{k}(X\oplus W)=E_{k}(X)\oplus E_{k}(W)=E_{k}(\bar{X})\]  
Homomorphic encryption schemes have changed the way watermarking protocols are designed. They have been used to prevent content providers from having exclusive rights on their contents sold to buyers since, in the early watermarking protocols, content providers took charge of embedding watermarks into the distributed contents. On the contrary, homomorphic encryption schemes enable all the parties involved in the protocols to directly operate on the encrypted contents. More precisely, performing operations on the plaintexts before encryption is equivalent, for a fixed key, to carrying out operations on the corresponding ciphertexts after encryption. For example, consider the watermark insertion algorithm based on the spread spectrum technique described in [4] and represented by the formula:  
\[\bar{x}=x+\alpha(2b-1)s\]  
where \(x\) is a host signal feature obtained by calculating the cosine discrete transform (DCT), \(\bar{x}\) is the corresponding watermarked feature, \(b\in\{0,1\}\) is the bit to embed, \(s\) is the component of a spreading sequence, and \(\alpha\) is a scaling factor that controls the watermark's strength.