Research On Watermarking Techniques For Relational Databases Authentication And Rights Protection

In recent years, with the fast development of information technology, an increasing numberof databases (e.g., parametric specifications, surveys, and life sciences data) are distributedthrough the internet. The piracy problem has become one of the most devastating threats tonetworking systems and electronic business. While demand for the use of databases is growing,pirated copying has become a severe threat to such databases due to the low cost of copying andthe high values of the target databases. Two major concerns are explored in this thesis, namelythe rights protection and integrity verification of relational data.These concerns introduce the issue of database security, which dramatically increases theneed of effective mechanisms for copyright protection and authentication of relational data. Toaddress these concerns, digital watermarking has been introduced, first in the multimediacontext, and recently in relational databases literature, so that the ownership and the integrity ofthe data can be asserted based on the detection of watermark.To bring our contribution to the very active field of database watermarking, we proposethree appropriate watermarking solutions including, a fragile watermarking algorithm, asemi-fragile watermarking technique, and a hybrid watermarking scheme.Our fragile watermarking technique is based on zero-watermarking paradigm. Unliketraditional database watermarking schemes, our proposed method does not introduce anydistortion to the underlying data. Furthermore, no constraint is defined on the type of attributescandidate for marking. The scheme is called “zero-watermark” because the watermark bits arenot actually encoded in the data. Instead, we introduce a trusted third party called CertificationAuthority (CA) with whom the watermark is registered and notarized along the original data forauthentication purpose. Our fragile technique consists of two main stages:(i) watermarkgeneration and registration, and (ii) watermark extraction and verification. Without loss ofgenerality, we call the first stage watermark embedding and the second stage watermarkdetection. All these stages are secure as they are governed by the use of a unique secret keyknown only to the data owner. This secret key should be chosen long enough for thwarting brute force guessing attack to the key. The properties of our fragile scheme can be summarizedas follows:(i) It is fragile: any modification maliciously made to the watermarked relation canbe detected and localized with high probability;(ii) it is a distortion free scheme in nature: noerror is introduced to the underlying data. As a result, the scheme is especially suitable fordatabase relations for which zero-distortion is required, e.g., categorical data;(iii) it provides anattribute reordering method that assures the synchronization of the watermark. The purpose ofthis method is to define a secret “initial” order of the relation attributes before the generation ofthe watermark. At the detection phase, the secret “initial” order is then recovered beforewatermark extraction;(iv) no constraint is defined on the type of attributes involved in thewatermarking process. Attributes can be numeric or non-numeric.The second contribution of this thesis is an innovative and blind semi-fragile watermarkingtechnique for integrity verification of numeric relational data. Unlike prior watermarking basedauthentication schemes which are totally fragile, the goal of our semi-fragile method is detectillegitimate modifications, while allowing legitimate ones. To do so, with each attribute, weassociate a secret weight that reflects its sensitivity to benign updates. A weight can be of threetypes: high weight, intermediate weight, and low weight. A high weight is assigned to sensitiveattributes, i.e., attributes that do not need to be legally updated after watermark insertion. Anintermediate weight is associated to semi-sensitive attributes which can be legitimatelymodified up to a predefined level of distortion. A low weight is assigned to non sensitiveattributes which can be altered without fear of any constraint. Thereafter, according to attributeweights, we vertically partition the database relation into three non-overlapping classes(clusters), namely high-weight cluster, intermediate-weight cluster, and low-weight cluster.Notice that our clustering method is a virtual operation since it does not physically split thedatabase relation rows. Moreover, for each intermediate-weighted attribute, we define a (legal)alteration bandwidth which represents the degree of legitimate distortion that these attributescould tolerate. In watermark embedding, since high-weighted attributes do not need any benignupdates, we securely encode the semi-fragile watermark bits into these attributes by altering theleast significant bit of some selected attributes. In watermark detection, since the proposedscheme is semi-fragile in nature, only unauthorized distortions should be detected as tampering.So, for an attack to be effective, the pirate needs to maliciously modify sensitive attributes and/or non alterable bits of semi-sensitive attributes, while keeping unchanged the embeddedwatermark. However, since the embedded watermark is computed from data characteristicsusing cryptographic secure hash function (SHA-1), any modification made beyond allowedlimits are correctly detected and localized as tampering with high rate.In the third contribution of the thesis, we propose a combined robust-fragile watermarkingtechnique for ownership protection and tamper-proofing of relational databases. Our proposedhybrid watermarking scheme is a multiple watermarks application that has two maincomponents: a robust component and a fragile component. These components can be usedindependently depending on the nature of the dispute: ownership claim or tamper proofing.Obviously, the fragile component has to be applied after the robust one in order to hash therobust watermark with the data. As a result, the integrity of the robust watermark is guaranteedby the fragile component. Any attack aimed to destroy or remove the robust watermark will becorrectly detected and localized as malicious modification. To ensure the robustness andreliability of the robust watermark, we propose to use the LSB of every attribute for embeddingthe fragile watermark, while the robust watermark bits can be securely encoded into theremainder (ξ-1) LSBs available for marking. The main characteristics of our hybrid solution canbe summarized as follows:(i) Imperceptibly: the watermarks embedding only introduce smallalterations that will not affect the data usability;(ii) Robustness: the embedded robustwatermark is resilient against distortions caused either by benign updates or malicious attacks;(iii) Fragileness: the embedded fragile watermark is sensitive to malicious modifications,meaning that any slight change made to the database relation is correctly detected and localized;(iv) Secure and reliable embedding: the insertion of the fragile watermark preserves therobustness and the reliability of the robust watermark, i.e. the fragile watermark embeddingdoes not remove or flip-back the robust watermark bits;(v) Blindness: the watermarks detectionand verification do not require the knowledge of the original non-watermarked databaserelation; and (vi) Tuple and attribute order independent: the embedded watermarks do notdepend on a particular order of tuples or attributes.