# Watermarking Protocols: A Short Guide for Beginners
## 4 Performance Issues  
The requirements listed in Section 2 provide researchers with a guide to designing watermarking protocols able to protect the copyrights of digital content distributed on the web. The protocols are implemented as web applications that embed personalized protections into distributed content [1], as reported in Section 1. This means that protections are applied \"on-the-fly\" when contents are purchased by buyers (see Figures 1 and 2). Therefore, such applications have to be run by systems provided with adequate resources if they want to implement competitive, real-time services in the current web context. Figure 1: Buyer and seller watermarking protocol based on asymmetric fingerprinting and homomorphic encryption. More precisely, the computing and memory resources needed to implement a watermarking protocol determine its efficiency and scalability; the former mainly depends on the processing time taken to protect content, whereas the latter depends on how such a time increase is related to the increment in the number of the buyers purchasing content. Efficiency should be maximized so as to achieve a near-linear growth of scalability. In this regard, it is worth noting that, in past years, searching for secure watermarking protocols led researchers to design protection schemes mainly based on homomorphic primitives (see Figures 1 and 2). This resulted in rather inefficient protocols, since homomorphic primitives require that each sample of protected content is individually encrypted. In fact, the public-key individual encryption of samples causes a high computing overhead as well as an expansion of data, which also has a specific impact on communication bandwidth. The performance problems caused by homomorphic public-key encryption algorithms particularly affect watermarking protocols based on the interaction scheme shown in Figure 1, in which sellers implement the most resource-intensive and time-consuming operations. For example, consider the tests conducted in [26; 59] on images of 1024 \(\times\) 1024 pixels. Each image is watermarked by applying the QIM algorithm reported in Section 3.2. The watermarked features are extracted by the lowest frequency DCT coefficients, excluding the DC value, of the 8 \(\times\) 8 DCT blocks composing the images. The embedded watermarks are 128-bit strings. Each image is encrypted using the Paillier cryptosystem with a public key size of 1024 bits [35]. Therefore, in an image of 1024 \(\times\) 1024 pixels, the size of the host signal is 1,048,576 DCT coefficients. This means that the Paillier cryptosystem requires 1,048,576 multiplication exponentiations on a 2048 bit group to protect an image according to the expression (2). However, by adopting the optimization strategy called \"composite-embedding strategy\" [26; 59], it is possible to group several signal features into a single 2048-bit group and to perform basic linear operations on them. As a consequence, the number of multiplication exponentiations can be reduced by a factor of about 100 in the tests documented in [26; 59]. Under the above assumptions, let \(T^{1}_{sel}\) denote the computing time spent by the seller to protect a digital content. Let \(T^{1}_{buy}\) denote the computing time spent by the buyer to obtain the same content in its final protected form. According to the scheme in Figure 1, the total computation cost \(T^{1}_{total}\) needed to protect a content can be expressed as \(T^{1}_{total}\approx T^{1}_{sel}+T^{1}_{buy}\) since it can be approximated by the sum of three main contributions corresponding to the phases 4, 5, and 9 indicated in Figure 1. These phases consist of public key encryption,  
Figure 2: Buyer and seller watermarking protocol based on asymmetric fingerprinting and joint watermarking. watermark insertion, and public key decryption. In fact, the remaining computation costs to complete content protection can be ignored since they are related to operations on short bit strings [26; 59].