# A Lightweight Buyer-Seller Watermarking Protocol

Authors: Yongdong Wu; Hweehua Pang
Journal: Advances in Multimedia
 (2008)

---

## Abstract

The buyer-seller watermarking protocol enables a seller to successfully identify a traitor from a pirated copy, while preventing the seller from framing an innocent buyer. Based on finite field theory and the homomorphic property of public key cryptosystems such as RSA, several buyer-seller watermarking protocols (N. Memon and P. W. Wong (2001) and C.-L. Lei et al. (2004)) have been proposed previously. However, those protocols require not only large computational power but also substantial network bandwidth. In this paper, we introduce a new buyer-seller protocol that overcomes those weaknesses by managing the watermarks. Compared with the earlier protocols, ours isn times faster in terms of computation, where n is the number of watermark elements, while incurring only O(1/lN) times communication overhead given the finite field parameter lN. In addition, the quality of the watermarked image generated with our method is better, using the same watermark strength.


---

## Body

## 1. Introduction

The rapid development of computer networks and
increased use of multimedia data via the Internet have resulted in fast and
convenient exchange of digital information. With the ease of editing and
perfect reproduction, the protection of ownership of digital audio, image and
video materials become an important concern.
Copyright marking [1]
is a relatively new technique for hiding information in multimedia content with
the aim of tracing any traitor who redistributes the content illegally. Its
application is broad, for instance, copyright protection [2–4].In general, a watermarking scheme for traitor tracing
(a traitor is a legitimate buyer who subsequently
distributes his copy illegally) involves three
steps: first, an owner embeds into a cover image a watermark that identifies
the buyer. Secondly, if a suspicious image is found, the owner will detect the
watermark in the image. Once the watermark of a specific buyer is identified,
the owner will take the case to a court. Finally, the authority will
independently detect the watermark again in the image in question. If the
watermark is really found, the traitor is confirmed. A number of watermarking
protocols have been proposed in [5–9] to track down the distributors of illegal replicas.However, the accusation against the charged
distributor, who was the buyer in some earlier transaction, could be
objectionable because the seller also has access to the watermarked copies and,
hence, is able to release such a replica on his own to frame the distributor.To solve thecustomer's right problem [10] in the arbitration phase,
Memon and Wong [11] proposed an interactive buyer-seller protocol
(hereafter referred to as MW protocol) for invisible watermarking. In the
protocol, the seller does not know the watermark of the buyer, so the seller
cannot create copies of the protected content containing the buyer's watermark.
After the seller finds an unauthorized copy, the seller can identify the buyer
from a watermark in the unauthorized copy, and furthermore the seller can prove
this fact to a third party using a dispute resolution protocol. This prevents
the buyer from claiming that the unauthorized copy may have originated from the
seller himself. Memon and Wong proposed two embodiments in [11, 12] based on RSA [13] and ElGamal [14] crytosystems, respectively.As explained in [15], Memon's protocol has a weakness in that the seller
can frame a buyer with a higher-value image; this is known as
in [15]. To rectify the
problem, Lei et al. proposed another buyer-seller protocol (called LYTC
protocol hereinafter), which inserts a second watermark into the cover image.
The second watermark is generated by a watermark certification authority (WCA)
and sent to the buyer securely. As further observed in [15, page 1620], “the protocol (note: [11]) restricts
itself to the use of linear watermarking schemes and, hence, provides limited
flexibility in practice.” However, Lei et al. did not propose
any nonlinear method that would have allowed them to replace the asymmetric
cipher in their protocol with a much cheaper symmetric cipher. Zhang et al. [16] enhanced the
previous buyer-seller schemes with the same computational complexity so as to
defeat malicious arbitrator. Recently, Zhao et al. [17] follow the footprint of MW
scheme. It is not clear whether it is possible to design a nonlinear scheme
because the popular/standard asymmetric cryptosystems are in finite fields. For
example, other buyer-seller schemes such as [18] also employ asymmetric cipher. Hence the cover image
has to be separated and encrypted independently in the previous schemes.Neither MW nor LYTC is efficient in terms of
computation cost and communication overhead, because a lot of asymmetric cipher
operations are performed. As the buyer-seller protocol may be employed in an
online application, for example a paid Internet image gallery, response time is
important to user retention. In particular, the buyer may be using a mobile
device that has only limited computing power, battery life, and/or
communication bandwidth. Therefore, to be feasible in practice, an alternative
light-weight buyer-seller protocol is needed.Kuribayashi and Tanaka [19] proposed an anonymous
fingerprinting that improves the enciphering rate with interactive
Zero-knowledge proof. But it is computationally intensive and bandwidth
inefficient.In our proposed protocol, the seller asks a WCA to
generate two independent watermarksW and W^,
where W is used for identifying the buyer at the WCA side. Let V=W+βW^ where β is a predefined parameter to ensure
frame-proof. V is for the seller securely while W^ is for the buyer securely. To be able to
identify the buyer with V at the seller side, the seller embeds V into the cover image to produce a watermarked image. The buyer obtains the
watermarked image which she watermarks again with (βW^); this effectively reverses out βW^ and leaves the final copy that is watermarked
with W.
The identification step is the same as that in [5]. While the proposed protocol
may look similar to multiwatermarking schemes (e.g., [20, 21]) at first sight, our scheme
is really different from them in nature. Specifically, the watermarks in
multiwatermarking are independent and all the watermarked images are of high
quality. In contrast, the watermarks V and W^ in our scheme are dependent, and only the
final watermarked copy derived by the buyer is of high quality since one
watermark alleviates the effect of the other.The reminder of this paper is as follows. Section2
elaborates on our protocol. Section 3 analyzes the protocol in terms of frame
deterrence, performance comparison, and so forth. Section 4 describes
experiment results. Finally, Section 5 concludes the paper.


## 2. The Proposed Buyer-Seller Protocol

Denote the
original image asX={x1,x2,…,xn} and the watermarks for identifying a buyer as W={w1,w2,…,wn} and W^={w^1,w^2,…,w^n},
where n is the number of image elements (e.g., DCT
coefficients) to be manipulated. Our protocol is a light-weight buyer-seller
watermarking scheme that focuses on managing the watermarks. We do not design a
new embedding method, but simply employ a state-of-the-art scheme for embedding
the watermarks. In particular, the robust watermarking method Add-embedding in
[5] is used for
illustrating our proposed solution(1)yi=xi+αwi,i=1,2,…,n,where α is the watermark strength relating to
watermark robustness and invisibility. Y={y1,y2,…,yn} is the watermarked image.


### 2.1. Trust Model

In our
protocol, the trust model is the same as that in MW and LYTC. There are three
participants: seller, buyer, and WCA. The seller may attempt to frame an
innocent buyer with an image that is embedded with the buyer's watermark
(customer's), right problem or frame a traitor with a higher-value image
( .
(
: when a
pirated copy is found and the illegal distributor is identified, a higher-value
image enables the seller to seek much higher compensation from the illegal
distributor.) The buyer may attempt to disseminate
her legal copy without being identified ( ). In addition,
the WCA, who is a trusted third party, is assumed to manage the watermarks
secretly in the process of watermark generation, storage, delivery, and
arbitration.We also assume that the watermarks are independent and
normalized. That is to say, for any pair of watermarksW1 and W2, W1•W2=0 if W1≠W2,
otherwise 1, where • is the correlation operator (i.e., inner
product).For simplicity, for the rest of this paper we assume
that all the communication messages are authentic and that the cover signal is
an image.


### 2.2. Watermarking Protocol

In the watermarking process, the original image is
doubly-watermarked with the watermarks generated from a WCA. Figure1
summarizes the message flows in the watermarking process.Figure 1
Our
proposed watermarking protocol.Y1 is the seller's copy, and Y2 is the buyer's copy. ℰB(⋅) is a hybrid encryption [23] with the public key of
buyer. hS is the fingerprint of the original image, and
it is signed by the seller (the signature is not shown here).(1) Acting on information such as advertisement or
the seller's website, the buyerB decides to purchase an image. She thus sends a
request for the image.(2) The sellerS generates a fingerprint hS from the original image from the features of original image X (e.g., [22]). He then forwards the request of the buyer along
with hS to a WCA.(3) The WCA generates two independent watermark
sequencesW and W^ based on hS and buyer's description. Let V=W+βW^,
where β>1 is a predefined parameter that controls the
quality of the watermarked image at the seller side. The WCA sends the
ciphertext ℰB(αβW^) to the buyer, and ℰS(V) to the seller respectively.
(In order to speed up encryption/decryption, a
hybrid algorithm [23]
is used to produce ℰS(V):
WCA generates a random session key K,
then encrypts K with the seller's public key, and encrypts the
watermark V with the session key K.
A similar process is applied to produce
ℰB(W^).)(4) The seller decryptsℰS(V) to extract V. Next he inserts V into the cover image X to produce his watermarked copy Y1=X+αV=X+α(W+βW^). The seller sends Y1 and hS to the buyer.(5) The buyer decryptsℰB(αβW^) with her private key to obtain αβW^,
then she generates her watermarked copy(2)Y2=Y1−αβW^=X+α(W+βW^)−αβW^=X+αW.Afterwards, the buyer will
reconstruct the fingerprint hB of Y2.
Due to the invisibility property of watermarking, the original image is only
manipulated slightly. Hence, hS should match the fingerprint hB at a very high probability. Thus, if hS≠hB,
the buyer rejects the watermarked image Y2 and complains to the WCA.


### 2.3. Identification Protocol

Whenever the
seller finds a suspicious copyY=Y2+αD, where D is a distortion due to whatever
reasons, he tests the copy with the buyer's message V based on the
method in [5].
Specifically, he checks whether(3)γS=(Y−X)•Vα=(W+D)•(W+βW^)≈1+D•(W+βW^)≈1+ϵ>ηSfor some predefined threshold ηS,
where ϵ is a small number. Thus, the seller will
accuse the buyer if γS>ηS.
If there are more than one potential traitor, the seller may target the one
with the largest γS.


### 2.4. Dispute Resolving Protocol

In case the
buyer denies that an unauthorized copy originated from her version of the
image, the seller asks the WCA (for simplicity, we assume that the WCA is also
the arbitrator.) to resolve the dispute. Since the WCA calculates the
correlation value withW instead of V according to (4), smaller
noise is involved in WCA's detection. Hence the WCA's decision is
final:(4)γW=(Y−X)•Wα=(W+D)•W≈1+D•W≈1+ϵ′>ηW,where ϵ′ is small since D and W are
independent.


## 2.1. Trust Model

In our
protocol, the trust model is the same as that in MW and LYTC. There are three
participants: seller, buyer, and WCA. The seller may attempt to frame an
innocent buyer with an image that is embedded with the buyer's watermark
(customer's), right problem or frame a traitor with a higher-value image
( .
(
: when a
pirated copy is found and the illegal distributor is identified, a higher-value
image enables the seller to seek much higher compensation from the illegal
distributor.) The buyer may attempt to disseminate
her legal copy without being identified ( ). In addition,
the WCA, who is a trusted third party, is assumed to manage the watermarks
secretly in the process of watermark generation, storage, delivery, and
arbitration.We also assume that the watermarks are independent and
normalized. That is to say, for any pair of watermarksW1 and W2, W1•W2=0 if W1≠W2,
otherwise 1, where • is the correlation operator (i.e., inner
product).For simplicity, for the rest of this paper we assume
that all the communication messages are authentic and that the cover signal is
an image.


## 2.2. Watermarking Protocol

In the watermarking process, the original image is
doubly-watermarked with the watermarks generated from a WCA. Figure1
summarizes the message flows in the watermarking process.Figure 1
Our
proposed watermarking protocol.Y1 is the seller's copy, and Y2 is the buyer's copy. ℰB(⋅) is a hybrid encryption [23] with the public key of
buyer. hS is the fingerprint of the original image, and
it is signed by the seller (the signature is not shown here).(1) Acting on information such as advertisement or
the seller's website, the buyerB decides to purchase an image. She thus sends a
request for the image.(2) The sellerS generates a fingerprint hS from the original image from the features of original image X (e.g., [22]). He then forwards the request of the buyer along
with hS to a WCA.(3) The WCA generates two independent watermark
sequencesW and W^ based on hS and buyer's description. Let V=W+βW^,
where β>1 is a predefined parameter that controls the
quality of the watermarked image at the seller side. The WCA sends the
ciphertext ℰB(αβW^) to the buyer, and ℰS(V) to the seller respectively.
(In order to speed up encryption/decryption, a
hybrid algorithm [23]
is used to produce ℰS(V):
WCA generates a random session key K,
then encrypts K with the seller's public key, and encrypts the
watermark V with the session key K.
A similar process is applied to produce
ℰB(W^).)(4) The seller decryptsℰS(V) to extract V. Next he inserts V into the cover image X to produce his watermarked copy Y1=X+αV=X+α(W+βW^). The seller sends Y1 and hS to the buyer.(5) The buyer decryptsℰB(αβW^) with her private key to obtain αβW^,
then she generates her watermarked copy(2)Y2=Y1−αβW^=X+α(W+βW^)−αβW^=X+αW.Afterwards, the buyer will
reconstruct the fingerprint hB of Y2.
Due to the invisibility property of watermarking, the original image is only
manipulated slightly. Hence, hS should match the fingerprint hB at a very high probability. Thus, if hS≠hB,
the buyer rejects the watermarked image Y2 and complains to the WCA.


## 2.3. Identification Protocol

Whenever the
seller finds a suspicious copyY=Y2+αD, where D is a distortion due to whatever
reasons, he tests the copy with the buyer's message V based on the
method in [5].
Specifically, he checks whether(3)γS=(Y−X)•Vα=(W+D)•(W+βW^)≈1+D•(W+βW^)≈1+ϵ>ηSfor some predefined threshold ηS,
where ϵ is a small number. Thus, the seller will
accuse the buyer if γS>ηS.
If there are more than one potential traitor, the seller may target the one
with the largest γS.


## 2.4. Dispute Resolving Protocol

In case the
buyer denies that an unauthorized copy originated from her version of the
image, the seller asks the WCA (for simplicity, we assume that the WCA is also
the arbitrator.) to resolve the dispute. Since the WCA calculates the
correlation value withW instead of V according to (4), smaller
noise is involved in WCA's detection. Hence the WCA's decision is
final:(4)γW=(Y−X)•Wα=(W+D)•W≈1+D•W≈1+ϵ′>ηW,where ϵ′ is small since D and W are
independent.


## 3. Analysis of the Proposed Protocol

In this section, we analyze the proposed
protocol with regards to customer's right, traitor tracing, and performance.


### 3.1. Parameter Selection

The present
scheme has to select some parameters, especiallyα and β. α is used to control the quality of the
watermarked image generated by buyer, and β is used to prevent the seller from framing the
buyer. For the sake of security, both α and β are unknown to the buyer. Based on (8) in Section 3.2, β=10 is enough since the interference noise can
reduce the quality of watermarked image 20 dB. The other parameters for
threshold values (e.g., ηS for seller's detection and ηW for arbitrator's detection) can be decided
based on the security requirement.


### 3.2. Frame-Resilience

Since the
seller knows the imageY1 which is watermarked with both W and W^,
an accused buyer may argue that she has been framed by the buyer. Fortunately,
the watermarked image Y1 that the seller possesses is of low quality
due to the large amount of noise α(W+βW^),
so it is not worth to protect the watermarked image Y1 at all. To demonstrate the fidelity of the
watermarking, let us measure the distortion mean squared error (MSE) σ1 and σ2 of the watermarked images Y1 and Y2:(5)σ1=∥Y1−X∥2=∥α(W+βW^)∥2≈α2(1+β2),(6)σ2=∥Y2−X∥2=∥αW∥2≈α2. Therefore, the difference ΔPSNR in peak signal-to-noise ratio (PSNR) [24] between Y1 and Y2 is(7)ΔPSNR=PSNR2−PSNR1=10log⁡10σ1M−10log⁡10σ2M(8)=10log⁡10(α2(1+β2)M)−10log⁡10(α2M)=10log⁡10(1+β2)>20log⁡10β(dB), where M is the number of pixels in the image. To
achieve high robustness, Cox's watermarking method
in (1) is performed in frequency domain, thus, (5)
and (6) are calculated in frequency domain. However, PSNR is defined in spatial
domain. We are still able to calculate the difference in PSNR with (7) though,
because the MSE in spatial domain is equal to that in frequency domain. According
to (8), the quality of the watermarked image Y1 is much lower than that of Y2.
Therefore, the buyer is willing to execute the second embedding so as to reduce
the embedding noise. Since Y1 is of very low quality, the seller has no
reason to frame a buyer with such a poor-quality image.


### 3.3. Detecting Malicious Buyer

The
identification protocol in Section2.3 can detect a traitor if
she follows the protocol faithfully. However, a malicious buyer may attempt to
defeat the protocol by exploiting knowledge of the watermarked image Y1 and her watermark W^.
For instance, the buyer selects a random sequence Z over a distribution with mean 1, and generates
a new watermark αβW^′ which is close to αβW^:(9)Z={zi∣i=1,2,…,n},W^={w^i∣i=1,2,…,n},αβW^′=def{w^i′∣w^i′=zi(αβw^i),i=1,2,…,n}.Then, she
calculates(10)Y2′=Y1−αβW^′=X+α(W+βW^−βW^′).If the seller finds an illegal Y2′,
he will check it with (3) as(11)γS=(Y2′−X)•Vα=(W+βW^−βW^′)•(W+βW^)=1+β2−βW^′•(W+βW^)=1+β2−β2W^′•W^.Clearly, the correlation value γS is a random variable which depends on variable Z.
Since αβ is unknown to the buyer, zi should be selected by the buyer in a small
interval [1−ε,1+ε].
Therefore, the expected value of γS is(12)E(γS)=E(1+β2−β2W^′•W^)=1+β2−β2=1.In contrast, the expected
correlation valueγS′′ of an innocent buyer with watermark pair (W′′,W^′′) is(13)V′′=W′′+βW^′′,E(γS′′)=E((Y2′−X)•V′′α)=E((W+βW^−βW^′)•(W′′+βW^′′))=−E(W^′•(W′′+βW^′′))=0.Thus, a traitor can be
identified at a high probability, while an innocent buyer has a very low
probability of being accused wrongly.


### 3.4. Performance Comparison

In this subsection, we compare our protocol with the earlier protocols in [11, 15], in terms of computation
cost and communication overhead. Here, Mul-RSA denotes the protocols in [11, 15]. Table 1 gives the
comparative performance among the protocols. In the table, the first row
indicates the quality degradation of the final watermarked image Y2 with reference to the original image X.
Clearly, our method (in (6)) produces watermarked images of better quality than
that achievable by [11] or [15], with the same parameter α.Table 1
Performance comparison.
MW [11]LYTC [15]PresentMSEσ2α22α2α2Seller timetSn(Te+Tm)n(Te+Tm)TdBuyer timetBnTdnTd+TskTdWCA timetWnTenTe2TeSeller overheadCSnlNnlX+nlNnlX+lNWCA overheadCWnlNnlN2nlW+2lNTe:
the computation time for an asymmetric encryption.Td:
the computation time for an asymmetric decryption.Tm:
the computation time for a modular multiplicationTsk:
the computation time for generating a pair of public/private key.Tsk≫Td.n:
the number of DCT coefficients to be manipulated.lX:
the size of one image element xi.lN:
the size of a RSA modulus N.lW:
the size of one watermark element wi.In the previous schemes [11, 15], each element is processed
independently, thus the computation cost and overhead increase linearly with the
number n of the manipulated elements. In contrast, our
protocol which employs the hybrid scheme [23] has only one asymmetric operation at the
seller/buyer, and two asymmetric operations at the WCA. Correspondingly, the
communication overhead is almost constant. As a result, our scheme is much more
efficient in terms of computation cost (rows 3–5) and communication overhead
(rows 6-7). Roughly, the earlier schemes are n times slower while generating lN/lX times more network traffic.To illustrate the performance differences, we use
typical parameter settingslX=64, lN=1024, lW=32,
and n=10000.
Since symmetric cipher (e.g., AES/RC4) is much faster (over 1000 times) than
asymmetric cipher (e.g., RSA-1024), we can ignore the computation time of
symmetric encryption/decryption. According to the experiment in [25] with Pentium IV 2.1 GHz
processor running Windows XP, Te=0.18millisecond, Td=4.77millisecond, Tsk≈100Td=477millisecond.
As shown in Table 2, the protocols of [11, 15] are almost 360 times slower than our scheme at the
seller, and 10000 times slower at the buyer. The latter differentiation is
particularly critical for buyers that use portable devices with limited
computing and communication resources.Table 2
Example performance comparison
MW [11]LYTC [15]PresentSeller time (millisecond)180018004.77Buyer time (millisecond)47700481774.77WCA time (millisecond)180018000.36We should also clarify that the proposed protocol has
the disadvantage that the WCA (or seller) has to record all the watermarksW (or V, resp.) associated to each transaction, whereas in [15] only seller records the
watermarks, and WCA is memoryless.


## 3.1. Parameter Selection

The present
scheme has to select some parameters, especiallyα and β. α is used to control the quality of the
watermarked image generated by buyer, and β is used to prevent the seller from framing the
buyer. For the sake of security, both α and β are unknown to the buyer. Based on (8) in Section 3.2, β=10 is enough since the interference noise can
reduce the quality of watermarked image 20 dB. The other parameters for
threshold values (e.g., ηS for seller's detection and ηW for arbitrator's detection) can be decided
based on the security requirement.


## 3.2. Frame-Resilience

Since the
seller knows the imageY1 which is watermarked with both W and W^,
an accused buyer may argue that she has been framed by the buyer. Fortunately,
the watermarked image Y1 that the seller possesses is of low quality
due to the large amount of noise α(W+βW^),
so it is not worth to protect the watermarked image Y1 at all. To demonstrate the fidelity of the
watermarking, let us measure the distortion mean squared error (MSE) σ1 and σ2 of the watermarked images Y1 and Y2:(5)σ1=∥Y1−X∥2=∥α(W+βW^)∥2≈α2(1+β2),(6)σ2=∥Y2−X∥2=∥αW∥2≈α2. Therefore, the difference ΔPSNR in peak signal-to-noise ratio (PSNR) [24] between Y1 and Y2 is(7)ΔPSNR=PSNR2−PSNR1=10log⁡10σ1M−10log⁡10σ2M(8)=10log⁡10(α2(1+β2)M)−10log⁡10(α2M)=10log⁡10(1+β2)>20log⁡10β(dB), where M is the number of pixels in the image. To
achieve high robustness, Cox's watermarking method
in (1) is performed in frequency domain, thus, (5)
and (6) are calculated in frequency domain. However, PSNR is defined in spatial
domain. We are still able to calculate the difference in PSNR with (7) though,
because the MSE in spatial domain is equal to that in frequency domain. According
to (8), the quality of the watermarked image Y1 is much lower than that of Y2.
Therefore, the buyer is willing to execute the second embedding so as to reduce
the embedding noise. Since Y1 is of very low quality, the seller has no
reason to frame a buyer with such a poor-quality image.


## 3.3. Detecting Malicious Buyer

The
identification protocol in Section2.3 can detect a traitor if
she follows the protocol faithfully. However, a malicious buyer may attempt to
defeat the protocol by exploiting knowledge of the watermarked image Y1 and her watermark W^.
For instance, the buyer selects a random sequence Z over a distribution with mean 1, and generates
a new watermark αβW^′ which is close to αβW^:(9)Z={zi∣i=1,2,…,n},W^={w^i∣i=1,2,…,n},αβW^′=def{w^i′∣w^i′=zi(αβw^i),i=1,2,…,n}.Then, she
calculates(10)Y2′=Y1−αβW^′=X+α(W+βW^−βW^′).If the seller finds an illegal Y2′,
he will check it with (3) as(11)γS=(Y2′−X)•Vα=(W+βW^−βW^′)•(W+βW^)=1+β2−βW^′•(W+βW^)=1+β2−β2W^′•W^.Clearly, the correlation value γS is a random variable which depends on variable Z.
Since αβ is unknown to the buyer, zi should be selected by the buyer in a small
interval [1−ε,1+ε].
Therefore, the expected value of γS is(12)E(γS)=E(1+β2−β2W^′•W^)=1+β2−β2=1.In contrast, the expected
correlation valueγS′′ of an innocent buyer with watermark pair (W′′,W^′′) is(13)V′′=W′′+βW^′′,E(γS′′)=E((Y2′−X)•V′′α)=E((W+βW^−βW^′)•(W′′+βW^′′))=−E(W^′•(W′′+βW^′′))=0.Thus, a traitor can be
identified at a high probability, while an innocent buyer has a very low
probability of being accused wrongly.


## 3.4. Performance Comparison

In this subsection, we compare our protocol with the earlier protocols in [11, 15], in terms of computation
cost and communication overhead. Here, Mul-RSA denotes the protocols in [11, 15]. Table 1 gives the
comparative performance among the protocols. In the table, the first row
indicates the quality degradation of the final watermarked image Y2 with reference to the original image X.
Clearly, our method (in (6)) produces watermarked images of better quality than
that achievable by [11] or [15], with the same parameter α.Table 1
Performance comparison.
MW [11]LYTC [15]PresentMSEσ2α22α2α2Seller timetSn(Te+Tm)n(Te+Tm)TdBuyer timetBnTdnTd+TskTdWCA timetWnTenTe2TeSeller overheadCSnlNnlX+nlNnlX+lNWCA overheadCWnlNnlN2nlW+2lNTe:
the computation time for an asymmetric encryption.Td:
the computation time for an asymmetric decryption.Tm:
the computation time for a modular multiplicationTsk:
the computation time for generating a pair of public/private key.Tsk≫Td.n:
the number of DCT coefficients to be manipulated.lX:
the size of one image element xi.lN:
the size of a RSA modulus N.lW:
the size of one watermark element wi.In the previous schemes [11, 15], each element is processed
independently, thus the computation cost and overhead increase linearly with the
number n of the manipulated elements. In contrast, our
protocol which employs the hybrid scheme [23] has only one asymmetric operation at the
seller/buyer, and two asymmetric operations at the WCA. Correspondingly, the
communication overhead is almost constant. As a result, our scheme is much more
efficient in terms of computation cost (rows 3–5) and communication overhead
(rows 6-7). Roughly, the earlier schemes are n times slower while generating lN/lX times more network traffic.To illustrate the performance differences, we use
typical parameter settingslX=64, lN=1024, lW=32,
and n=10000.
Since symmetric cipher (e.g., AES/RC4) is much faster (over 1000 times) than
asymmetric cipher (e.g., RSA-1024), we can ignore the computation time of
symmetric encryption/decryption. According to the experiment in [25] with Pentium IV 2.1 GHz
processor running Windows XP, Te=0.18millisecond, Td=4.77millisecond, Tsk≈100Td=477millisecond.
As shown in Table 2, the protocols of [11, 15] are almost 360 times slower than our scheme at the
seller, and 10000 times slower at the buyer. The latter differentiation is
particularly critical for buyers that use portable devices with limited
computing and communication resources.Table 2
Example performance comparison
MW [11]LYTC [15]PresentSeller time (millisecond)180018004.77Buyer time (millisecond)47700481774.77WCA time (millisecond)180018000.36We should also clarify that the proposed protocol has
the disadvantage that the WCA (or seller) has to record all the watermarksW (or V, resp.) associated to each transaction, whereas in [15] only seller records the
watermarks, and WCA is memoryless.


## 4. Experimental Results

In the following experiments, we setα=20, β=10,
and the size of the test images to 200×200.
The normalized watermarks W and W^ are of length n=1000.
For each 8×8 DCT block, 16 coefficients are selected for
embedding. Thus, each watermark is embedded with the repetition r=(200×200/8×8)×16/n=10 to achieve robustness in detection.As our protocol aims to protect customer's right, it
employs Cox's embedding method [5] twice and hence produces the watermarked
images
Y1 and Y2.
The entire watermarking process includes the following steps. (1) The WCA
produces watermarks W and W^. (2) The seller performs DCT on the original image X, embedding V=W+βW^ into X in the DCT domain, IDCT, and
round IDCT output into integer
interval [0, 255] to produce Y1. (3) The buyer executes DCT on Y1,
embedding βW^ into Y1 in DCT domain, IDCT, and round IDCT output to
produce Y2.The following experiment results indicate that our
protocol has little side-effect to the underlying embedding method in terms of
robustness and invisibility.


### 4.1. Detecting “Honest” Traitor

To verify the
detection method in Section2.3, assume 400 watermark pairs (W,W^) are generated by the WCA, and assigned to
400 buyers. We generate a watermarked image Y2 with the watermarks of the 200th buyer
according to (3). The seller then calculates the correlation values γS with (3). Figure 2 illustrates the correlation
values at the seller. It shows clearly that the 200th buyer is the
traitor.Figure 2
Identifying the “honest” buyer by the
seller. The seller tests the buyers with the watermarkV according to
(3).Similarly, Figure3 shows the detection result of the
WCA with (4). The WCA confirms that the 200th buyer is indeed the
traitor.Figure 3
Identifying the “honest” buyer by the
WCA. The WCA traces the traitor with the watermarkW according to
(4).


### 4.2. Detecting Malicious Buyer

As mentioned in Section3.3, a malicious buyer may use (10) instead
of (3) to create a pirated copy. Assume that the buyer selects zi uniformly from (0.9,1.1) with mean 1. Since the watermark W^′ is close to W^,
her watermarked image will be of good quality. If such a pirated copy is found,
the seller calculates the correlation value γS based on (3). Figure 4 illustrates the
detection results by the seller for the traitor and innocent users. Similarly,
Figure 5 is the detection result γW from WCA according to (4).Figure 4
Identifying the malicious buyer by the
seller. The seller tests the buyers with the watermarkV according to
(3).Figure 5
Identifying the malicious buyer by the WCA.
The WCA traces the traitor with the watermarkW according to (4).As with “honest” traitors, the malicious buyer will
be identified by the seller and WCA according to Figures4 and 5. Therefore, the traitor is accused correctly while other buyers are not framed
despite the traitor modifying the watermarking method. This experiment result is
in concert with our analysis in (12) and (13).


### 4.3. Comparing PSNR of Watermarked Image

To demonstrate
the different quality of the watermarked images, we now test a group of images.
Figure6 shows the PSNRs of the watermarked images, and Figure 7 shows a
portion of the watermarked images Y1 and Y2.
It is clear that the PSNR of Y1 is 16 dB lower than that of Y2;
(due to integer transform, the experimental ΔPSNR is smaller than that in (8)), this confirms
that it is pointless for the seller to frame the buyer with Y1.Figure 6
PSNR ofY1 and Y2.The
watermarked images generated by the seller (left column) and buyer (right
column), respectively.
(a)
38.05 dB(b)
56.97 dB(c)
38.07 dB(d)
54.86 dB(e)
38.03 dB(f)
54.97 dB(g)
38.11 dB(h)
54.17 dB


## 4.1. Detecting “Honest” Traitor

To verify the
detection method in Section2.3, assume 400 watermark pairs (W,W^) are generated by the WCA, and assigned to
400 buyers. We generate a watermarked image Y2 with the watermarks of the 200th buyer
according to (3). The seller then calculates the correlation values γS with (3). Figure 2 illustrates the correlation
values at the seller. It shows clearly that the 200th buyer is the
traitor.Figure 2
Identifying the “honest” buyer by the
seller. The seller tests the buyers with the watermarkV according to
(3).Similarly, Figure3 shows the detection result of the
WCA with (4). The WCA confirms that the 200th buyer is indeed the
traitor.Figure 3
Identifying the “honest” buyer by the
WCA. The WCA traces the traitor with the watermarkW according to
(4).


## 4.2. Detecting Malicious Buyer

As mentioned in Section3.3, a malicious buyer may use (10) instead
of (3) to create a pirated copy. Assume that the buyer selects zi uniformly from (0.9,1.1) with mean 1. Since the watermark W^′ is close to W^,
her watermarked image will be of good quality. If such a pirated copy is found,
the seller calculates the correlation value γS based on (3). Figure 4 illustrates the
detection results by the seller for the traitor and innocent users. Similarly,
Figure 5 is the detection result γW from WCA according to (4).Figure 4
Identifying the malicious buyer by the
seller. The seller tests the buyers with the watermarkV according to
(3).Figure 5
Identifying the malicious buyer by the WCA.
The WCA traces the traitor with the watermarkW according to (4).As with “honest” traitors, the malicious buyer will
be identified by the seller and WCA according to Figures4 and 5. Therefore, the traitor is accused correctly while other buyers are not framed
despite the traitor modifying the watermarking method. This experiment result is
in concert with our analysis in (12) and (13).


## 4.3. Comparing PSNR of Watermarked Image

To demonstrate
the different quality of the watermarked images, we now test a group of images.
Figure6 shows the PSNRs of the watermarked images, and Figure 7 shows a
portion of the watermarked images Y1 and Y2.
It is clear that the PSNR of Y1 is 16 dB lower than that of Y2;
(due to integer transform, the experimental ΔPSNR is smaller than that in (8)), this confirms
that it is pointless for the seller to frame the buyer with Y1.Figure 6
PSNR ofY1 and Y2.The
watermarked images generated by the seller (left column) and buyer (right
column), respectively.
(a)
38.05 dB(b)
56.97 dB(c)
38.07 dB(d)
54.86 dB(e)
38.03 dB(f)
54.97 dB(g)
38.11 dB(h)
54.17 dB


## 5. Conclusion

Since the
buyer-seller protocols in [11, 15] employed the homomorphic property of public key
cryptosystem to encrypt each image element (i.e., DCT coefficient), they incur
large computation costs and increase the size of the intermediate (encrypted)
images (i.e., the first watermarked image). To overcome these shortcomings, we
propose a watermark management solution that preserves the functionality in
[11, 15], but is much more efficient
in terms of computation cost and communication overhead. Another advantage is
that watermarked images generated by our solution have significantly higher
quality than that achievable by [11] or [15].



---

*Source: 905065-2008-08-12.xml*