24-03-2011, 03:54 PM
[attachment=10927]
Watermarking Relational Databases Using Optimization- Based Techniques
Abstraction
Proving ownership rights on outsourced relational databases
We present a mechanism for proof of ownership based on secure embedding of robust(Sturdy in construction)
Here we formulate the constrains and discuss efficient tech to solve the optimization prob and to handle the constrains
Overcomes a major weakness in previously proposed tech
Probability of decoding errors are minimized by an optimal threshold(Threshold-Based Tech)
Introduction
Enforcing data ownership is an important requirement which requires articulated solutions
In last years watermarking techniques have emerged as an important building block which plays a crucial role in addressing the ownership problem.
A watermark describes information that can be used to prove the ownership of data, such as the owner, origin, or recipient of the content.
Watermarking techniques have been developed for video, images, audio, and text data and also for software and natural language text
application contexts for which data represent an important asset, the ownership of which must thus be carefully enforced.
For example, of weather data, stock market data, power consumption, consumer behavior data, medical and scientific data
Watermarking
Main Contribution
We formulate the watermarking of relational databases as a constrained optimization problem, and discuss efficient techniques to handle the constraints. We present two techniques to solve the formulated optimization problem based on genetic algorithms and pattern search techniques.
We present a data partitioning technique that does not depend on marker tuples to locate the partitions and thus it is resilient to watermark synchronization errors.
We develop an efficient technique for watermark detection that is based on an optimal threshold. The optimal threshold is selected by minimizing the probability of decoding error.
With a proof of concept implementation of our watermarking technique, we have conducted experiments using both synthetic and real-world data. We have compared our watermarking technique with previous approaches shows the superiority of our technique with respect to all types of attacks.
Related Work
1. Agrawal proposed a watermarking algorithm that embeds the watermark bits in the least significant bits (LSB) of selected attributes of a selected subset of tuples
This technique does not provide a mechanism for multi bit watermarks; instead only a secret key is used.
For each tuple, a secure message authenticated code (MAC) is computed using the secret key and the tuple’s primary key.
Hiding bits in LSB is efficient.
Problem : the watermark can be easily compromised by very trivial attacks.
2. Sion et al proposed a watermarking technique that embeds watermark bits in the data statistics.
data partitioning technique used is based on the use of special marker tuples which makes it vulnerable to watermark synchronization errors resulting from tuple deletion and tuple insertion; thus such technique is
not resilient to deletion and insertion attacks.
He recommend storing the marker tuples to enable the decoder to accurately reconstruct the underlying partitions
Problem: violates the blinded watermark detection property
Furthermore, Sion et al. proposed
a threshold technique for bit decoding that is based on two thresholds.
However, the thresholds are arbitrarily chosen without any optimality criteria.
Thus the decoding algorithm exhibits errors resulting from the non-optimal threshold selection
Even in the absence of an attacker.
Next Comes Gross-Amblard
Gross-Amblard proposed a watermarking technique for
XML documents and theoretically investigates links between query result preservation and acceptable watermarking alterations.
Another interesting related research effort is to be found in where the authors have proposed a fragile watermark technique
to detect and localize alterations made to a database relation with categorical attributes.
APPROACH OVERVIEW
The Main Components are as follows
Data set “D”
Data set “D” is transformed into a watermarked version “DW”
watermark encoding function that also takes as inputs a secret key “Ks”
only known to the copyright owner and a watermark “W”
Watermarking modifies the data.
modifications
are controlled by providing usability constraints referred to by the set G.
Watermarking Encoding
summarized by the following three steps:
Step E1: Data set partitioning: by using the secret key Ks
the data set D is partitioned into m non-overlapping partitions {S0, . . . , Sm−1}.
Step E2: Watermark embedding: a watermark bit is embedded in each partition by altering the partition statistics while still verifying the usability constraints in G. This alteration is performed by solving a constrained optimization problem.
Step E3: Optimal threshold evaluation: the bit embedding statistics are used to compute the optimal threshold T∗ that minimizes the probability of decoding error.
Watermark Decoding
The watermark decoding is divided into three main steps:
Step D1: Data set partitioning: by using the data partitioning
algorithm used in E1, the data partitions are generated.
Step D2: Threshold based decoding: the statistics of each partition are evaluated and the embedded bit is decoded using a threshold based scheme based on the optimal threshold T∗.
Step D3: Majority voting: The watermark bits are decoded using a majority voting technique.
Watermark Encoding Algorithms
Data Partitioning
Watermark Embedding
Single Bit Encoding
Genetic Algorithm Technique
Pattern Search Technique
Watermark Embedding Algorithm
Watermark Decoding Algorithms
Decoding Threshold Evaluation
Watermark Detection
Attacker Model:
Deletion Attack
Alteration Attack
Insertion Attack
Watermarking Relational Databases Using Optimization- Based Techniques
Abstraction
Proving ownership rights on outsourced relational databases
We present a mechanism for proof of ownership based on secure embedding of robust(Sturdy in construction)
Here we formulate the constrains and discuss efficient tech to solve the optimization prob and to handle the constrains
Overcomes a major weakness in previously proposed tech
Probability of decoding errors are minimized by an optimal threshold(Threshold-Based Tech)
Introduction
Enforcing data ownership is an important requirement which requires articulated solutions
In last years watermarking techniques have emerged as an important building block which plays a crucial role in addressing the ownership problem.
A watermark describes information that can be used to prove the ownership of data, such as the owner, origin, or recipient of the content.
Watermarking techniques have been developed for video, images, audio, and text data and also for software and natural language text
application contexts for which data represent an important asset, the ownership of which must thus be carefully enforced.
For example, of weather data, stock market data, power consumption, consumer behavior data, medical and scientific data
Watermarking
Main Contribution
We formulate the watermarking of relational databases as a constrained optimization problem, and discuss efficient techniques to handle the constraints. We present two techniques to solve the formulated optimization problem based on genetic algorithms and pattern search techniques.
We present a data partitioning technique that does not depend on marker tuples to locate the partitions and thus it is resilient to watermark synchronization errors.
We develop an efficient technique for watermark detection that is based on an optimal threshold. The optimal threshold is selected by minimizing the probability of decoding error.
With a proof of concept implementation of our watermarking technique, we have conducted experiments using both synthetic and real-world data. We have compared our watermarking technique with previous approaches shows the superiority of our technique with respect to all types of attacks.
Related Work
1. Agrawal proposed a watermarking algorithm that embeds the watermark bits in the least significant bits (LSB) of selected attributes of a selected subset of tuples
This technique does not provide a mechanism for multi bit watermarks; instead only a secret key is used.
For each tuple, a secure message authenticated code (MAC) is computed using the secret key and the tuple’s primary key.
Hiding bits in LSB is efficient.
Problem : the watermark can be easily compromised by very trivial attacks.
2. Sion et al proposed a watermarking technique that embeds watermark bits in the data statistics.
data partitioning technique used is based on the use of special marker tuples which makes it vulnerable to watermark synchronization errors resulting from tuple deletion and tuple insertion; thus such technique is
not resilient to deletion and insertion attacks.
He recommend storing the marker tuples to enable the decoder to accurately reconstruct the underlying partitions
Problem: violates the blinded watermark detection property
Furthermore, Sion et al. proposed
a threshold technique for bit decoding that is based on two thresholds.
However, the thresholds are arbitrarily chosen without any optimality criteria.
Thus the decoding algorithm exhibits errors resulting from the non-optimal threshold selection
Even in the absence of an attacker.
Next Comes Gross-Amblard
Gross-Amblard proposed a watermarking technique for
XML documents and theoretically investigates links between query result preservation and acceptable watermarking alterations.
Another interesting related research effort is to be found in where the authors have proposed a fragile watermark technique
to detect and localize alterations made to a database relation with categorical attributes.
APPROACH OVERVIEW
The Main Components are as follows
Data set “D”
Data set “D” is transformed into a watermarked version “DW”
watermark encoding function that also takes as inputs a secret key “Ks”
only known to the copyright owner and a watermark “W”
Watermarking modifies the data.
modifications
are controlled by providing usability constraints referred to by the set G.
Watermarking Encoding
summarized by the following three steps:
Step E1: Data set partitioning: by using the secret key Ks
the data set D is partitioned into m non-overlapping partitions {S0, . . . , Sm−1}.
Step E2: Watermark embedding: a watermark bit is embedded in each partition by altering the partition statistics while still verifying the usability constraints in G. This alteration is performed by solving a constrained optimization problem.
Step E3: Optimal threshold evaluation: the bit embedding statistics are used to compute the optimal threshold T∗ that minimizes the probability of decoding error.
Watermark Decoding
The watermark decoding is divided into three main steps:
Step D1: Data set partitioning: by using the data partitioning
algorithm used in E1, the data partitions are generated.
Step D2: Threshold based decoding: the statistics of each partition are evaluated and the embedded bit is decoded using a threshold based scheme based on the optimal threshold T∗.
Step D3: Majority voting: The watermark bits are decoded using a majority voting technique.
Watermark Encoding Algorithms
Data Partitioning
Watermark Embedding
Single Bit Encoding
Genetic Algorithm Technique
Pattern Search Technique
Watermark Embedding Algorithm
Watermark Decoding Algorithms
Decoding Threshold Evaluation
Watermark Detection
Attacker Model:
Deletion Attack
Alteration Attack
Insertion Attack
