From CSULA CS Wiki
Jump to: navigation, search


Jan 5 (week 1)

Jan 12 (week 2)

This week I consulted my advisor Huiping Guo regarding thesis and she gave me some research papers and some tutorials to go through. The papers are related to Database security, some of the papers are related to privacy and some are related to outsourced database security. I am currently in the processes of going through them.

Huiping Guo asked to read the tutorial before jumping on to the research topic. The tutorial gives the overview of cryptography, data outsourcing, query correctness, data confidentiality, access privacy, searching for encrypted data and trusted hardware.

This week I studied about cryptography related topics. I studied about public key encryption, digital signatures and public key infrastructure.

Jan 19 (week 3)

This week I studied one of the research paper given by my advisor HuipingGuo. The paper is about Authentication and Integrity in Outsourced Databases.

In outsourced database model, organizations outsource their data management needs to an external provider. The service provider host client databases and offer seamless mechanisms to create, update, store and access (query) their databases. One of the core security requirements is providing efficient mechanisms to ensure data integrity and authentication while incurring minimal computation and bandwidth overhead. In this paper the author investigated the problem ensuring of data integrity and suggest secure and practical schemes that help facilitate authentication of query replies.

By outsourcing, organizations can concentrate on their core tasks and operate other business applications via internet rather than incurring substantial software, hardware and personal costs involved in maintaining applications in-house. One of the foremost challenges is the security of the stored data at external, untrusted database service providers. It is essential to provide security from both malicious attackers and database providers itself.

The outsourced database is an example of client-server model. In ODB model the Database Provider has infrastructure to host outsourced databases and provides efficient mechanisms for the clients to create, store, update and query the database. There are flavors of ODB model.

Unified Client Model: This is the most basic setting in each outsourced database is used by single entity, in which the client, who creates, manipulates and the quires the database are same.


MultiQuerierModel: In this there are two types of clients: owners and queriers. The owner can create, update and delete records where as querier is a client only allowed to read access (query) the database.


MultiOwnerModel: In this a single database can have multiple owners.


The focus on this paper is integrity and authentication. The optimal way to provide data integrity/authentication is at record level. The MAC can provide record level integrity which is best suited for Unified Client Model. For other model the only choice is public key digital signatures.

This paper mainly focused on Condensed-RSA for integrity/authentication. In condensed-RSA given input messages and their corresponding signatures, a Condensed RSA is given by the product of the individual signatures.The resulting signature has the same size as a standard RSA signature. When verifying a condensed signature, the verifier needs to multiply the hashes of all input messages.

This paper claims that security of Condensed-RSA is as secure as Batch-RSA which in turn is was shown to be secure under the assumption that RSA is a collection of one way functions.

In this signature scheme .The server performing the client query is required to perform the following: select records that match query predicate; fetch the signatures corresponding to these records; aggregate them and send back the single aggregated signature along with the records in the result set. Condensed RSA helps save both quierier computation and quierier bandwidth.

This paper also discusses about Batch verification of RSA signatures, BGLS and Merkel hash trees. I didn’t go through all of them.


Jan 26 (week 4)

This week I studied a tutorial given by Huiping Guo. She asked me to read this tutorial before deciding on the thesis topic about outsourced databases. This tutorial gives the high level concepts of the components involved in Database Outsourcing. The tutorial gives a brief idea about cryptography, data outsourcing, query correctness, data confidentiality, access privacy and searching encrypted data.

In cryptography section it describes about Crypto Hashes, public key encryption, signatures, ciphers, semantic security, forward secrecy, performance and merkel-hash tress. In data outsourcing sections it gives the idea about what are the challenges involved in outsourced database.

I read some sections of the tutorial and plan to read the remaining sections in next week. This tutorial help me to understand the various components involved in database outsourcing.

Tutorial [1]

Feb 2 (week 5)

This week I met my advisor and she suggested an interesting thesis topic. It is extension of her work. Her work is based on providing integrity to databases using fragile watermarking to detect and localize malicious alterations made to database relation with categorical attributes. In her work, she covered where the changes have been occurred in database, but does not identify who made the changes in multi owner database scenario (everybody share a single secret key). If one of the owners becomes malicious and tries changes the data, the current infrastructure can’t detect who changed it since all the owners share the same key. My work is to find a way to assign a single secret key to each individual owner and identify the owner who changes the data in the database.

Since her work is based on watermarking relational databases to maintain the integrity,I studied on how to do watermarking in relational databases. The paper recommends a bit injection technique which ensures that some bit positions of some of the columns of some of the rows contain specific values. The rows, columns within a row, bit positions in an attribute, and specific bit values are all algorithmically determined under the control of a private key known only to the owner of the data. This bit pattern constitutes the watermark.

I learnt that even though there are lot of existing techniques developed and used for watermarking of the digital images and videos (multimedia), they can’t be used as is for relational databases. This is because there is lot of redundancy in multimedia watermarking; the multimedia content will not change or can’t be altered. However, in a database, the rows and columns values can be altered any time and having high redundancy will cause data explosion.

Studying to understand the finer details of how the watermarking bits are generated and injected into the table rows.

Apart from this I studied and learnt about JUnit for next week presentation. It is an open source framework which is used to write and run automated tests. JUnit features include assertions for testing expected results, test fixtures for sharing common test data, test suites for easily organizing and running tests and graphical and textual test runners.

I ran a simple example in JUnit using Eclipse platform. First I wrote a simple calculator class

 public class Calculator {
   public int add(int x, int y) {
       return x+y;
  public int subtract(int x, int y) {
       return x-y;
  public int multiply(int x, int y) {
       return x*y;
  public int divide(int x, int y) {
       return x/y;

Then in the Eclipse IDE ,under the same package as Calculator class ,select a Junit and in this we should write the tests that we want to test for the calculator class

 public class CalcTest extends TestCase {
    public void testAddition() {
     Calculator calc = new Calculator();	    
     int expected = 7;
     int actual = calc.add(3, 4);
     assertEquals("adding 3 and 4", expected, actual);
  public void testDivision() {
    Calculator calc = new Calculator();		    
    try {
     fail("Should have thrown an exception!");
    catch (ArithmeticException e) {
    // Good, that's what we expect

This class extends TestCase which holds a number of test methods. The JUnit uses assert methods to see if we get expected results. In the above example we wrote the two tests. If both the tests pass then in the JUnit console we get a green bar indicating all the tests are passed. If any of the tests fails then we get a red bar and highlight the test cases that are failed.

Feb 9 (week 6)

This week I studied a research paper given by my advisor. This paper is about how to use fragile watermarks to detect and localize malicious alterations made to database relation with categorical attributes. The watermark used in this paper is distortion free compared to other watermarks that are used in relational databases. For digital watermarking in databases, there are two types of watermarking. One is robust watermarking which is used for ownership verification and other is fragile watermarking which is used for tamper detection.

The main challenge in this paper is to find a way for watermarking to embed an invisible watermark in the database relation. This can be done using fragile watermarking. The watermark is embedded by first calculating the hash value for each row in conjunction with the embedding key (secret key known only to authorized persons).Then group hash is then calculated using primary key and embedding key. Then the rows are grouped and then sorted within the group based on their primary key hash value.


Suppose let us consider these two are the same tables before watermark embedding and after watermark embedding. First the rows are made into groups .Lets consider these are made into two groups ,the shaded ones belong to a group and remaining one belong to another group. Then watermark bits are grouped and the number of bits will be number of rows in a group by 2 because with an group again the rows are taken as a pair. Lets consider the water mark bits be {0,1} is to embedded. To embed the watermark into the group 1, we take the row pair {1009, 1005}. Since first watermark bit is zero 0 and the first tuple hash is larger than the second one, the two tuples are switched. The other two tuples in the second pair remain untouched because a watermark bit 1 is embedded and the first tuple hash is already larger than the second one. Similarly, the second group is watermarked and the watermarked table is shown on the right.

This week I met the advisor regarding the watermark embedding algorithm. First I didn’t get a clear picture of the algorithm; I thought they will inject watermark bits into the data. But later I learnt that the watermark bits are used to order the rows in the table based on the hash value and there will be no injection of the bits into the data that is the reason why this algorithm is distortion free.

Feb 16 (week 7)

This week I studied how to detect watermark in the database relation. In verification algorithm first all the rows are divided into groups and sorted just like embedding algorithm and in the similar way the watermark is calculated. Then, the watermarking that is actually embedded is extracted from the rows. For every row pair if the first row is larger than the second row then the watermark bit is 1 otherwise it is 0. Then the extracted watermark is checked against the embedded watermark, if both of them match then data has not been tampered. The embedding capacity of the rows can be increased by dividing the groups into subgroups again. For database relations without a primary key, row hash can be used to group and sort rows. When we are inserting a new row we have to recalculate only that particular group watermarks. Apart from this I started working on the prospectus.

Feb 23 (week 8)

This week I learnt about shamir’s secret sharing algorithm. It is a form of secret sharing where a secret is divided into parts, giving each participant its own unique part, where some of the parts or all of them are needed in order to reconstruct the secret.If we want n secret keys then we should pick k value which is k < n and n unique keys are given to n people. Knowledge of k pieces can easily construct the key i.e. we need to know at least k pieces to reconstruct the key. Polynomial by interpolation is used to find the secret key

Presentation Slides:Media:Cs590-2.ppt

My Prospectus

Mar 1 (week 9)

This week I studied about some of the secret sharing algorithms and worked my prospectus.This algorithm shows how can we divide an single secret among different members in the group.Today in the presentation I am going to present one of the algorithm and if time permits I will talk about my prospectus.

My Prospectus

Presentation slides Media:Secret_Sharing_Algorithms.ppt‎

Mar 8 (week 10)

This week I discussed with my advisor regarding all issues that I am trying to solve in the thesis. I wrote my prospectus based on the recommendations given by my advisor. Here is the updated version of prospectus.

Here is the updated Prospectus

My Prospectus

Mar 15 (week 11)

My Prospectus