JXT & JXT+ & JXT++

This repo implements the join query schemes, for example, JXT [1], JXT+ and JXT++, and shows the constructions and comparison of them.

This work has been accepted by ACM CCS 2024.

Overview

• Background
• Features
• Installation
  • Prerequisites
  • Clone Repository
  • Build
  • Test
• Project structure
  • File tree
  • Data Description
• Validate Results
• Reuse Beyond the Paper
• Contact Information

Background

The corresponding works i.e., JXT, JXT+, JXT++, solve the join query over encrypted database. The project aims to implement JXT, JXT+ and JXT++ by JAVA, and show the comparison of their storage overhead and query efficiency.

Features

• Applied Cryptography
• Encrypted Database
• Join Queries
• JAVA

Installation

Prerequisites (Need Internet)

• A computer (Recommended configuration 16 GB RAM)
• JDK version 1.8.0
• Maven 3
• Recommended an IDE (IntelliJ IDEA), which will save plenty of time.

Clone Repository (Need Internet)

Download source code from Scalable Equi-Join Queries over Encrypted Database (zenodo.org).

Build (Need Internet)

Build the project using Maven:

mvn clean install

Test (No need Internet)

Test to run the java files

src/test/java/JXT.java
src/test/java/JXTp.java
src/test/java/JXTpp.java

Project structure

File tree

MJXT/
├── pom.xml
├── README.md
├── data																								
├──	├── *										//Datasets
├── src
│   ├── main
│   │   └── java
│   │       ├── client																	
│   │       │   ├── Setup_JXT.java				//Setup algorithm of JXT
│   │       │   ├── Setup_JXTp.java				//Setup algorithm of JXT+
│   │       │   └── Setup_JXTpp.java			//Setup algorithm of JXT++
│   │       ├── server
│   │       │   ├── Server_JXT.java				//Search algorithm of JXT
│   │       │   ├── Server_JXTp.java			//Search algorithm of JXT+
│   │       │   ├── Server_JXTpp.java			//Search algorithm of JXT++
│   │       │   ├── Server_MJXT.java			//Search algorithm of MJXT
│   │       │   └── Server_MJXTp.java			//Search algorithm of MJXT+
│   │       └── utils
│   └── test
│       └── java
│           ├── JXT.java						//JXT scheme
│           ├── JXTp.java						//JXT+ scheme
│           ├── JXTpp.java						//JXT++ scheme
│           ├── M_JXT.java						//MJXT scheme
│           ├── M_JXTp.java						//MJXT+ scheme
│           ├── Table_Gen.java					//Generate tables
│           ├── Table_Gen_Entropy.java			//Generate tables with diff entropy
│           ├── Table_Gen_Lmax.java				//Generate tables with diff Lmax
│           ├── test_JXT.java					//batch test JXT scheme
│           ├── test_JXTp.java					//batch test JXT+ scheme
│           ├── test_JXTpp.java					//batch test JXT++ scheme
│           ├── test_JXTpp_Lmax.java			//batch test JXT++ scheme for diff Lmax
│           ├── test_Setup.java					//test setup time for three schemes
│           └── test_storage.java				//test storage overhead for three schemes
└── target (generated after build)

Data Description

The tables have the naming rules, for example "table1_k5_j5_65536.csv" where "1" denotes the table index, "k5" and "j5" means that there are 5 columns (as attributes, not join attributes) and 5 columns (as join attributes), "65536" means the number of records. Particularly, there are some special tables, for example, "table1_k9_j1_65536_12.csv" where "12" denotes the entropy of join-attribute corresponding to queried attribute value is 12; "table1_k9_j1_65536_Lmax100.csv" where "Lmax100" means the Lmax for the join attribute is 100.

Note that all tables for experiments have been generated, and there is no need to generate new table for result.

For "table*_k*_j*_65536.csv", they have follwoing feature

Attribute value	# records	Number of query result
table1_keyword_0_0	1000	1000
table1_keyword_0_1	2000	2000
table1_keyword_0_2	3000	3000
......	.......	......
table1_keyword_0_8	9000	9000
table1_keyword_0_9	10000	10000
table1_keyword_0_10	1000	100
table1_keyword_0_11	1000	200
table1_keyword_0_12	1000	300
......	......	......
table1_keyword_0_18	1000	900
table1_keyword_0_19	1000	1000

For "table1_k9_j1_65536_*.csv", they have follwoing feature

Table name	Attribute value	# records	# occurrence for each join attribute
table1_k9_j1_65536_12.csv	table1_keyword_0_0	256	16
table1_k9_j1_65536_14.csv	table1_keyword_0_0	256	4
table1_k9_j1_65536_16.csv	table1_keyword_0_0	256	1

For "table1_k9_j1_65536_Lmax100.csv", they have follwoing feature

Attribute value	# records	Number of query result	# occurrence for each join attribute
table1_keyword_0_0	1000	1000	100

Validate Results

The output of the experiments will validate the following claims:

• Figure 1 : run src/test/java/test_storage.java and set join_column from 1 to 5.
• Figure 2 and Figure 3 : run src/test/java/test_JXT.java, src/test/java/test_JXTp.java and src/test/java/test_JXTpp.java, you will get lines for JXT, JXT+, JXT++. Note that the result of keyword0-keyword9 belongs to Figure 2 which corresponds to its x-axis 1000-10000 , and keyword10-keyword19 belongs to Figure 3 which corresponds to its x-axis 10%-100%.
• Figure 4 : run src/test/java/test_Setup.java set join_column from 1 to 5.
• Figure 5 : run src/test/java/JXTpp.java, src/test/java/M_JXT.java, src/test/java/M_JXTp.java and set table_num from 2 to 6.
• Figure 6 : run src/test/java/test_JXTpp_Lmax.java.
• Table 3 : run src/test/java/test_storage.java and set join_column = 1, set condition as _16,_14,_12.

Reuse Beyond the Paper

You can reuse the project by exchanging the dataset which you want to setup and search, but notice that you need to change the variants key_colnum,join_column,record_num and the path of your dataset (recommended that put your dataset in /data/).

Contact Information

You can reach us at:

• Author: Kai Du, Jianfeng Wang
• Email: [email protected], [email protected]

Reference

[1] Charanjit Jutla and Sikhar Patranabis. 2022. Efficient searchable symmetric encryption for join queries. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 304–333.