• Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

A bucketing framework for Database security

Extracts from this document...

Introduction

image51.pngimage52.pngimage53.png

Query-Optimal-Bucketization and Controlled-Diffusion algorithms for privacy in outsourced databases

National University of Singapore, School of Computing

CS5322 Databases Security - 2009/2010 (Semester 2) - Project Report

Rattanak CHHUNG

A0066240N

NUS - SoC, Singapore

Supélec, France

[email protected]


Damien FOREST

A0066246A

NUS - SoC, Singapore

Supélec, France

[email protected]

Yann-Loup PHAN VAN SONG A0066238B

NUS - SoC, Singapore Supélec, France [email protected]


Monika

A0066244H

NUS - SoC, Singapore

[email protected]

ABSTRACT

For the Databases  Security  project,  we choose to make a Java implementation of the solutions showed in [4].  The context of this paper is the classic paradigm of database outsourcing and privacy threats.  Our paper provides some explanations of [4] and of our choices of implementation.

Keywords

database, security, privacy, encryption, query, index, java, Query-Optimal-Bucketization, Controlled-Diffusion, attack.

1.   THE ORIGINAL PAPER

In this section we will quickly introduce the notions pre- sented in [4].  We advice the reader to refer at least to the table 1:  Notation  for Bucket of [4] page 722.  We  will be more precise in the section 3 where we will detail our imple- mentation.

1.1   Context and preliminaries

In the first assignment we studied [3, 1], where the problem is to assure privacy and confidentiality on untrusted server. [4] deals with  the same problem.  The solutions introduced

image00.pngThis paper is based on the work of [4]. This paper has 9 pages.

Version of April 12, 2010.


in [1, 3, 4] use indexes to make basic operations on encrypted tuples.

A partition is an ensemble of buckets that are represented by the indexes.  It is used to create privacy on an sensitive column of the  relation  which  are used to  make the  basic operations (usually selections).  An example is given below:

Example 1. 1  Consider the table 1 (page 1) reprensenting the clear-text taple.

I d

N ame

Addr

One

T wo

23

Tom

Paris

70

40

860

Mary

Metz

60

80

320

John

Tours

50

50

875

Jerry

Jakarta

55

110

Table 1: Representation of the clear-text table

The  sensitive  attribute  consided from the  selection  are Id, One and Two.

...read more.

Middle

image12.pngwhere E(X ) =   n


pi  × xi


distribution of X’b Xi is a guessed value from X’b

If the dimension of X superior is to one, we use the Euclidean norm to generalize  the  distance  between xi   and E(X ).  It gives:

n

Var(X ) = ) pi  ×  xi  E(X )2

i=1


Goal of adversary: to estimate the true value of a random element chosen from the bucket B.

In this project, our group also comparing the result of ASEE

formula above with the theorem 4.2, which defined in [4].


5

3

7

6

1

9

5

9

8

6

8

6

3

4

8

3

1

7

2

6

6

2

8

4

1

9

5

8

7

9

Propriety 1. This theorem explicit a relation between ASEE, variances and expectations of random variables.

ASEE(X, X t ) = Var(X ) + Var(X t ) + (E(X ) E(X t ))2

3.4        Bucketization algorithms

3.4.1        Query-Optimal-Bucketization (QOB)

Damien

3.4.2        Controlled-Diffusion (CD)

YL

4.        CONFRONTATION OF THE QOB BUCK-


Table 3: Deductive Sudokus are easy, right?

image13.png12

ETIZATIONS

In [4], they have introduced composite buckets, which is suppose to  answer a lake  of privacy of the  QOB “cutting” partition (but not the mapping of the indexes). We want to show this lake of privacy, by making two attack algorithms.

4.1   Assumptions

We assume that the attacker can access the encrypted table and knows the partition and the exact distribution (i.e. the DataSet of the table).


10

7

6

5         5

4    4

3    3

2         2

1    1         1         1

image14.png0


8

7

6

4

3

2

1         1    1

The objective of the attacker is to obtain the mapping the indexes and the partition.  In that case He will be able to place each eTuple (the old and the new ones) into its asso- ciate buckets and he can know a approximation (depending of the width of the buckets) of the sensitive columns.

4.2   Our Basic Attack Algorithm (BAA)

4.2.1  Principle

RATTA

4.2.2  Pseudo-Code

RATTA

4.3   Our Sudoku Attack Algorithm (SAA)

4.3.1  Origin of the name

We  have called  it Sudoku Attack  Algorithm, because  the way we found the mapping is deductive, like medium level Sudoku are.

...read more.

Conclusion

c r ypted Date in the

Database-Service-Provider Model. In SIGMOD ’02: Proceedings of the 2002 ACM SIGMOD international conference on Management of data, pages 216–227, New York, NY, USA, 2002. ACM.

[4] B. Hore, S. Mehrotra, and G. Tsudik. A

Privacy-Preserving Index for Range Queries. In VLDB

’04:  Proceedings of the Thirtieth international conference on Very large data bases, pages 720–731. VLDB  Endowment, 2004.

[5] JUnit. http://www.junit.org/.

[6] Project  Locker. https://www.projectlocker.com/. [7] Subclise. http://subclipse.tigris.org/.

image29.png[8] Gaussian distribution. http://en.wikipedia.org/wiki/Gaussian distribution.

[9] Sudoku.  http://en.wikipedia.org/wiki/Sudoku. [10] Variance - Discrete case.

image29.pnghttp://en.wikipedia.org/wiki/Variance#Discrete case.

APPENDIX

A.   INSTALLATION

[2] In this appendix you may find some basic instructions to help you using our Java project.  If you have some difficulties you can contact us during to the one week warranty.

5

3

4

6

7

8

9

1

2

6

7

2

1

9

5

3

4

8

1

9

8

3

4

2

5

6

7

8

5

9

7

6

1

4

2

3

4

2

6

8

5

3

7

9

1

7

1

3

9

2

4

8

5

6

9

6

1

5

3

7

2

8

4

2

8

7

4

1

9

6

3

5

3

4

5

2

8

6

1

7

9

A.1   Java Project

To install Eclipse, please refer to [2]

To import the project into Eclipse:

File -> New -> Java Project

Create  project  from existing  source :  selection  the  un-

zipped folder DatabasesSecurity

Write “DatabasesSecurity” in the Project Name (if nec-

essary)

click on Finish

If you are confortable with Eclipse and Subclipse you might want to download the project directly from our SVN, if you want to do so, please ask us a access to our Project Locker account on [6].

A.2   JUnit

We  used the  junit-4.8.1.jar, you can download it on [5], after that you might want to:

Right click on the DatabasesSecurity project -> Build

Path -> Configure Build Bath

Selection the Libraries  tab

Click on Add External JARs and selection the recently

downloaded .jar

Now you should be able to run the tests.  In order to do so, right click on what you want to run (the test source folder, a package or even a class) and Run As  -> JUnit Test.

The JUnit tab should automatically opens itself.

B.   SOLUTION OF THE SUDOKU

Here is the solution of the sudoku in the table 3 (page 5):


Table 6: The  solution of the sudoku

2009/2010 (Semester 2)         - 9 / 9 -


Monika Damien Forest Rattanak Chhung

Yann-Loup Phan  Van  Song

image54.pngimage55.pngimage56.png

...read more.

This student written piece of work is one of many that can be found in our University Degree Computer Science section.

Found what you're looking for?

  • Start learning 29% faster today
  • 150,000+ documents available
  • Just £6.99 a month

Not the one? Search for your essay title...
  • Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

See related essaysSee related essays

Related University Degree Computer Science essays

  1. Measurement of Processors Performance report. In the experiment, a testing code was developed in ...

    Set the initial region of the array to be accessed. 4) Record the initial system time by calling function my_clk() and store into variable t. 5) A. Perform the nested loop in which data in the array is read and stored into the variable sum again to overwrite its previous value thus a Sequential Access is done.

  2. The project explains various algorithms that are exercised to recognize the characters present on ...

    Image and High Resolution 26 5.2.2 Case 2: Low Quality Image and Poor Lighting Condition 28 5.2.3 Case 3: Blurry Image 29 5.2.4 Case Analysis 30 5.3 Implementation Results 31 5.3.1 Case 1: High Quality Image 31 5.3.2 Case 2: Low Quality Image (Plate Detection + Recognition)

  1. Information systems development literature review. Since the 1960s Methodologies, Frameworks, Approaches and CASE ...

    to analyse information, evaluating an IS project deployed throughout change within an organisation. A suitable framework was provided to tackle this complex situation regarding the relationship between Information Systems Development and the organisation, where roles were ill-defined and political tension was rife.

  2. Geometric Brownian Motion. The aim of this project is to gain an understanding ...

    coding within VBA, outputting graphs through built in functions such as command buttons with Microsoft Excel, both will calculate volatility and covariance of a stock. The returns and standard deviation for each company will also be calculated using built in functions in Microsoft excel.

  1. Ethics and professionalism in computing - examples from Facebook and Google

    In particular: � They encrypt many of their services using SSL. � They offer you two step verification when you access your Google Account, and a Safe Browsing feature in Google Chrome. � They review their information collection, storage and processing practices, including physical security measures, to guard against unauthorized access to systems.

  2. Lifecycle Management Of Information Technology Project In Construction

    ?uch, paper i? largely conceptual in nature. Future work will include further development of propo?ed ?olution? and indu?trial experimentation and validation. Limitation of ?tudy A number of limitation? of our ?tudy mu?t be mentioned. The?e limitation? al?o provide avenue? for further re?earch. A major limitation i? that only one organization wa?

  1. Data Warehouse Security

    Because of this new vulnerability, new security measures were needed to be established. With the rising trend towards flatter, more horizontally structured companies, new security measures are required that enable a division within the company to view only the data that is relevant to them, yet allow employees on the

  2. Implementation of Path Finding Techniques in Homeland Security Robots

    An improvement to the A* algorithm has been implemented. In this thesis it has been proved through experimental results that the performance of the A* algorithm improves drastically after adding an additional heuristic. Dynamic path finding techniques is an extension of normal path finding.

  • Over 160,000 pieces
    of student written work
  • Annotated by
    experienced teachers
  • Ideas and feedback to
    improve your own work