Current MS Students/Kanaka Rajanala/My Prospectus
From CSWiki
Thesis: Tamper detection in Multi Owner Databases
Contents |
[edit] What I am planning to accomplish
[edit] (Thesis) Issues to be investigated
In recent times, database relations are widely used and distributed over the internet. Since this data can be easily tampered , some watermarking techniques are designed to detect the data tampering. The current database watermarking techniques require a secret key to generate and embed the watermark into the tables. Once the table is watermarked, any tampering to the table can be detected using the secret key. The secret key is known to the database owner. In multi owner databases the same secret key is shared by all the owners of the database. The sharing of the secret key can be problematic if one of the owners is malicious. He can tamper the data, regenerate the watermarked table and can escape without being identified.
To be able to solve this problem we need to have a mechanism where in, any single owner should be able verify the data tampering but all owners or a group of owners are required to be able to generate/regenerate and embed the watermark. For example, if there are “n” owners, the secret key should be divided and shared in such a way that any “t” owners (where t < n) can generate the complete key which can be used to generate and embed the watermark. Also, any individual owner should be able verify the data tampering. To achieve this multiple watermarks may need to be embedded into the tables.
This problem of dividing the secret key to multiple owners can be solved by using secret sharing schemes such as Shamir’s secret sharing scheme or Ito’s generalized secret sharing scheme.
Using these secret sharing schemes, the key can be divided into multiple pieces say “n” and each owner gets one piece. Any “t” (where t < n) owners will be able to reconstruct the whole key using their individual keys.
A new watermarking scheme for databases needs to be designed where in a single owner can verify the data tampering using his piece of the secret key but all or group of owners are required to generate and embed the watermark.
Issue # 1: Design a new watermarking technique in which all the owners should come together to embed the watermark.
Issue # 2: Embed multiple watermarks so that any individual owner can verify whether the data has been tampered or not based on the part of his key. For example a single share point key should be enough to detect the tampering.
Issue # 3 : Since this logic requires embedding multiple watermarks, a new watermarking scheme needs to be designed.
Issue # 4: All the watermarks should be designed in such a way that the data will not be distorted. In other words, the watermarks should be fragile and the data should be distortion free when embedded.
[edit] (Thesis) Annotated table of contents
Literature study to understand all the existing techniques. Discussing the problem and possible solutions and approaches with the advisor. Come up with a list of suitable approaches or new algorithms. Prototype and test new algorithms. Refine the algorithms based on test results. Based on the test results select the most practical and efficient algorithm.
[edit] (Thesis) High level Architecture
[edit] Why this is academically interesting
[edit] Intended audience
Commercial enterprises providing database services through internet. Database owners and administrators
[edit] Why this is MS-level work
Database watermarking is a new expanding area and adequate research has not been done to detect data tampering in a multi owner environment. As the “Database As Service” (DAS) concept is evolving and gaining popularity in the research and commercial space, data tamper detection using watermarking techniques is becoming a crucial component of DAS architecture. This thesis proposing new algorithms to satisfy the watermarking requirements and tamper detection in multi owner databases.
This requires research and development and deep understanding of the areas such as databases, cryptography, watermarking, security, and mathematics and probability models.
The database technology needs to be studied to understand the underlying data storage techniques. This is required to embed the fragile watermarks without distorting the data.
The existing multimedia and database watermarking literature needs to be studied to understand different techniques employed currently. This is required to get the background and understanding of the existing technologies.
The security related algorithms such as Shamir’s secret key sharing needs to be studied which are required to divide the secret key among all the data owners.
New mathematical equations and formulas needs to be designed to be able to embed and detect data tampering. The probability models are required to identify the probability of successful tamper detection under the new watermarking scheme.
[edit] Previous work
[edit] Literature review
Tamper Detection and Localization for Categorical Data Using Fragile Watermarks
This paper, describes the technique that makes use of fragile watermarks to detect and localize malicious alterations made to a database relation with categorical attributes. Unlike other watermarking schemes which inevitably introduce distortions to the cover data, the proposed scheme is distortion free. In this algorithm, all tuples in a database relation are first securely divided into groups according to some secure parameters. Watermarks are embedded and verified in each group independently. Thus , any modifications can be localized to some specific groups. Theoretical analysis shows that the probability of missing detection is very low.
A novel approach to digital image watermarking based
on a generalized secret sharing scheme-Huiping Guo, Nicolas D. Georganas
This paper proposes a novel algorithm that makes use of a generalized secret sharing scheme in cryptography to address this problem. Given that multiple owners create an image jointly, distinct keys are given to only an authorized group of owners so that only when all the members in the group present their keys can the ownership of the image be verified. Any owner alone cannot verify the image ownership. In addition, experimental results show that the proposed algorithm has the desired properties such as invisibility, reliable detection, and robustness against a wide range of image-processing operations.
ChainingWatermarks for Detecting Malicious
Modifications to Streaming Data-Huiping Guo a Yingjiu Li b Sushil Jajodia
In this paper, we propose a novel fragile watermarking algorithm which verifies the integrity of streaming data at the application layer. The data are divided into groups based on synchronization points, so each group can be synchronized and any modifications made to one group only affect up to two groups. A unique watermark is embedded directly into each group to save communications bandwidth. The embedded watermark can detect as well as locate any modifications made to a data stream. To ensure the completeness of the data stream, watermarks are chained across groups so that no matter how many data are deleted, these deletions can be correctly detected. Security analysis and experimental results show that the proposed scheme can efficiently detect and locate modifications and ensure the completeness of data streams.
[edit] Anticipated challenge(s)
[edit] Challenge(s)
1. Desiging an algorithm that can embed multiple watermarks in the database.
2. Designing a technique such that any individual owner should be able to detect the data tampering with his part of the key.
3. Use a fragile watermarking scheme for embedding multiple watermarks in the database.
[edit] Anticipated approach to each challenge
1. Study all the existing watermarking techniques and understand the concepts developed.
2. Study the multimedia watermarking techniques and see if any concepts or ideas can be borrowed and applied to the database.
Suppose if there are two owners, we will have three keys k1, k2 which are derived using the master key and the master key k. Three individual watermarks will be generated based on these three keys {w1, w2, w3}. Using these three watermarks, a combined watermark called w will be generated and embedded. The logic of generating “w” has reverse formula using which we can generate {w1, w2, w3} call it w’. A correlation factor using the formula w * w’/|w’| is computed. Based on the correlation formula, given k1 or k2, the partial ownership can be verified and if both k1 and k2 are given or k is given, full ownership can be verified.
The above similar technique can be extended to database watermarking though which data tampering can be verified using any given individual key.
3. Study different commercial database architecture and identify a feasible watermarking embedding technique without data distortion.
[edit] What I bring to this work
[edit] My relevant background and experience (CS 590)
I did cryptography CS481 with Huiping Guo which will help in understanding the concepts of secret sharing algorithms. I did algorithms and database concept courses which will help me understand different algorithms and relational databases concepts. The mathematics and probability theory that I learnt in the bachelor’s degree will help me handle the complex mathematical formulas.
[edit] What I find interesting about this work
The reason why find this work interesting is it gives me an opportunity to design a new fragile watermarking algorithm which is very challenging. It also exposes me to many areas like relational databases, watermarking, security, and mathematics and probability models.
[edit] How this work goes beyond my experience and course work
This thesis requires a new algorithm to be developed that embeds multiple fragile watermarks into the database. This requires research and development of new watermarking techniques without data distortion which goes beyond my academic experience and course work.
