Nancy Awad
email: nancy.awad@ua.edu.lb

A L Bechara

Bouna

Jean-François Couchot

Laurent Philippe
email: laurent.philippe@univ-fcomte.fr

Bechara Al Bouna
email: bechara.albouna@ua.edu.lb

Jean-Francois Couchot
email: jean-francois.couchot@univ-fcomte.fr

SEE PROFILE

Keywords: Disassociation, cover problem, data privacy, set-valued, privacy preserving

Disassociation introduced by Terrovitis et al. is a bucketization based anonimyzation technique that divides a set-valued dataset into several clusters to hide the link between individuals and their complete set of items. It increases the utility of the anonymized dataset, but on the other side, it raises many privacy concerns, one in particular, is when the items are tightly coupled to form what is called, a cover problem. In this paper, we present safe disassociation, a technique that relies on partial-suppression, to overcome the aforementioned privacy breach encountered when disassociating set-valued datasets. Safe disassociation allows the k m -anonymity privacy constraint to be extended to a bucketized dataset and copes with the cover problem. We describe our algorithm that achieves the safe disassociation and we provide a set of experiments to demonstrate its efficiency.

Introduction

Privacy preservation is a key concern in data publishing where individual's personal information must remain protected under all circumstances. This sounds straightforward, but it is somehow difficult to achieve. The AOL search data leak in 2006 (BZ06) is an explicit example that shows the consequences of a unsupervised data publishing. The query logs of 650k individuals were released after omitting all explicit identifiers. They were later withdrawn due to multiple reports of attackers linking individuals to their sensitive records. Alternatively, providing a "complete" privacy over the data requires sacrifices in terms of utility, in other words, usefulness of the data (Sam01, Swe02, MGKV06, XT06, DMNS06). Hence, it is pointless to publish datasets that do not provide valuable information. A suitable trade-off between data utility and privacy must be achieved. The point is to provide not only a value anonymization technique, but instead a dataset anonymization technique, that hides/anonymizes the link between individuals and their sensitive information, and, at the same time, keeps the dataset useful for analysis. When publishing a set-valued dataset (e.g., shopping and search items) it is important to pay attention to attackers that try intentionally to link individuals to their sensitive information. These attackers may be able to single out an individual's complete record/itemset by associating data items from the dataset to their background knowledge. The example in Figure 1(a) shows a set-valued dataset T consisting of 6 records r 1 ,. . . ,r 6 , which are itemsets linked to individuals 1, . . . , 6 respectively. For instance, r 1 : {a, e} can be interpreted as individual 1 has searched for item a and item e. If an attacker knows that individual 1 has searched for items d and e, he/she will be able to link 1 to his record r 2 . Several techniques (Sam01, Swe02, XT06, LLZM12, DCdVFJ + 13, WWFW16, WDL18) have been defined in the literature to anonymize the dataset and cope with this particular association problem. Anonymization by disassociation (TMK08, LLGT14,LLGDT15) is a bucketisation technique (XT06,LLZM12,DCdVFJ + 13) that keeps the items without alternation/generalization but separates the records into clusters and chunks to hide their associations. More specifically, disassociation transforms the original data into k m -anonymous clusters of chunks to ensure that an attacker who knows up to m items cannot associate them with less than k records. First, disassociation divides the dataset horizontally, creating clusters of records with similar frequent items. In Figure 1(a), the item a has the highest number of occurrences in the records; thus, all records containing the item a are added to the cluster. Next, disassociation divides the clusters vertically, creating inside each cluster k m -anonymous record chunks of items, and one item chunk containing items that appear less than k times. Figure 1 (b) shows the result of disassociation with only one cluster, namely T * , containing 2 record chunks R C 1 , and R C 2 and no item chunk. Both R C 1 and R C 2 are 2 2 -anonymous. That is, an attacker who knows any two items about an individual will be able link them to at least two records from the dataset.

In a previous work (BaBNG16), the disassociation technique has been evaluated and found to be vulnerable to what is called, a cover problem. This cover problem provides attackers with the ability to associate itemsets in consequent record chunks with individuals' records, and compromises the disassociated dataset. Figure 1(c) highlights all datasets T 1 , T 2 , and T 3 that could be reconstructed from the disassociated dataset T * by associating records from different record chunks. Suppose now the attacker knows that an individual has searched for items d and e , {d, e}. In such a case, he/she can remove T 2 from the possible reconstructed dataset and will be able to link every record containing d and e with certainty to {a, b, c} from the two remaining reconstructed datasets leading to a privacy breach. This paper extends the previous work (BaBNG16) by providing a theoretical and practical solution to this cover problem. It introduces a privacy preserving technique to safely disassociate a set-valued dataset and address this cover problem. This method is further denoted as safe disassociation. Our contributions are summarized as follows:

-We define the privacy guarantee for safe disassociation and provide the appropriate algorithm to achieve it. -We investigate the efficiency of safe disassociation and its impact on the utility of aggregate analysis and the discovery of association rules. The rest of the paper is organized as follows. Section 2 presents an overview of some of the related works in set-valued dataset anonymization . In Section 3, we describe the formal model of disassociation and discuss the cover problem that makes disassociation vulnerable. We define safe disassociation in Section. 4. Experimental evaluations of this method is presented in Section 5. Finally, we conclude in Section 6 and present outlines for future work.

Related Work

Anonymization techniques can be divided into several categories, namely categorization, generalization, and bucketization, detailed hereafter. With categorization (JPX + 14, CLZ + 16, WDL18), attributes are classified into several categories with respect to their sensitivity: identifying, sensitive or nonsensitive. On the opposite, all the data in this current work are considered to be grouped into sets whose items have the same level of sensitivity; the items combined together are sensitive and therefore only the link between the individual and their corresponding items must be protected. Generalization techniques (Sam01, Swe02, MGKV06) create homogeneous subsets by replacing values with ranges wide enough to create ambiguity. Reducing the extent of generalization, and thus decreasing the information loss is critical to preserving the usefulness of the data. In (HN09), only a local generalization is applied whereas in (FW10) a clustering based technique is implemented to minimize the abstraction. On the opposite, initial data in this current work are not generalized to ensure privacy or even modified. Bucketization techniques (XT06,CVF + 10,BPW11) are valuable due to their ability to keep the values intact. Identifiable links between items are hidden by separating the attributes of the data. Under this category lies the disassociation technique (TMLS12,LLGT14,LLGDT15,BLLL17) that works on clustering the data and hiding identifiable links in each cluster by separating the attributes. Unfortunately, disassociation has shown to be vulnerable to a privacy breach when the items are tightly coupled. It is the ability of an attacker to link his/her partial background knowledge represented by at most m items that he/she is allowed to have, according to the privacy constraint k m -anonymity, with certainty to less than k distinct records in a disassociated dataset. Differential privacy (DMNS06) is an anonymization technique that adds noise to the query results. It is based on a strong mathematical foundation that guarantees that an attacker is unable to identify sensitive data about an individual if his/her information were removed from the dataset. Unlike differential privacy, this disassociation based work does not distinguish between sensitive and non-sensitive attributes and is capable to retrieve viable and trustful information that has not been altered nor modified. The authors in (ZHZ + 15) defined cocktail a framework that uses both disassociation to anonymize the data for publishing as well as differential privacy to add noise on data querying. In spite of the originality of the idea, their technique subsumes the drawbacks of both disassociation and differential privacy; as it is vulnerable to the cover problem and releases questionable information.

Background

To be self-content, this section recalls the basis of disassociation (Sec. 3.1 and Sec. 3.2) introduced in (TMLS12). Next (Sec. 3.3), it exhibits a class of privacy breach called cover problem inherent to this anonymization technique already sketched in (BaBNG16) showing its repercussion on data privacy.

Data model

Let D = {x 1 , ..., x d } be a set of items (e.g., supermarket products, query logs, or search keywords). Any subset I ⊆ D is an itemset (e.g., items searched together). Let T = {r 1 , ..., r n } be a dataset of records where each r i ⊆ D for 1 ≤ i ≤ n is a record and r i is associated with a specific individual i of a population. Let R T be a subset of records in T . Both T and R have the multiset semantic, which can contain more than one instance for each of its elements.

With such notations, s(I, T ) is the number of records in T that contain all the elements in I. More formally, it is defined by the following equation

s(I, T ) = |{r ∈ T | I ⊆ r}| (1)
By extension s(T ) = s( / 0, T ) and s(R T ) = s( / 0, R T ) are the number of records in T and R T respectively. an item chunk in a disassociated cluster R C a record chunk in a disassociated cluster δ maximum number of records allowed in a cluster n number of records in T

Disassociation

Disassociation works under the assumption that the items should neither be altered, suppressed, nor generalized, but at the same time the resulting dataset must respect the k m -anonymity privacy constraint (TMK08). Formally, k m -anonymity is defined as follows:

Definition 1 (k m -anonymity). Given a dataset of records T whose items belong to a given set of items D. The dataset T is k m -anonymous if ∀I ⊆ D such that |I| ≤ m, the number of records in T that are superset of I is greater than or equal to k, i.e., s(I, T ) ≥ k.

Given a dataset T , applying k m -disassociation3 on T produces a dataset T * composed of q clusters, each divided into a set of record chunks and an item chunk,

T * = {R 1 C 1 , . . . , R 1 Ct , R 1 Y }, . . . , {R q C 1 , . . . , R q Cv , R q T } such that ∀R i C j ∈ T * , R i C j is k-anonymous, where,
-R i C j represents the itemsets of the i th cluster that are contained in its j th record chunk. -R i T is the item chunk of the i th cluster containing items that occur less than k times. The example in Figure 1(b) shows that the 2 2 -disassociated dataset contains only one cluster with two 2 2 -anonymous record chunks. We thus have T

* = {R C 1 , R C 2 } with R C 1 = {{a}, {a, b, c, d}, {a, b, c, d}, {a, b, c, d}, {a, b, c, d}, {a, b}}, and R C 2 = {{e}, {e}}.
According to (TMLS12) and by construction, k m -disassociation guarantees all the produced record chunks are k m -anonymous. This can be better explained in this example as: any combination of two items (m = 2) from Figure 1(a), for example {a, b}, is found at least in two records (k = 2) in the record chunk, thus satisfying k manonymity in Figure 1(b). However, to ensure the privacy of a disassociated dataset, k m -anonymity has to be guaranteed in one of the valid reconstructed datasets of T * since an attacker can produce all of them, provided he/she knows T * , k, and m (TMLS12). This privacy guarantee is formally expressed as follows:

Definition 2 (Disassociation Guarantee). Let G be the inverse transformation of T * with respect to a k m disassociation, i.e., the set of all possible datasets whose k m disassociation would yield T * . Disassociation guarantee is established if for any I ⊆ D such that |I| ≤ m, there exists T . ∈ G(T * ) with s(I, T . ) ≥ k.

The Disassociation Guarantee ensures that for any individual with a complete record r, and for an attacker who knows up to m items of r, at least one of the datasets reconstructed by the inverse transformation contains the record r k times or more. That is, the record r, as all other records, exists k times in at least one of the inverse transformations. The authors in (BaBNG16) demonstrate that this disassociation guarantee is not enough to ensure privacy. They show that whenever a disassociated dataset is subject to cover problem, a privacy breach might be encountered. In the following section, we briefly present the cover problem.

Cover Problem

Let us recall, from Subsection 3.2 that the disassociation technique hides itemsets that occur less than k times in the original dataset for a given m items, by 1) dividing them into k m -anonymous sub-records in record chunks and 2) ensuring that all the records reconstructed by the inverse transformation are k m -anonymous in at least one of the resulting datasets. A cover problem is defined by the ability to associate one-to-one or one-to-many items in two distinct record chunks, from the same cluster, in the disassociated data. Without loss of generality, we focus on one cluster R = {R C 1 , . . . , R C t , R T } of T * resulting from a k m -disassociation. Formally, the cover problem is defined as follows.

Definition 3 (Cover Problem). Let I j be the set of items in R C j , I j = {x ∈ R C j }. If there exists an item z ∈ I j such that the support of I j is equal to the support of the singleton {z} in R C j , i.e.,

s(I j , R C j ) = s({z}, R C j ), (2)
the cluster R, and the dataset T * as a consequence, are subject to a cover problem.

∀ z ∈ I j , if z satisfies equation ( 2), z is denoted as covered item. The set of all the covered items is denoted as L j , which is contained in I j . ∀x ∈ I j , such that x / ∈ L j , x is not a covered item, then x is denoted as a covering item. Obviously, the set of covering items is I j \ L j . For instance, in Figure 1

(b), I 1 = {a, b, c, d}. The support of the itemset I 1 in R C 1 , which is s(I 1 , R C 1 )
, is equal to 4. In turn, it is equal to the minimum support of the items in I 1 , which, in our example, is s({c}, R C 1 ) = 4. Therefore, we say that the item c is covered by the items a and b. Similarly, the item d is also covered by the items a and b. Intuitively, a privacy breach occurs if an attacker is able to link m items from his/her background knowledge, to less than k records in all the datasets reconstructed by the inverse transformation. More subtle is when these records contain the same set of items in all the reconstructed datasets, thus linking more than m items to the individual, or worse leading to a complete de-anonymization by linking, with certainty, the complete set of items to the individual. We will show in the following that this privacy breach might occur whenever the dataset is subject to a cover problem. Formally speaking: Lemma 1. Let T * be a k m -disassociated dataset subject to a cover problem. The disassociation guarantee is thus not valid for m ≥ 2.

Proof. Let T * be a k m -disassociated dataset subject to a cover problem. The following set I j = {x|x ∈ R C j } is thus not empty and there exists a covered item z ∈ I j such that s(I j , R C j ) = s({z}, R C j ). This means that each record r of R C j that contains z includes also I j . Suppose now that the attacker's background knowledge is the set {z, y} where y is an item in another record chunk R C l . By contradiction, suppose that the disassociation guarantee is valid, i.e., z and y are associated together in k records in at least one of the datasets T . , reconstructed by the inverse transformation of T * . Since z is a covered item, it appears in each record r defined above. The item y will also be associated k times with all the items in I j .

While this is correct from a privacy perspective, it cannot be considered for disassociation. Items, y, z and any covering item x ∈ I j are indeed considered as k m -anonymous, and, therefore, should have been allot to the same record chunk R C j according to disassociation4 , whereas z and y are respectively items of chunks R C j and R C l by hypothesis.

Safe Disassociation

In this section, we show that a safe disassociation can be achieved, to ensure that a released/published dataset is no longer subject to a cover problem. This privacy guarantee is formally defined as follows:

Definition 4 (Safe Disassociation). Let G be the inverse transformation of T * with respect to a k m -disassociation, whose set of items is D. The dataset T * is safely disassociated if ∀I ⊆ D such that |I| ≤ m, there exists T . ∈ G(T * ) with s(I, T . ) ≥ k and T . is not subject to a cover problem.

Safe disassociation ensures that at least a dataset T . reconstructed by the inverse transformation of T * :

contains k records for an itemset of size m or less, abiding to the k m -anonymity privacy constraint, and the dataset T . has no covered items.

In the following, we show how this safe disassociation can be achieved by applying a partial suppression on a disassociated dataset.

Achieving safe disassociation with partial suppression

In previous works dedicated to privacy preservation (JPX + 14), partial suppression is used to ensure that no sensitive rules can be inferred with a confidence greater than a certain threshold. Here, we assume that partial suppression can achieve disassociation safely regardless the sensitivity of the data; all items are considered with the same level of sensitivity. Moreover, using partial suppression, we minimize the information loss with respect to our privacy guarantee. Unlike global suppression that removes the items in question from all the records, partial suppression remains more efficient in terms of utility.

Partial Suppression. Applying the following rules until the hypothesis is established produces a safely disassociated dataset.

-Hypothesis: Let I, as defined in Definition 3, be the itemset of the record chunk R C j that suffers from a cover problem.

-Preconditions: Let card = |I| 2 be the count of records that are going to be partially suppressed from R C j , and let δ be the maximum number of records allowed in the cluster. Partial suppression is applicable over R C j when:

|R C j | ≤ δ -2 (3) s(I, R C j ) ≥ k + min(card, m) (4)
-Rules:

1. Create a random partition I 1 ∪ I 2 .... ∪ I card of I where each set I j is composed of two items, but I card , which is a singleton if the cardinality of I is odd. 2. Create two empty sets L 1 and L 2 , known as the ghost records. 3. For each I i ∈ I, successively: (a) suppress I i from a record r i ∈ R C such that r i = I and (b) add the items x 1 and x 2 from I i to respectively L 1 and L 2 :

L 1 = L 1 ∪ {x 1 } and L 2 = L 2 ∪ {x 2 } 4. Add the two ghost records L 1 and L 2 to R C j
By definition, a cover problem is the ability to link one-to-one or one-to-many items in two record chunks. This arises when there exists x ∈ I j such that s(I j , R C j ) = s({x}, R C j ). The aim of partial suppression is to suppress items in such a way as to ensure that s(I j , R C j ) remains different than s({x}, R C j ), thus s(I j , R C j ) = s({x}, R C j ). 3) and ( 4) play an important role in ensuring that the safe disassociation is preserved throughout the process of partial suppression. Precondition (3) is defined to keep the size of the clusters bounded by the maximum cluster size δ. In fact, in the horizontal partitioning, no additional records are added to the cluster if the maximum cluster size is reached. As a consequence, the record chunks created from the vertical partitioning have a cardinality less or equal to δ. Hence, to add the two ghost records L 1 and L 2 to a record chunk, its cardinality must be less than δ -2. Precondition (4) is defined to preserve the k m -anonymity constraint in the record chunk. Partial suppression modifies card occurrences of I, and, therefore, leaves s(I, R C j )card unmodified. Thus, we have:

Discussion on preconditions Preconditions (

s(I, R C j ) = s(I, R C j ) -card ≥ k + min(m, card) -card (5)
Let X = {x 1 , x 2 , ...x m } be a subset of I, X ⊂ I. There are two cases to consider, depending on whether m is greater than card or not.

if card ≤ m: s(I, R C j ) is greater than k according to inequality (5). We have s(X, R C j ) ≥ s(I, R C j ) ≥ k. This means that k m -anonymity is satisfied. if m < card: s(I, R C j )card records are kept unchanged by the partial suppression. After applying step 3a in partial suppression, we notice that s(X, R C j ) ≥ cardm. This is because the smallest value, cardm, is obtained when each item in X belongs to a distinct pair I j . In this situation, m records do not associate items x 1 , x 2 ,. . . ,x m together. As a result, the following applies according to hypothesis (4).

s(X, R C j ) ≥ s(I, R C j ) -card + card -m ≥ s(I, R C j ) -m ≥ k + min(card, m) -m ≥ k
Lemma 2. Given a record chunk R C j , we say that partial suppression achieves safe disassociation on R C j if preconditions (3) and (4) are verified.

Proof. Let R C j be the result of applying the partial suppression rules on the record chunk R C j . The itemset I is randomly partitioned in card (where card = |I| 2 )

disjoint subsets of cardinality equal to 2, and possibly one singleton if |I| is odd.

Those subsets are used successively to perform partial suppression. Since the preconditions are verified, it is straightforward to prove that due to the rules of partial suppression, the support of any item in R C j remains the same. ∀x ∈ I, x is suppressed from a record r i = I and then added randomly to one of the ghost records L 1 or L 2 , therefore:

s({x}, R C j ) = s({x}, R C j ). (6)
However, what has been partially suppressed is the association between any two items x and y in I. Two case scenarios can arise:

items x and y belong to the same subset I i of I. Thus, x and y are suppressed once from the same record r i , and added to L 1 and L 2 respectively. This ensures that they cannot be associated again in the ghost records:

s({x, y}, R C j ) = s({x, y}, R C j ) -1 = s({x}, R C j ) -1 = s({y}, R C j ) -1
items x and y belong to two different subsets of I, I i and I j respectively. The association between x and y is lost twice since these items were suppressed from two distinct records in R C j , then: s({x, y}, R C j ) is equal to s({x, y}, R C ) -2 (resp. to s({x, y}, R C ) -1) if x and y are added to the different ghost records L 1 and L 2 (resp. if x and y are added to the same ghost records). In both cases, we have:

s({x, y}, R C j ) < s({x}, R C j ) < s({y}, R C j )
Due to the inequality S(I, R C j ) ≤ s({x, y}, R C j ) and ∀x, y in I we have s(I, R C ) < s({x}, R C ), which concludes the proof.

To illustrate how a cover problem can be eliminated through partial suppression, let us consider the example in Figure 2(a). Both items c and d are covered items in the disassociated dataset T * . After applying partial suppression, in Figure 2(a), two subsets I 1 = {a, b} and I 2 = {c, d} are created after randomly partitioning I = {a, b, c, d}. From I 1 and I 2 , two ghost records are created L 1 = {a, d} and L 2 = {b, c}, containing one of the items from each suppressed subsets. Next, these two ghost records are added to R C 1 . We illustrate, in Figure 2(b), all possible reconstructed datasets of the final disassociated dataset. Now, if an attacker knows that a specific individual has searched for items {d, e} (considered as the attacker's background knowledge), he/she will be able to associate them with three possible records {c, d, e}, {a, d, e} and {a, b, c, d, e}. While these extra associations are considered noise, for the sake of privacy, they added ambiguity to the result since the attacker cannot link {d, e} to a particular record. In the next section, we will study and evaluate the impact of partial suppression on the utility of the dataset.

T * R C 1 R C 2 a e £ a £ b c d e a b £ c £ d a b c d a b c d a b T * R C 1 R C 2 a e c

Experimental Evaluation

In keeping with the previous work (BaBNG16), we elaborate our experiments on two datasets, the BMS1 and the BMS2, which contain click-stream E-commerce data. Table 2 shows the properties of the datasets. The aim of the experiments can be summarized as follows:

-Evaluating the privacy breach in the disassociated dataset.

-Evaluating the utility loss w.r.t the suppression of items (or their occurrences). -Studing the loss in associations when disassociating and safely disassociating a dataset. -Evaluating the performance of partial suppression.

Privacy and utility metrics

5.1.1 Privacy Evaluation Metric (PEM) represents the number of vulnerable record chunks in a disassociated dataset. In fact, we consider that every

RLM = ∑ ∀x∈D (s({x}, T * ) -s({x}, T )) ∑ ∀x∈D (s({x}, T * ))
where,

s({x}, T * ) represents the support of the item x in the disassociated dataset T * , and s({x}, T ) represents the support of the item x in the safely disassociated dataset T .

Relative Association Error (RAE) evaluates how likely two items

remain associated together in an anonymized dataset (TMLS12). In fact, using RAE, we are able to evaluate the information loss due to the anonymization of the dataset (whether it is disassociated or safely disassociated). Formally, RAE is defined as follows:

RAE = s({x, y}, T ) -s({x, y}, [T * |T ]) AV G(s({x, y}, T ), s({x, y}, [T * |T ]))
where, s({x, y}, T ) represents the support of items {x, y} in the original dataset T , the disassociated dataset T * , or the safely disassociated dataset T .

Experimental results

In this section, we present the results of the conducted experiments, evaluating privacy and data utility over the safely disassociated dataset.

Evaluating the privacy breach

We consider that a privacy breach occurs if an attacker is able to link m items, which he/she already knows about an individual, to less than k records in all the datasets reconstructed by the inverse transformation. In this test, we study the impact of the cover problem on the privacy of the disassociated dataset. In fact, we consider that a potential privacy breach exists whenever a cover problem is identified in a record chunk regardless of the background knowledge of the attacker. It is typically a strong attacker (BaBNG16) who is able to link any two items to a specific individual. Hence, we determine the following:

the relationship between the PEM and both, k and m.

the relationship between the PEM and the maximum cluster size δ.

Varying k and m: we vary k and m from 2 to 6. For each value, we compute the PEM to evaluate how the privacy constraint remains satisfied in the record chunks. Figure 3 shows the results of the evaluation. When k increases in both datasets BMS1 and BMS2, the PEM decreases from 46% to 30% in BMS1 and from 56% to 39% in BMS2. While varying k affects the PEM, varying m has no noticeable impact on the PEM in both datasets. This is not surprising since, due to the cover problem, any two items known to the attacker can lead to a privacy breach. Varying δ: we vary δ from 10 to 60. For each value, we compute the PEM to evaluate how the privacy constraint remains satisfied in the record chunks. The results in Figure 4 show that the PEM increases from 17% to 52% in BMS1 and from 26% to 57% in BMS2. This means that with more records in the cluster, the higher the chances are to compromise the dataset due to the cover problem.

Evaluating the number of suppressed items

In this test, we evaluate the number of items to be suppressed to safely disassociate a dataset. We note that the record chunks that do not comply with preconditions (3) and ( 4) in partial suppression, for the sake of privacy, their items are completely suppressed. We use the RLM to estimate this loss of items. We vary the maximum cluster size δ from 10 to 60 and compute, for each value, the RLM. Figure 5 shows the results of our evaluation. It is not surprising that BMS2 is more susceptible to partial suppression since it is more vulnerable to the cover problem due to its size, as noted in the previous test (Figure 4). In addition, in both datasets, when the maximum cluster size δ increases, we notice an increase in the RLM. This is actually consistent with the fact that the more vulnerable the record chunks are, the more items will be suppressed. Overall, the 20% suppressions of items represent an acceptable trade-off between privacy and utility, especially that, with safe disassociation, we release real datasets without modifying the items.

Evaluating the association error

In this test, we evaluate the error in associations, which is the result of dividing the records into chunks after the partitioning process. Eventually, some of the itemsets will be separated and their items will be stored into different chunks. This adds noise to the dataset since the support of associations between these separated items might be higher in the reconstructed datasets. This leads to this error in associations that can be calculated using the RAE, which is the relative difference between the support of the association of an itemset in the original dataset and the anonymized dataset (XT06). Again, we vary the maximum cluster size δ from 10 to 60 and compute, for each value, the RAE on disassociated and safely disassociated datasets. The results in Figure 6 shows that the RAE is higher in a safely disassociated dataset. It is not surprising because, with safe disassociation, we suppress some items to prevent the privacy breach. However, the difference between RAE in safe disassociation and disassociation remains acceptable; varying between 1% for BMS1 and 0.1% for BMS2.

Performance evaluation

We compare the performance of our algorithm with different dataset size. The datasets used in this experiment are formed from BMS1 and BMS2. We vary, in the xaxis, the number of records with {358k, 149K, 100K, 80K, 50k, 30k 10k}; and the maximum cluster size δ is fixed to 30. Figure 7 shows an increase in the run time with the increase of the dataset size.

Conclusion

Disassociation is an interesting anonymization technique that is able to hide the link between individuals and their complete set of items while keeping the items 0 1 2 3

•105 50 100 Dataset Size Run Time (msec) Fig. 7. Performance evaluation without generalization. In a previous work (BaBNG16), disassociation was considered vulnerable due to a cover problem. Basically, it is the ability to associate one-to-one or one-to-many items in two subsequent record chunks of the disassociated data. In this paper, we propose safe disassociation to solve this problem. We use partial suppression to achieve safe disassociation by suppressing some of the items that lead to a cover problem from subsequent record chunks. In the experiments, we show that the vulnerability of a disassociated dataset depends on the size of the cluster. We evaluate the utility of a safely disassociated dataset in terms of 1) the number of items to be suppressed to achieve safe disassociation, and 2) the additional noisy associations added due to item suppression and partitioning. The results of our evaluations showed that an acceptable trade-off between privacy and utility is met. In future works, we aim at maximizing the utility of a safely disassociated dataset by modifying the clustering algorithm to keep user-defined itemsets associated together.

  Fig. 1. Disassociation leading to a cover problem

  i.e. a dataset anonymized using the disassociation technique T . a dataset reconstructed by cross joining the itemsets of the record chunks in a cluster from the disassociated dataset r a record (of T ) which is set of items associated with a specific individual of a population I an itemset included in D s(I, T ) support of I in T i.e. the number of records in T that are superset of I R a cluster in a disassociated dataset, formed by the horizontal partitioning of T R T

Fig. 2 .

 2 Fig. 2. Eliminating a cover problem with partial suppression

Fig. 3 .

 3 Fig. 3. Evaluating the PEM while varying k and m

Fig. 4 .

 4 Fig. 4. Evaluating the PEM while varying δ

Fig. 5 .

 5 Fig. 5. Evaluating the RLM while varying δ

Fig. 6 .

 6 Fig. 6. Evaluating the RAE while varying δ

Table 1

 1 recalls the basic concepts and notations used in the paper.

Table 1 .

 1 Notations used in the paper

Table 2 .

 2 Datasets properties RC represents the total number of record chunks in T .5.1.2 Relative Loss Metric (RLM)determines the relative number of suppressed occurrences of items with partial suppression. Formally,

	Dataset # of distinct individuals # of distinct items count of items' occurrences
	BMS1 59602	497	149639
	BMS2 77512	3340	358278
	record chunk that is subject to a cover problem is a vulnerable record chunk. We
	formally define our PEM as:
		PEM = vRC RC
	where,
	-vRC represents the number of vulnerable record chunks in T , the disassoci-
	ated dataset, and
	-

In what follows, we use k m -disassociation to denote a dataset that is disassociated and satisfies k m -anonymity.

Vertical partitioning creates k m -anonymous record chunks.

www.inmobiles.net

Acknowledgments

This work is funded by the InMobiles company 5 and the Labex ACTION program (contract ANR-11-LABX-01-01). Computations have been performed on the supercomputer facilities of the Mésocentre de calcul de Franche-Comté. Special thanks to Ms. Sara Barakat for her contribution in identifying the cover problem.


Makram W Hatoum
email: makram.hatoum@univ-fcomte.fr

Rony Darazi
email: rony.darazi@ua.edu.lb

Jean-François F Couchot
email: jean-francois.couchot@univ-fcomte.fr

Normalized Blind STDM Watermarking Scheme for Images and PDF Documents robust against Fixed Gain Attack

Keywords: Digital watermarking, Data hiding, Portable Document Format, Robustness

Spread Transform Dither Modulation (STDM), a special case of Quantization Index Modulation (QIM), has been widely used in digital watermarking. STDM has good performance in robustness against re-quantization and random noise attacks, but it is largely vulnerable to the Fixed Gain Attack (FGA). In addition to digital images and videos watermarking applications, copyright protection for digital text such as Portable Document Format (PDF) has received particular attention and interest. In this paper, we modify the STDM watermarking scheme by making the quantization step dependent on the original samples during the embedding process and on the watermarked samples during the decoding process to resist the FGA attack and enhance the robustness against the Additive White Gaussian Noise (AWGN) attack and JPEG compression attack in both the spatial domain and frequency domain regardless of the source of elements used as cover work. Experimentations have been conducted distinctly on digital images and text PDF documents. The tested images were watermarked with a uniform fidelity, where SSIM is fixed to 0.982 and 0.953. Our approach achieves significant robustness against the FGA attack with an improvement of 98% in terms of Bit Error Rates (BER) compared to traditional STDM. As for the AWGN attack, an improvement of 21% is shown. The proposed method also presents robustness against a variety of filtering and geometric attacks, while preserving a high level of transparency.

Introduction

Nowadays, digital contents such as images, videos, and documents are getting more and more commonly distributed over the internet than before with increasing size and values. With the advancement of internet technologies, unauthorized users authenticate, duplicate and distribute digital contents in an illegal way. Therefore, digital watermarking was used for copyright protection, access control, authentication, and broadcast monitoring [START_REF] Boney | Digital watermarks for audio signals[END_REF][START_REF] Cox | Digital watermarking and steganography[END_REF][START_REF] Jalil | A review of digital watermarking techniques for text documents[END_REF][START_REF] Langelaar | Watermarking digital image and video data. A state-of-the-art overview[END_REF][START_REF] Potdar | A survey of digital image watermarking techniques[END_REF]. The watermarking schemes are categorized as a substitutive class known by Quantization Index Modulation (QIM) introduced by Chen and Wornell [START_REF] Chen | Quantization index modulation: a class of provably good methods for digital watermarking and information embedding[END_REF] and an additive class known by Spread Spectrum (SS) which was introduced by Cox et al. [START_REF] Cox | Secure spread spectrum watermarking for multimedia[END_REF][START_REF] Cox | Secure spread spectrum watermarking for images, audio and video[END_REF][START_REF] Malvar | Improved spread spectrum: A new modulation technique for robust watermarking[END_REF]. Part of the mentioned algorithms was performed in the spatial domain, where the watermark is embedded, for example, in the pixel intensity of an image or the character position in a text, while other watermarking algorithms were performed in the frequency domain using the DCT, DFT, DWT, and SVD [START_REF] Barni | A DCT-domain system for robust image watermarking[END_REF][START_REF] Hsu | Hidden digital watermarks in images[END_REF][START_REF] Xia | A multiresolution watermark for digital images[END_REF], where the watermark is embedded in the frequency transform of the image. Spread Transform Dither Modulation (STDM), a special case of Quantization Index Modulation (QIM), has been widely used for digital image watermarking, and in previous work we have applied the STDM watermarking scheme in PDF documents for copyright protection with a tradeoff between the transparency and robustness [START_REF] Bitar | Blind digital watermarking in PDF documents using Spread Transform Dither Modulation[END_REF]. STDM achieves high robustness against additive noise attack, but it is largely vulnerable to the FGA attack [START_REF] Hatoum | Blind Image Watermarking using Normalized STDM robust against Fixed Gain Attack[END_REF]. In this type of attack, the received signal is indeed multiplied by a gain factor ρ, which scales the watermark vector and shifts it away from its original quantization cell. Therefore, the decoded watermark would be different from the embedded one. In this paper, we modify the STDM watermarking scheme to resist the FGA attack, to enhance the robustness against other types of attacks such as AWGN attack and JPEG compression, and improve its effectiveness for images and PDF documents.

Related Work

Below are a number of presented solutions that have been proposed using perceptual models based on Watson's model [START_REF] Watson | DCT quantization matrices visually optimized for individual images[END_REF] to improve the fidelity and to provide robustness against the FGA attack. Watson provided a perceptual model for computing the slack associated with each DCT coefficient within an 8×8 block. These slacks are further used in watermarking schemes to determine the quantization step size during the embedding and decoding process. Li et al. [START_REF] Li | Using perceptual models to improve fidelity and provide invariance to valumetric scaling for quantization index modulation watermarking[END_REF] have modified the QIM watermarking scheme based on Watson's perceptual model. They applied the DCT on the original image, in order to compute the quantization step size ∆ based on the slacks, which are evaluated by:

s[i, j, k] = max(t L [i, j, k], |C 0 [i, j, k]| 0.7 t L [i, j, k] 0.3 ), (1)
In the equation above, C 0 [i, j, k] is the coefficient at the position (i, j) of the k th block of the cover work, and t L [i, j, k] is the luminance masked threshold given as:

t L [i, j, k] = t[i, j](C 0 [0, 0, k]/C 0,0 ) 0.649 , (2)
where C 0 [0, 0, k] is the DC coefficient of the k th block, C 0,0 is the average of all the DC coefficient in the image, and t[i, j] is the smallest magnitude of the corresponding DCT coefficient in a block presented in a frequency sensitive table [START_REF] Cox | Digital watermarking and steganography[END_REF]. ∆ is modified based on the slacks and a constant factor G, which can be adjusted to alter the watermark strength. This method ameliorates the robustness against the FGA attack, but still vulnerable against AWGN attack and misses the experiments against varieties of attacks such as JPEG compression. Zhu, X. [START_REF] Zhu | Image-adaptive spread transform dither modulation using human visual model[END_REF] introduced an image-adaptive STDM performed in the DCT domain in order to resist the FGA attack. In this method, ∆ is computed based on Watson's model during the embedding process as:

∆ = 2L -1 4 D L l=1 s l . (3)
D is the perceptual distance between the watermarked signal and the host signal, and the slack s l is computed using the contrast making presented in (1) at the position (i, j) of the k th block. The slacks s have been rearranged in a vector of length L to compute ∆. During the detection process, ∆ is modified as:

∆ = ∆ C 0,0 C 0,0 ,
where C 0,0 and C 0,0 are the mean of all the DC coefficients of the original and watermarked image. This method is not robust against JPEG compression and low-pass filtering as all the DCT coefficients were used to embed the watermark.

In [START_REF] Li | Improved spread transform dither modulation using a perceptual model: robustness to amplitude scaling and JPEG compression[END_REF], Li et al. proposed the STDM-MW-SS watermarking scheme in order to provide invariance to the FGA attack while improving the fidelity constraint. The DCT transform is applied to the original image, and the slacks of each 8×8 block are computed based on Watson's model to determine the projection vector and the quantization step size ∆. Given a length L vector of DCT coefficients and its corresponding vector of modified slacks, ∆ is computed as follows:

∆ = G f × L l=1 S M l . (4)
G f is a global factor used to adjust the watermarking strength, and S M l is the modified slack at the position (i, j) of the k th block, computed as follows:

S M [i, j, k] = max(t M L [i, j, k], |C 0 [i, j, k]| 0.7 t M L [i, j, k] 0.3 ) t M L [i, j, k] = t L [i, j, k](C 0,0 /128),
This method has been tested only against JPEG compression and FGA attack. Yu et al. [START_REF] Yu | Adaptive spread-transform dither modulation using an improved luminance-masked threshold[END_REF] presented an Adaptive STDM (ASTDM) based on Watson's model. The slacks are computed during the embedding process as in [START_REF] Alizadeh-Fahimeh | Using steganography to hide messages inside PDF files[END_REF], and the luminance masking is modified during the extraction process as:

t L [i, j, k] = t[i, j] C 0 [0, 0, k] C 0,0 0.7 C 0,0 C 0,0 ,
∆ i is computed for the i th bit of the watermark as:

∆ i = 2λ|s i | k i 2 /| ki |,
where k i is a private subvector, s i presents a vector containing the slacks of the i th 8×8 block, λ ∈ (0, 1) is used to adjust the embedding strength, |s i | and | ki | are the absolute mean values of s i and k i , and k i 2 is the l 2 -norm of k i . An extra intensity sequence of the image must be transmitted to the detector to provide resistance to FGA attack. In the STDM-Step projection (STDM-SP) scheme that was proposed by Li et al. [START_REF] Li | Step-projection-based spread transform dither modulation[END_REF], ∆ is selected for each host vector based on Watson's model, and performed in the DCT domain. The slack vector s of the host signal is projected into a random vector p. ∆ is given as:

∆ = 2s T p,
in which s presents the slack vector of the host signal, and p is the positive projection vector. In this sense, the original image is divided into 8×8 blocks, and the DCT is performed to each block to form the slack vector S i , based on the position of the host vector elements in the 8×8 block. STDM-SP-wm selects the slack from the frequency sensitivity table [START_REF] Cox | Digital watermarking and steganography[END_REF] which has been modified as:

T m = T × C 0,0 µ ,
where C 0,0 is the mean intensity of the image and µ=512. This method was not examined with related work. Wan et al. [START_REF] Wan | Logarithmic spread-transform dither modulation watermarking based on perceptual model[END_REF] proposed a Logarithmic STDM (LSTDM-WM) watermarking scheme based on the perceptual model. According to a logarithmic function, the projection of the host signal x onto a random vector p is transformed as:

F (x T p) = ln(1 + µ x T p C 0,0 ) ln(1 + µ) ,
in which the parameter µ is selected based on:

µ < C 0,0 |x T p| .
∆ is modified as:

∆ = ln(1 + 2s T p × µ C 0,0 ) ln(1 + µ) ,
where s presents the distortion visibility thresholds which is calculated based on Watson's perceptual model. This method is complex. Jiang et al. [START_REF] Jiang | Adaptive spread transform QIM watermarking algorithm based on improved perceptual models[END_REF] proposed an adaptive spread transform QIM (ST-QIM) watermarking algorithm based on improved perceptual models. They proposed four different implementations of perceptual modal and combined it with ST-QIM to form an adaptive quantization watermarking schemes. Those methods were not compared with related works.

Wang et al. [START_REF] Wang | An improved AQIM watermarking method with minimum-distortion angle quantization and amplitude projection strategy[END_REF] presented an improved AQIM watermarking method with minimumdistortion angle quantization and amplitude projection strategy. They proposed a new angle quantization function, which is given by:

Q(θ) =              ∆ θ + ∆ 2 ∆ if m = 0 ∆ θ ∆ + ∆ 2 if m = 1
, where ∆ = 2π/k, and k is a positive integer number. This method is implemented in the wavelet transform domain of grayscale images.

In [START_REF] Wan | Improved logarithmic spread transform dither modulation using a robust perceptual model[END_REF], Wan et al. proposed an improved logarithmic spread transform dither modulation using a robust perceptual model. They introduced a new measurement of the edge, strength, and pixel intensity to calculate the slacks at the watermark embedder and watermark detector. They make a new quantization step size as:

∆ = ln(1 + 2s T p 128 ) ln(1 + γ) ,
where γ is a positive parameter defining the compression level.

Those modified watermarking schemes are applied in the frequency domain and could only be implemented on images to resist the FGA attack since they are dependent on the luminance and contrast making of images. Most of the proposed methods are studied based on the DCT transform, i.e. the DCT coefficients are quantized rather than the pixel values.

A different watermarking scheme, Rational Dither Modulation (RDM), has been proposed by Perez-Gonzalez et al. [START_REF] Pérez-González | Rational dither modulation: A high-rate data-hiding method invariant to gain attacks[END_REF] in which the feature signal for quantization is constructed using the ratio of the previously generated watermarked sample and the current host sample as:

y k = g(y k-1 k-L )Q m x k g(y k-1 k-L ) , (5)
where Q m represents the standard quantization operation, y k-1 k-L denotes the set of past signals (y k-L ... y k-1 ), and the function g() has the property that for any gain factor ρ > 0:

g(ρy) = ρg(y).

The function g() include the L p vector-norm:

g(y k-1 k-L ) = 1 L L i=1 |y k-i | p 1 p .
The decoding is performed by using the minimum euclidean distance rule as:

m = arg min m∈{-1,1} z k g(z k-1 k-L ) -Q m z k g(z k-1 k-L ) . (6)
Whereas RDM has proved to be robust against the FGA attack, it still limited against the additive noise attack due to the variation of the quantization step size.

Aside from digital images, electronic documents such as PDF files are widely exchanged over the internet, and they are subject to illegal copying and redistribution due to the effortless copying and distributing. Therefore, it has become more important to protect PDF files from any malicious user [START_REF] Hatoum | Blind PDF Document Watermarking Robust Against PCA and ICA Attacks[END_REF]. Few methods are proposed for hiding information in PDF files. Castiglione et al. [START_REF] Castiglione | Security and privacy issues in the Portable Document Format[END_REF] noted that PDF documents are not immune to some privacy issues. It is possible in PDF document to retrieve the previous version and display information not meant to be published, and it is also possible to trigger events when a PDF document is opened or printed. Therefore, the scientific communities have to consider such issues that might disclose the fairness of the review process of scientific papers. In [START_REF] Feng | A Systematic Method on PDF Privacy Leakage Issues[END_REF], Feng et al. conducted a series of studies of the privacy leakage issues of PDF documents. The hidden private information is revealed with documents, and that will provoke privacy leakage. This methodology is helpful for users to check whether their PDF documents include privacy information prior to transmitting it via the Internet. Vellasques et al. [START_REF] Vellasques | A high throughput system for intelligent watermarking of bi-tonal images[END_REF] presented an intelligent watermarking technique based on particle swarm optimization for bi-tonal (or binary) images. They intended a watermarking application of streams of documents images. The performance remains to be tested. Por et al. [START_REF] Por | Information hiding: A new approach in text steganography[END_REF] proposed an approach in information hiding using inter-paragraph and inter-word spacing. The main drawback of this method is that the embedded message can be easily destroyed. Lee et al. [START_REF] Lee | A new approach to covert communication via PDF files[END_REF] presented an alternative space coding method to embed a secret message in a PDF file. An opponent could easily remove or modify the embedded message by replacing the ASCII codes. Alizadeh et al. [START_REF] Alizadeh-Fahimeh | Using steganography to hide messages inside PDF files[END_REF] proposed two different algorithms using a TJ method. One of them has a lower security level, and the other one has a lower capacity level. Kuribayash et al. [START_REF] Kuribayashi | Data Hiding for Text Document in PDF File[END_REF] used the space lengths between characters as watermarking space, and the watermark is embedded using the DM-QIM watermarking scheme. This method still missing the experimental tests of robustness. In previous work [START_REF] Bitar | Blind digital watermarking in PDF documents using Spread Transform Dither Modulation[END_REF], we proposed a blind digital watermarking scheme for PDF documents. This method consists of embedding the watermark in the x-coordinates of a group of characters, taking into consideration the transparency and robustness trade-off.

Contribution

Except for the RDM, all the watermarking schemes mentioned above are based on Watson's perceptual model to resist the FGA attack. Therefore, those methods are dedicated for image watermarking and could not be applied on other types of signal. As for the RDM watermarking scheme, it achieves a good performance against the FGA attack with a certain limitation against the additive noise attack. RDM does not benefit from the property of the spreading vector, and the quantization step size is a variable step quantizer, whose size is a function of several past watermarked samples. For that, the attacking noise has more influence on the decoding quantization step size. In this paper, we modified the traditional STDM watermarking scheme by making the quantization step dependent on the original samples during the embedding process and the watermarked samples during the decoding process to resist the FGA attack and enhance the robustness against AWGN attack, JPEG compression attack, and variety of filtering and geometric attacks. Moreover, we affirm that this approach could also be used as a blind watermarking scheme for PDF documents. We have applied our approach on the grayscale images and PDF documents in the spatial domain and frequency domain and compared its performance with other proposed methods. Our approach is more flexible as it is not dependent on the perceptual model to achieve the robustness against the FGA attack, and any element can be used as support to embed the watermark. The rest of this paper is organized as follows: Section 3 recalls some backgrounds on STDM. The proposed N-STDM method is presented in Section 4. Section 5 provides a theoretical analysis of STDM and N-STDM. Experiments on real images are shown in Section 6. Section 7 presents the experiments on PDF documents. The findings and discussion are shown in Section 8. Finally, Section 9 provides our conclusion and future work.

Background

STDM [START_REF] Chen | Quantization index modulation: a class of provably good methods for digital watermarking and information embedding[END_REF][START_REF] Darazi | Secure and HVS-adaptive exhibition Spread Transform Dither Modulation watermarking for Digital cinema[END_REF][START_REF] Darazi | Applying Spread Transform Dither Modulation for 3Dmesh watermarking by using perceptual models[END_REF]] is a special case of QIM where the quantization occurs entirely in the projection of the host signal x onto a normalized projection vector p. This way, the embedding-induced distortion spreads into a group of samples rather than one. The embedded function is as follows:

y = x + (Q m (x T p, ∆) -x T p)p = x + round x T p -d m ∆ ∆ + d m -x T p p, (7)
where ∆ represents the quantization factor, round() is the rounding value to the nearest integer, and d m denotes the dither level based on the message bit m ∈ {0, 1}:

d 0 = - ∆ 4 and d 1 = ∆ 4 . (8)
The detection can be performed with a minimum distance decoder to extract the embedded message as follows:

m = arg min m∈{0,1} | y T p -Q m (y T p, ∆) | . (9)
Therefore, it achieves high robustness against re-quantization attack and additive noise attack, yet it is still unsafe against the FGA attack. In this type of attack, the received signal is indeed multiplied by a gain factor ρ, which scales the watermark vector and shifts it away from its original quantization cell; More formally, when the FGA attack is applied on the watermarked signal y, it becomes:

z = ρ • y,
and m will be decoded as follows: The quantification factor

m = arg min m∈{0,1} | ρ • y T p -Q m (ρ • y T p, ∆) | .
Q m (ρ • y T p, ∆) is indeed equal to round ρ•y T p-d m ∆ ∆ + d m which may be different from round y T p-d m ∆ ρ • ∆ + ρ • dm and consequently not equal to ρ • Q m (y T p, ∆).
Therefore, as the decoded message can be different from the embedded one, the robustness against the FGA attack cannot be obtained. After analyzing the performance of STDM against the FGA attack and re-quantization attack, Bartolini et al. [START_REF] Bartolini | Performance analysis of ST-DM watermarking in presence of nonadditive attacks[END_REF] concluded that STDM has more superior robustness against the re-quantization attack than the FGA attack. They argued that even though the values of gain factor ρ are close to 1, the error probability will still be excessively high.

Proposed N-STDM Method

The traditional STDM watermarking scheme has good performance in robustness against re-quantization and random noise attacks, but it is largely affected by the FGA attack. This is mainly due to the fact that when the host signal is scaled by the global factor ρ, the quantization step used for decoding is not scaled simultaneously. This problem will be solved if we scale the quantization step in the same way the watermarked signal is scaled. Obviously, it is difficult to straightforwardly estimate the global factor ρ, but if the quantization step size becomes dependent on the watermarked samples, it will be scaled concurrently with those samples. Therefore, in the proposed watermarking scheme, N-STDM, we have modified the embedding and decoding functions of the traditional STDM as illustrated in Fig. 1. We have computed the norm value x based on the host signal to be used during the embedding process as:

y = x + x Q m x T p x , ∆ -x T p p m ∈ {0, 1}. ( 10
) x = (|x 1 | 1 u + |x 2 | 1 u + ... + |x n | 1 u ) u , ( 11
)
where n is the length of the extracted vector from the cover elements, |x n | is the absolute value of element x n , and x is a norm function that could be expressed as a l 2 -norm when u = 1/2 and l 1 -norm when u = 1 etc. (the influence of x against the FGA attack while varying u is detailed in Section 6).

Algorithm 1 N-STDM Embedder

Input: I, m, p I: Original image of size n = N × N m: Binary watermark of size s = S × S p: Normalized projection vector of length L = n/s Choose ∆ and u; j = 0; X ← reshape (I, n, 1); W ← reshape (m, s, 1);

for i = L + 1 : L : n + 1 do j++; w = W (j); x = X(i -L : i -1); no = Power(Sum(Power(x, 1/u)), u); q=Quantizer(x T p, w, ∆); y(i -L : i -1) = x + (no * q -x T p)p; end for Output = y T
The detection is performed with a minimum distance decoder to extract the embedded message as follows:

m = arg min m ∈{0,1} ỹ -y Q m ỹ y , ∆ . (12)
where ỹ = y T p.

As a result, when performed, the FGA attack s.t. z = ρ.y will not affect the minimum distance decoder :

m = arg min m∈{0,1} | z -z Q m z z , ∆ | = arg min m∈{0,1} | ρ • ỹ -ρ • y Q m ρ • ỹ ρ • y , ∆ | = arg min m∈{0,1} | ρ ỹ -y Q m ỹ y , ∆ | . (14)
Therefore, the non-linear impact of the ρ factor in the quantization is now linear and consequently will not affect the process of decoding the message. Algorithm 1 details the embedding process of a watermark into an image using the proposed N-STDM. The complexity is directly proportional to n; order of growth is n. In a worst-case scenario, the statement will be executed n times. The time complexity is linear O(n).

Theoretical Analysis of STDM and N-STDM

This section provides a theoretical proof of the correction of the STDM and N-STDM watermarking schemes. In other words, we have verified that when a message is embedded into a host signal and when there is no attack, the message would be extracted without any error.

The quantizer Q m of the STDM watermarking scheme is given by:

Q m (s, ∆) = round s -d m ∆ ∆ + d m , (15)
where:

d m = - ∆ 4 + m. ∆ 2 . ( 16
)
Let us first recall the definition of the rounding function.

round(x) = x + 0.5 if x is postive or null x -0.5 otherwise
In all what follows and without loss of generality, we consider s-d m to be positive. There exists q s ∈ N and r s ∈ R + , 0 ≤ r s < ∆ such that:

s -d m + ∆ 2 = q s ∆ + r s , or equivalently s -r s + ∆ 2 = q s ∆ + d m . (17)
In such a case,

Q m (s, ∆) = round s -d m ∆ ∆ + d m = q s ∆ + d m = s -r s + ∆ 2 . ( 18
)
Let m ∈ {0, 1} be the bit to be embedded into the host vector x = (x 1 , . . . , x n ) with respect to the normalized projection vector p = (p 1 , . . . , p n ) and a parameter ∆. Let y be the vector that contains the watermark.

Correction Proof of STDM

In the original STDM algorithm:

y = x + Q m (x T p, ∆) -x T p p m = arg min m ∈{0,1} y T p -Q m y T p, ∆ , thanks to eq. (18), Q m (x T p, ∆) = x T p -r x T p + ∆ 2 so that y = x -(r x T p )p + ∆ 2 p,
this allows deducing

y T p = x T p -r x T p + ∆ 2 .
Let us then evaluate

Q m y T p, ∆ = Q m x T p -r x T p + ∆ 2 , ∆ .
First of all:

Q m x T p -r x T p + ∆ 2 , ∆ = Q m q x T p ∆ + d m , ∆ thanks to eq. (17) = round q x T p ∆ + d m -d m ∆ ∆ + d m = round    q x T p ∆ + ∆ 2 (m -m ) ∆    ∆ + d m = round q x T p + m -m 2 ∆ + d m
We then have

m = arg min m ∈{0,1} y T p -Q m y T p, ∆ = arg min m ∈{0,1} x T p -r x T p + ∆ 2 -round q x T p + m -m 2 ∆ -d m ) = arg min m ∈{0,1} q x T p ∆ + d m -round q x T p + m -m 2 ∆ -d m = arg min m ∈{0,1} q x T p + m -m 2 ∆ -round q x T p + m -m 2 ∆ = arg min m ∈{0,1} q x T p + m -m 2 -round q x T p + m -m 2 (19)
Therefore, we conclude that the extracted message m depends on m and m . Obviously, if m = m , we have to evaluate q x T p -round(q x T p ) which is null since q x T p is a natural number. Otherwise, i.e., when m and m are distinct, let us first suppose that m -m 2 = 0.5. In this case, q x T p + 0.5 -round(q x T p + 0.5) = q x T p + 0.5 -(q x T p + 1) = 0.5. The last case, i.e, when m -m 2 = -0.5 is similar and is thus omitted. The minimum value is thus obtained when m = m . Without any attack, m is thus m.

Correction Proof of N-STDM

In the following equations, . is consider as the norm of elements.

Theorem 1 Let y be the watermarked host:

y = x + x Q m x T p x , ∆ -x T p p.
Let m be the retrieved watermark bit, which is defined by:

m = arg min m ∈{0,1} y T p -y Q m y T p y , ∆ . (20)
Without any attack, m is the same as m.

Proof: First of all, let us identify y T p:

y T p = x + x Q m x T p x , ∆ -x T p p T p = x T p + x Q m x T p x , ∆ -x T p p T p.
Since p is a normalized vector, p T p is 1. Thus,

y T p = x Q m x T p x , ∆ = x     x T p x -r x T p x + ∆ 2     thanks to eq. (18) = x     q x T p x ∆ + d m     = x T p -x .r x T p x + ∆ 2 x
Hence,

y = x -x .r x T p x .p + ∆ 2 x . (21)
Let us now evaluate Q m y T p y , ∆ .

Q m y T p y , ∆ = round     y T p y -d m ∆     ∆ + d m = round             x T p -x .r x T p x + ∆ 2 x y -d m ∆             ∆ + d m = round           x (q x T p x ∆ + d m ) y -d m ∆           ∆ + d m = round       x q x T p x ∆ + x d m -y d m ∆ y       ∆ + d m = round         x q x T p x ∆ + x ∆ 4 (2m -1) -y ∆ 4 (2m -1) ∆ y         ∆ + ∆ 4 (2m -1) = round         x q x T p x + x 2m -1 4 -y 2m -1 4 y         ∆ + ∆ 4 (2m -1) = round     x y q x T p x + x y 2m -1 4 - 2m -1 4     ∆ + ∆ 4 (2m -1).
Let's go back to the definition (20) of m which becomes:

m = arg min m ∈{0,1} x     q x T p x ∆ + ∆ 4 (2m -1)     -y round     x y q x T p x + x y 2m -1 4 - 2m -1 4     ∆ + ∆ 4 (2m -1) = arg min m ∈{0,1} x     q x T p x + 2m -1 4     -y round     x y q x T p x + x y 2m -1 4 - 2m -1 4     + 2m -1 4 = arg min m ∈{0,1} x y .q x T p x + x y . 2m -1 4 - 2m -1 4 -round     x y q x T p x + x y 2m -1 4 - 2m -1 4     .
One can first notice that what is inside the absolute value is close to 0 since it has the form X -round(X), where X ∈ R.

Let us now evaluate

x y . Thanks to [START_REF] Jiang | Adaptive spread transform QIM watermarking algorithm based on improved perceptual models[END_REF], we have:

y ≤ x + x .r x T p x . p + ∆ 2 x ≤ x     1 + r x T p x + ∆ 2     ≤ x 1 + 3∆ 2 .
In all what follows, x and p are supposed to only have postive or null values and ∆ is assumed to be less than 2. Again, thanks to (21),

y i = x i -x .r x T p x .p i + ∆ 2 x .p i y i > x i -x .∆.p i + ∆ 2 x .p i since r < ∆ y i > x i - ∆ 2 x .p i which is postive if ∆ is sufficently small. Thus y ≥ x - ∆ 2 x .p ≥ x 1 - ∆ 2 .
Finally,

2 2 + 3∆ ≤ x y ≤ 2 2 -∆ , for ∆ < 2 sufficiently small. ( 22
)
Next, if ∆ is tiny, then r s is too; consequently, q s will have a very large value. Equation [START_REF] Jiang | Adaptive spread transform QIM watermarking algorithm based on improved perceptual models[END_REF] implies that y (resp. y ) is close to x (resp. x ). In this context, x y .q x T p x is significantly larger than

x y . 2m -1 4 - 2m -1 4 .
In this sense, when m and m are equal,

x y . 2m -1 4 - 2m -1 4 is close to 0;
therefore, the round() value will be close to the round() value of x y .q x T p x and the global result will be close to 0, but when m and m are distinct,

x y . 2m -1 4 - 2m -1 4
is close to ±0.5. In this situation, the round() value may be significantly different. As shown in subsections 5.1 and 5.2, the extracted message m depends on m and m ; without any attack, m will be the same as m. If we perform the FGA attack s.t. z = ρ.y on the tradional STDM watermarking scheme, m will be decoded as follows:

m = arg min m∈{0,1} | ρ • y T p -Q m (ρ • y T p, ∆) | . The quantification factor Q m (ρ • y T p, ∆) is indeed equal to round ρ•y T p-d m ∆ ∆ + d m which may be different from round y T p-d m ∆ ρ•∆+ρ•dm and consequently not equal to ρ • Q m (y T p, ∆).
Therefore, as the decoded message can be different from the embedded one, the robustness against the FGA attack cannot be obtained. But with the N-STDM watermarking scheme, m will be decoded as follows:

m = arg min m∈{0,1} ρ • ỹ -ρ • y Q m ρ • ỹ ρ • y , ∆ = arg min m∈{0,1} ρ • ỹ -y Q m ỹ y , ∆ .
Thus, the non-linear impact of the ρ factor in the quantization will not affect the process of decoding the message; as a result, the N-STDM has stronger resistance to the FGA attack.

Fig. 2: The original images (first and third columns) and corresponding watermarked images (second and fourth columns) using the N-STDM method for u=2 with a 4096-bit message embedded and SSIM=0.982.

Experiments on Real Images

The algorithm is parameterized by two variables, which are the u factor, presented in [START_REF] Cox | Secure spread spectrum watermarking for images, audio and video[END_REF], and the elements that are considered to compute the norm. The first part of the experiment aimed at finding optimal values for these parameters with respect to the results against the FGA attack. We compared our proposed method against the FGA attack while varying u using two forms. In the first one (Global form), we compute the norm value x of the whole pixels of the cover image which will be used to embed all the watermark bits. In the second one (Local form), we extract the pixels values from the cover image and arrange them into several vectors.

After that, we compute the norm value x of each vector, in which we will embed the i th bit of the watermark; hence, each bit will have a specific norm value, and each vector will have the same length as the projection vector. In this experiment, grayscale images with size 512×512, such as the images presented in Fig. 2, have been used as a host signal, the length of the projection vector is set to 64, which allows a 4096-bit message to be embedded into each image, and ∆ is adjusted to have watermarked images with same level of fidelity by using a fixed SSIM of 0.982 (PSNR around 45 dB). The robustness of N-STDM method against FGA attack when varying u between 1/5 and 5 using the global form is shown in Fig. 3a. The BER decrease when u increases, with preferable results when u is higher than 1. Fig. 3b shows the robustness of N-STDM against FGA attack using the local form. In this situation, the N-STDM has a good performance regardless of the value of u.

The BER increase a little bit when multiplying the pixels of the grayscale images by a gain factor higher than 1.2 due to the clipping error; when the pixels values are beyond 255, it will be clipped to 255. The maximum allowed value is 255.

Besides, the robustness of the global form and the local form was tested against the FGA attack, when applied to a given area of the watermarked image (between 25% and 75%). As shown in Fig. 4, the local form has better robustness comparing to the global form. The global form is affected when the FGA attack is applied to 50% or 75% of the area of the watermarked images. The problem of the global form is solved in the frequency domain when the DCT transform is applied to the cover images. The detailed results are presented in Section 6.2. Moreover, we have compared the robustness of global form and local form against the AWGN attack while varying the standard deviation between 1 and 8. As shown in Fig. 5, the N-STDM watermarking scheme has better robustness using the global form comparing to the local form. Fig. 6 shows the sets of reconstruction points of the quantizers for embedding each bit in each vector, where the projection of the vector is done before quantization. The signal is quantized to the nearest point on a •-line to embed a 0-bit and on a ×-line to embed a 1-bit. The minimum distance d min between the sets of reconstruction points of different quantizers in the ensemble effectively determines the robustness of the embedding. With STDM [START_REF] Chen | Quantization index modulation: a class of provably good methods for digital watermarking and information embedding[END_REF], as shown in Fig. 6, d min = ∆/2. In N-STDM global form, the same norm value is used uniformly to embed each bit of the watermark. For that, d min = x ∆/2. In the local form, the quantization step size can be seen as a variable step quantizer; each vector has a specific quantization step size. Therefore, d min of the first bit will be different from d min of the second bit, and so on. This variation increases the influence of additive noise attacks on the decoding quantization step size. In the global form, a uniform gain invariant adaptive quantization is obtained at both the embedder and decoder, which improves the robustness against the additive noise attacks. It still better to use the global form since the same norm value x is used to embed all the bits of the watermark; accordingly, all the watermarked vectors in the image will have an identical imperceptibility and better robustness.

       



In conclusion, the parameter value that provides the results with the lowest errors is u=2 using a global form of the norm, which will be applied in the subsequent experiments.

In the second part of the experiment, we have practically evaluated the correction of the N-STDM watermarking scheme. In other words, we have verified that when a message is embedded into a host signal, prior to applying any attacks, it will be extracted without any error. Practically speaking, 1000 grayscale images with size 512×512 extracted from Boss image database [START_REF]Information Hiding -13th International Conference, IH 2011[END_REF] are used as a host signal. The length of the projection vector is set to 64, which allows a 4096-bit message to be embedded into each image. The quantization step size ∆ is adjusted in order to have watermarked images with uniform fidelity, a fixed SSIM of 0.982. For all the images, the BER of the extracted watermark are equal to 0, which leads to a conviction that any embedded message could be retrieved without errors prior to applying any attacks.

In the third part of the experiment, the visual aspect of the presented approach has been studied. The length of the projection vector is set to 64, which allows a 4096-bit message to be embedded into each image. We used the Structural Similarity Index Measurement (SSIM) to evaluate the quality performance of N-STDM. Fig. 7 shows the comparison between N-STDM and STDM on 30 standard watermarked images in term of SSIM. N-STDM produces watermarked images that yield nearly the same SSIM performance as that of the traditional STDM. Fig. 2 shows a part of grayscale images. The second and fourth columns display the obtained watermarked images using the N-STDM method with a SSIM=0.982. These watermarked images appear identical to the original ones, to a far extent that they cannot be told differently with the naked eye. Fig. 9: Robustness against AWGN attack in term of BER with SSIM=0.982.

Comparison in the Spatial Domain

In this section, we compare the robustness in the spatial domain of our proposed approach with the traditional STDM watermarking scheme and RDM [START_REF] Pérez-González | Rational dither modulation: A high-rate data-hiding method invariant to gain attacks[END_REF] against the FGA attack and AWGN attack. The comparison is conducted using the grayscale images of size 512×512. The length of the projection vector is set to 64 which allows a 4096-bit message to be embedded into each image, and the tested images were watermarked with a uniform fidelity, where SSIM is fixed to 0.982 (PSNR around 45 dB).

As shown in Fig. 8, N-STDM and RDM have good robustness against the FGA attack, while STDM has low robustness against the FGA attack; even when the values of a gain factor are close to 1, such as 1.1 or 0.9, the BER are excessively high.

As to the RDM, the feature signal for quantization is constructed using the ratio of the previously generated watermarked sample and the current host sample. As a result, it resists the FGA attack but will be affected by the AWGN attack as shown in Fig. 9. The quantization step size in RDM is a variable step quantizer, whose size is a function of several past watermarked samples, and does not benefit from the randomness property of the spreading vector. Therefore, the attacking noise has more influence on the decoding quantization step size. Concerning the N-STDM, the quantization step size depends on the watermarked samples during the decoding process which will scale linearly with the FGA attack, and based on the global form, a uniform gain invariant adaptive quantization is obtained at both the embedder and decoder. However, since the proposed N-STDM keep on using the spreading vector in the embedding process, it withstands AWGN attack. This is due to the randomness property of the spreading vector, which affects the embedding of the watermark and hence makes it randomly distributed in the host signal samples. Therefore, the proposed N-STDM sustain the robustness against various noise attacks. Also, the quantization step size ∆ in RDM depends on g(y k-1 k-L ), which is not uniform for all the samples. Therefore, as shown in Fig. 10, each sample will have a specific minimum distance d min . By this way, each watermarked sample will have a specific level of robustness. Comparing to N-STDM global form, as shown in Fig. 6, d min is uniform for all the sets of reconstruction points of different quantizers. Therefore, the trade-off between robustness and transparency is achieved. The watermark bit is spread into a group of samples instead of one sample, which also increase the level of robustness. Each time the watermarking space increases, the probability of accurate decoding is higher. This is mainly because of the spreading property of the watermark using the spreading vector. Our approach achieves significant robustness against the FGA attack with an improvement of 98% in terms of BER compared to traditional STDM and 24% compared to RDM. As for the AWGN attack, an improvement of 21% is shown compared to STDM and 50% compared to RDM.

Comparison in the Frequency Domain

To test the performance of N-STDM in the frequency domain, we have implemented the DCT transform on the grayscale images of size 512×512 as shown in the block diagram in Fig. 11a. First of all, we have computed the norm value x of the original image to be used during the embedding process. After that, we have divided the image into 8×8 blocks of pixels, upon which the DCT transform was later performed to get the DCT coefficients. A part of these coefficients was used as a host vector of length L, in which we have later embedded the i th bit of the watermark message m. Then, we have performed the inverse DCT transform at each block to get the watermarked image. To assure a fair comparison, we compared the proposed N-STDM watermarking scheme with I-ASTDM [START_REF] Zhu | Image-adaptive spread transform dither modulation using human visual model[END_REF], STDM-MW-SS [START_REF] Li | Improved spread transform dither modulation using a perceptual model: robustness to amplitude scaling and JPEG compression[END_REF] and STDM-SP-wm [START_REF] Li | Step-projection-based spread transform dither modulation[END_REF]; family methods based on the perceptual model. The block diagram of those family methods is shown in Fig. 11b, where the quantization step size ∆ is modified based on the slacks vectors S which are computed using Watson's model. The FGA attack, AWGN attack, JPEG compression, and a variety of common signal processing attacks are used to verify the performance of our proposed scheme. The 2nd-21st DCT coefficients have been used for all the algorithms. These coefficients have been selected based on the zig-zag-scanned order of each 8×8 block, in which we embed 1 bit of the watermark. The embedding rate is 1/64, i.e. one bit in each 8×8 block, which allows the embedding of a 4096-bit message into each image. The tested images were watermarked using a uniform fidelity, with a fixed SSIM of 0.982 (PSNR around 45 dB) for the first part of comparisons, and a fixed SSIM of 0.953 (PSNR around 40 dB) for the second part of comparisons by regulating the quantization step size and the factors that adjust the watermarking strength. All of the experimental results are obtained by averaging over 100 runs.

In the first part of the experiments, the global form of the N-STDM watermarking scheme was examined facing the FGA attack, when applied to a given area of the watermarked image (between 25% and 100%). As shown in Fig. 12, the robustness is highly improved comparing to the global form in the spatial domain presented in Fig. 4, especially when the FGA attack is applied to 50% or 75% of the area of the watermarked image. Moreover, the proposed N-STDM is compared with the family methods based on Watson's model against the FGA attack. As expected, the results of the posted comparison have met the suggestions of the proposed method. According to Fig. 13, the proposed N-STDM watermarking scheme has a slightly better level of robustness than the family methods, varying from 5% comparing to STDM-MW-SS to 22% comparing to STDM-SP-wm for SSIM = 0.982, while proved to have better to more superior robustness against the AWGN attack and JPEG compression. The robustness against AWGN attack has been tested in terms of BER while varying the standard deviation between 1 and 8. As shown in Fig. 14, the proposed N-STDM watermarking scheme achieves better performance than the STDM-SPwm (improvement of 14%) and notably superior performance to the I-ASTDM (improvement of 38%) and STDM-MW-SS (improvement of 56%). Fig. 15 illustrates the robustness to JPEG compression in term of BER while varying the JPEG quality between 10 and 100. The JPEG quality denotes the compressibility of the JPEG compressor; lower numbers mean lower quality. The N-STDM has better performance than STDM-SP-wm (improvement of 13%) with more notable variations comparing to STDM-MW-SS (improvement of 18%) and I-ASTDM (improvement of 27%) against the JPEG compression.

To further evaluate the performance of N-STDM watermarking scheme, we have compared the robustness against noise addition attacks, image filtering attacks, and geometric attacks. All the watermarked images were exposed to many different attacks such as Salt&Pepper with noise densities ∈ {0.005, 0.01}, Gaussian filtering, Median filtering, Wiener filtering, Average filtering, Cropping, Rotation, and Resizing. The detailed experimental results are shown in Table 1 with SSIM=0.982 and Table 2 with SSIM=0.953. The experiments have verified that our proposed scheme is not only robust against the FGA attack but also robust to common signal processing attacks. N-STDM has achieved good robustness against Salt&Pepper attack and image filtering attacks comparing to the family methods based on Watson's model. As for the geometric attacks, N-STDM achieved good robustness against the cropping attack when we cropped 10% of the image, but the BER slightly increased when we increased the cropping dimension of the image to 20%. Concerning the rotation attack, all the compared methods were vulnerable to the rotation of 1 • of the image, though the BER highly decrease if we re-rotate the image by -1 • . As for the resizing attack, N-STDM achieved better robustness comparing to the family methods, noting that the robustness improved as well while adjusting the watermarking strength based on ∆.

Experiments and Comparisons on PDF Documents

Portable Document Format (PDF) has been invented by Adobe [19] and maintained by the International Organization for Standardization (ISO). PDF is a digital form and an imaging model derived from PostScript language, with more structured format for representing documents, which enable users to view and exchange the electronic documents reliably and easily. PDF users around the world include important information while using PDF. Therefore, the protection of those documents against unauthorized users has become essential and necessary. PDF functions vary from text to images and other multimedia elements.

The general text-based structure of PDF is composed of 4 parts: Fig. 16: Perceptual visualization of the watermarked document using the N-STDM for ∆ = 1 × 10 -3 to 5 × 10 -3 gradually from top to bottom.

3. Cross-reference table: contains one-line entry for each indirect object and has a fixed format in order to access randomly the entries in the table. 4. Trailer: enables a conforming reader to quickly find the cross-reference table and other special objects. In a PDF file, coordinate systems determine the position, orientation, and size of the text, images, and graphics that appear on a page. Each character has a coordinate pair, x and y, that locates the character horizontally and vertically within twodimensional coordinate space. The x-coordinates values are non-constant. Therefore, they have been used as the watermarking space in order to embed the watermark. Each character of the watermark has been encoded into 8 bits in order to form a total of N bits. Each bit message is then embedded into L characters' x-coordinates extracted from the original document. Accordingly, a total of N × L characters are used from the document to embed the whole bits of the message. Fig. 16 presents a part of a watermarked paragraph extracted from the watermarked document, which has been watermarked using the N-STDM watermarking scheme with several values of ∆. When ∆ increases, the error values increase as well, especially when ∆ ≥ 4 × 10 -3 . 24 lines have been extracted from a PDF document with 84 characters each (n=84), totalling 2016 characters. To assure a wider comparison between the proposed N-STDM watermarking scheme and the traditional STDM and RDM watermarking schemes against FGA and AWGN attacks, two scenarios have been applied through which the number of bits N and the length of the projection vector L have been variably used: In the first scenario, we embedded k = 1 bit per line (N =24 and L=84), and in the second one, we embedded k = 4 bits per line (N =96 and L=21). Same embedding parameters have been used such as the length of the host signal, the secret message, and dither level. All the experiments were conducted while varying ∆. Several values of ∆ have been used taking into account the Mean Squared Error (MSE) values; the ∆ value has been adjusted in order to have the same MSE values (0.03 and 0.13)

Against FGA and AWGN Attacks

In order to prove the superiority of N-STDM in terms of robustness constraint, a comparison between the proposed scheme (N-STDM) and the traditional schemes (RDM and STDM) was performed while varying the parameters N and L. The comparison mainly tackles the robustness against FGA and the robustness against AWGN attacks. The N-STDM robustness against the FGA attack, to start with, has achieved a great superiority over STDM. Fig. 17 and Fig. 18 show that the traditional STDM is affected by the FGA attack even when the ∆ value is high (MSE=0.13) and regardless of the length of projection vector and the number of the embedded bits. On the contrary, N-STDM, along with RDM, surpass the FGA attack for MSE = 0.03 and 0.13. As to the robustness against AWGN attack, the strength is evaluated by mean of the Watermark to Noise Ratio (WNR): Only the digits after the decimal point are modified. Fig. 19 and Fig. 20 show that RDM is noticeably affected by the AWGN attack even when the ∆ value is high whereas the proposed N-STDM achieves great performance against this attack. STDM preserves good performance against AWGN, yet the proposed N-STDM could perform even better noting that the BER of STDM and N-STDM are close to each other with an advantage of N-STDM over STDM.

WNR = 10 log 10 ( σ 2 w σ 2 n ). (23)
As shown in Fig. 19 and Fig. 20, RDM is affected by the AWGN attack even with a higher value of ∆. In contrast, our proposed N-STDM watermarking scheme preserves superior robustness against the AWGN attack. The robustness increases while ∆ and L increase, with a BER close to 0 when WNR > 0. The BER of

Findings and Discussion

We have studied the performance of the proposed N-STDM watermarking scheme in the spatial domain and the frequency domain using the grayscale images and With respect to the experiments on real images in the frequency domain, the family methods (I-ASTDM, STDM-MW-SS, and STDM-SP-wm) have good robustness against the FGA attack, and an accepted robustness against AWGN attack and JPEG compression. The proposed watermarking scheme, N-STDM, on the other hand, achieves a superior performance comparing to the family methods varying from little different against FGA attack to a greater one against AWGN, JPEG compression, and image filtering attacks. As for the geometric attacks, N-STDM has achieved good robustness against the cropping attack, but the BER slightly increased while increasing the cropping dimension of the image. N-STDM and the family methods are vulnerable to the rotation attack, though the BER highly decrease if we re-rotate the image. Concerning the resizing attack, N-STDM has achieved better robustness comparing to the family methods, noting that the robustness improved as well while adjusting the watermarking strength based on ∆. Moreover, we proved that our approach could also be used as a blind watermarking scheme for PDF documents under a sufficient transparency-robustness tradeoff. We exploited the x-coordinates values of characters as real cover elements to embed the watermark. The comparison between N-STDM and the traditional STDM and RDM against FGA and AWGN attacks shows that the proposed N-STDM achieves better performance than the mentioned watermarking schemes.

Conclusion and Future Work

In this paper, we have proposed an improved version of STDM watermarking scheme, which is essentially invariant to FGA attack. In this method, called N-STDM, we scaled the quantization step size in the same way the watermarked signal is scaled as an invariant adaptive size based on the global form. Experiments on real images in the spatial domain and frequency domain have verified that our method is not only robust to the FGA attack but also robust to common signals processing attacks such as AWGN attack, JPEG compression, and Image filtering attacks comparing to STDM, RDM, and the family methods based on Watson's model. As for the geometric attacks, N-STDM has achieved good robustness against the resizing and cropping attacks, but the BER slightly increased while increasing the cropping dimension of the image. N-STDM and the family methods are vulnerable to the rotation attack, though the BER highly decrease if we re-rotate the image. Moreover, we have verified that our approach could also be used as a blind watermarking scheme for PDF documents with a perceptual advantage and better robustness over STDM and RDM.

As for future enhancements, we plan to include further improvement of the N-STDM watermarking scheme against the geometric attacks, by applying other types of frequency transform such as DWT and SVD.

Fig. 1 :

 1 Fig. 1: Block diagram of the N-STDM watermarking scheme.

Fig. 3 :Fig. 4 :

 34 Fig.3: Robustness of N-STDM against FGA attack in term of BER while varying u with SSIM=0.982.

Fig. 5 :

 5 Fig. 5: Robustness of N-STDM (Local form vs Global form) against AWGN attack in term of BER while varying u with SSIM=0.982.

Fig. 6 :

 6 Fig. 6: Geometrical representation of STDM, N-STDM Global form, and N-STDM Local form. Points on solid-lines represent embedding for m=1, whereas dashedlines are for m=0.

Fig. 7 :Fig. 8 :

 78 Fig. 7: SSIM comparison between N-STDM and STDM.

Fig. 10 :

 10 Fig. 10: Geometrical representation of RDM in term of d min . The signal is quantized to the nearest point on a •-line to embed a 0-bit and on a ×-line to embed a 1-bit.

  Block diagram of the family methods based on Watson's model.

Fig. 11 :

 11 Fig. 11: Block diagrams of the N-STDM method (a) and the family methods based on Watson's model (b).

Fig. 13 :

 13 Fig. 13: Robustness against FGA attack in term of BER.

Fig. 14 :

 14 Fig. 14: Robustness against AWGN attack in term of BER.

Fig. 15 :

 15 Fig. 15: Robustness against JPEG compression in term of BER.

(a) ∆ = 1 ×

 1 10 -3 , M SE = 7 × 10 -3 .                                                                                         (b) ∆ = 2 × 10 -3 , M SE = 0.03.                                                                                                           (c) ∆ = 3 × 10 -3 , M SE = 0.07.                                                                                                  (d) ∆ = 4 × 10 -3 , M SE = 0.13.                                                                                                                                           (e) ∆ = 5 × 10 -3 , M SE = 0.17.

Fig. 17 :Fig. 18 :

 1718 Fig. 17: Robustness against FGA for N =24 and L=84.

  Rony DARAZI (SM'16) received the M.S. degree in Computer and Telecommunications engineering from Antonine Univerity (UA), Lebanon in 2005, and the Ph.D. degree in engineering sciences from the Universit catholique de Louvain (UCL), Louvain-la-Neuve, Belgium, in 2011. His PhD was entitled "Towards a combining scheme for compression and watermarking for 3D stereo images". He is currently an Associate Professor at UA. He was a Researcher in the ICTEAM Institute at UCL from 2006 until 2012, and is a Member of the TICKET Lab at UA since 2010. His research interests include information security and digital watermarking, digital 2D and 3D image processing, sensor networks, and e-health. Dr. Darazi is an IEEE senior member, he received a grant research project from the National Council for Scientific Research in Lebanon (CNRS-L) in 2016. In 2017, he received a research fund from the Hubert Curien CEDRE programme n • 40283YK, and another fund from the Agence Universitaire de la Francophonie AUF-PCSI programme. In 2018, Dr. Darazi received a research award from the research council at the Antonine University. He co-chaired the International Conference on Applied Research in Computer Science & Engineering (ICAR'15), sponsored by IEEE in 2015, and has been actively involved as a Reviewer in several conferences and journals. In 2009, he received the Best Paper Award, second prize by the Digital Watermarking Alliance and the IS&T/SPIE International Conference on Media Forensics and Security XII. Jean-François COUCHOT is an Associate Professor of the FEMTO-ST institute (CNRS) at the university of Bourgogne Franche-Comté. He received a Ph.D. in Computer Science in 2006 in the FEMTO-ST institute. He has applied for a postdoctoral position at INRIA Saclay Ile de France in 2006. His research focuses on discrete dynamic systems (with applications into data hiding, watermarking, pseudorandom number generators, hash function) and on bioinformatics, especially in gene evolution prediction. He has written more than 40 scientific articles in these areas.

Table 1 :

 1 BER comparison under noise addition, image filtering, and geometric attacks with SSIM=0.982.

	Attacks	I-ASTDM	STDM-MW-SS	STDM-SP-wm	N-STDM
	Salt&Pepper (d=0.005)	0.12	0.11	0.12	0.09
	Salt&Pepper (d=0.01)	0.21	0.19	0.22	0.17
	Gaussian filtering (3 × 3)	0.016	0.024	0.035	0.014
	Median filtering (3 × 3)	0.25	0.21	0.22	0.16
	Wiener filtering (3 × 3)	0.26	0.2	0.22	0.16
	Average filtering (3 × 3)	0.35	0.31	0.29	0.24
	Crop (10%)	0.0064	0.0063	0.0066	0.0061
	Crop (20% )	0.023	0.022	0.024	0.08
	Rotation (1 • )	0.48	0.46	0.47	0.46
	Re-Rotation (-1 • )	0.18	0.09	0.1	0.07
	Resizing (1024 × 1024)	0.025	0.003	0.008	0
	Resizing (256 × 256)	0.31	0.28	0.24	0.21

Table 2 :

 2 BER comparison under noise addition, image filtering, and geometric attacks with SSIM=0.953.

	Attacks	I-ASTDM	STDM-MW-SS	STDM-SP-wm	N-STDM
	Salt&Pepper (d=0.005)	0.09	0.07	0.08	0.06
	Salt&Pepper (d=0.01)	0.16	0.14	0.14	0.1
	Gaussian filtering (3 × 3)	0.004	0.002	0.01	0
	Median filtering (3 × 3)	0.17	0.14	0.15	0.11
	Wiener filtering (3 × 3)	0.16	0.13	0.12	0.07
	Average filtering (3 × 3)	0.26	0.22	0.21	0.16
	Crop (10%)	0.0053	0.0051	0.0052	0.0041
	Crop (20% )	0.019	0.017	0.018	0.06
	Rotation 1 •	0.47	0.48	0.46	0.45
	Re-Rotation 1 •	0.05	0.05	0.06	0.04
	Resizing (1024 × 1024)	0.001	0.001	0.001	0
	Resizing (256 × 256)	0.23	0.21	0.19	0.12

  1. Header: contains the version number of the PDF document. 2. Body: consists of a series of objects, representing the contents of a document.                                                                               

  Based on Watsons model, the family methods could not be applied to PDF documents because they are dependent on the perceptual model of images.

		
									
									 
									
									 
		
		  
		
		
		
		
										
						
	Fig. 19: Robustness against AWGN for N =24 and L=84.
		
									
									 
									
									 
		
		  
		
		
		
		
										
						
	Fig. 20: Robustness against AWGN for N =96 and L=21.
	STDM and N-STDM watermarking schemes are close to each other, with better
	performance for N-STDM.
	N.B.

Table 3 :

 3 Summary of the findings. As for the experiments on real images in the spatial domain, the proposed N-STDM has achieved high robustness against FGA and AWGN attacks comparing to STDM and RDM. STDM has good robustness against AWGN attack, but it is highly affected by the FGA attack. RDM achieves good robustness against FGA attack but has a weak performance against the AWGN attack.

	Watermarking scheme	Findings
	STDM	*Strong against the AWGN attack
		*Week against the FGA attack
	RDM	*Strong against the FGA attack
		*Week against the AWGN attack
		*Robust against FGA, AWGN, JPEG compression,
	Family methods based on Watson's model	Image filtering, and Cropping attacks *Weak against Rotation attack *Dedicated for images
		*Could only be applied in the frequency domain
		*More flexible
		*Could be applied in the spatial domain and frequency
		domain
		*Any element can be used as support to embed the
	N-STDM	watermark (such as images and PDF documents)

*High level of robustness against FGA, AWGN, JPEG compression, and Image filtering attacks *Robust against Copping, and Resizing attacks *Weak against Rotation attack PDF documents.

Acknowledgements This work is partially funded with support from the National Council for Scientific Research in Lebanon CNRS-L, the Hubert Curien CEDRE programme, the Agence Universitaire de la Francophonie AUF-PCSI programme, and the Labex ACTION program (contract ANR-11-LABX-01-01).