This project is a python3 implementation of the paper Secure k-Nearest Neighbor Query over Encrypted Data in Outsourced Environments.
All code is written in python3. The Paillier encryption library phe
requires GNU multiprecision library for large number calculations.
These dependencies can be installed using
sudo apt install libmpc-dev
sudo pip3 install gmpy2 phe
On some systems these may fail or require manual installation. If there are issues installing the dependencies, contact Dalton Cole or Samuel Grush.
Communication between the parties is networked on localhost by default. The server and client must each be run independently to start a session. In one terminal, type
./server.py
In a second terminal, type
./client.py
After running key generation you will be asked for a functionality to perform. Selecting a functionality will provide all instructions needed for that specific function.
The server represents P1 (or Bob for SkNN)
usage: server.py [-h] [port]
positional arguments:
port port to listen on (default: 49556)
optional arguments:
-h, --help show this help message and exit
--host HOST hostname to listen on (default: localhost)
The client represents P2 (or C1/C2 for SkNN) and is the private key holder.
usage: client.py [-h] [-s SK] [-o OPT] [port]
positional arguments:
port port to connect to (default: 49556)
optional arguments:
-h, --help show this help message and exit
--host HOST hostname to connect to (default: localhost)
-s SK, --secret-key SK
pregenerated secret key. If omitted we will generate a
key pair.
-o OPT, --option OPT the option to execute. Start interactively to see
available options
Keys can manually be generated by running ./keys.py
. Alternatively, this will
automatically be performed when a session is created between the server and client.
optional arguments:
-h, --help show this help message and exit
--name NAME Base file name for the output files.
-p, --pq Generate from p and q values.
-b, --bit Generate by bit-length.
Example:
./keys.py --name testk -b
Enter a bit-length for n (default: 2048): 1024
Wrote pk to 'testk.public.json'
Wrote sk to 'testk.private.json'
database.py performs Paillier encryption of CSV databases. Functions 1-6 can be performed without a database, but this step is necessary for performing SkNN.
usage: database.py [-h] [--csv CSV] [--key KEY] [--name NAME]
optional arguments:
-h, --help show this help message and exit
--csv CSV Unencrypted CSV database to read.
--key KEY Key to encrypt the database with.
--name NAME Base file name for the output file.
First you must have a database represented in CSV format, for example
1,2,3,8
4,5,6,25
7,8,9,3
Assuming this file is named database.csv
and you have already generated a public key called testk
,
you can encrypt the database as encrypted.enc.csv
by running
./database.py --csv database.csv --key testk.public.json --name encrypted
- Secure Multiplication
- Secure Minimum
- Secure Squared Euclidian Distance
- Secure Bit Decomposition
- Secure Bit-OR
- Secure Minimum-of-n
- Secure k-Nearest Neighbors
Secure Multiplication runs the secure multiplication protocol on two numbers entered by the server and client.
- Run
server.py
andclient.py
in two separate terminals - Server: Enter u
- Client: Enter v
Example:
./server.py
Secure multiplication selected, please enter u: 2
./client.py -s testk.private.json -o 1
Secure multiplication selected, please enter v: 3
u * v = 6
Secure Minimum returns the smaller of the two numbers entered by the server and client. The maximum bitlength assumed is 32.
- Run
server.py
andclient.py
in two separate terminals - Server: Enter u
- Client: Enter v
Example:
./server.py
Secure minimum selected, please enter u: 5
./client.py -s testk.private.json -o 2
Secure minimum selected, please enter v: 1
Min(u, v) = 1
SSED calculates the squared euclidian distance between two encrypted vectors.
- Run
server.py
andclient.py
in two separate terminals - Server: Enter comma-delimited vector u
- Client: Enter comma-delimited vector v
Example:
./server.py
Secure squared euclidean distance selected, please enter u:
Enter comma delimited vector:
1,2,3,4,5
./client.py -s testk.private.json -o 3
Secure squared euclidean distance selected, please enter v:
Enter comma delimited vector:
5,4,3,2,1
SSED(u, v) = 40
Secure Bit Decomposition breaks an encrypted number into its encrypted big-endian binary representation.
- Run
server.py
andclient.py
in two separate terminals - Client:
- Enter x (number to decompose)
- Enter m (bitlength)
Example:
./server.py
Secure bit decomposition selected.
./client.py -s testk.private.json -o 4
Secure bit decomposition selected, please enter x: 13
Enter a bitlength m (or default to len(x)): 8
Received [x] from server.
Decrypted; x-decomp: [0, 0, 0, 0, 1, 1, 0, 1]
Secure Bit-OR performs the OR operation between two encrypted bits.
- Run
server.py
andclient.py
in two separate terminals - Server: Enter
0
or1
- Client: Enter
0
or1
Example:
./server.py
Secure Bit-OR selected, please enter o1 [0,1]: 0
./client.py -s testk.private.json -o 5
Secure Bit-OR selected, please enter o2 [0,1]: 1
Sent o2 to server
OR(o1, o2) = 1
Secure Minimum-of-n performs SMIN for arbitrarily many values.
- Run
server.py
andclient.py
in two separate terminals - Client: Enter space-separated list of numbers
Example:
./server.py
Secure minimum-of-n selected.
./client.py -s testk.private.json -o 6
Secure minimum-of-n selected, please enter some numbers: 15 16 42 23 4 8
Sent [d] to server.
min(d) = 4
- Three terminals: Bob, C1, C2
- The database, a CSV file of integers
- C2:
- Run
./keys.py --name testk
to interactively generate a Paillier key pairtestk.private.json
andtestk.public.json
. - Run
./database.py --name testdb --key testk.public.json
to encrypt your database intotestdb.enc.csv
; make this accessible to C1.
- Run
- Bob:
- Run
./server.py
to start the server.
- Run
- C2:
- Run
./client.py -s testk.private.json -o c2
to start client C2.
- Run
- C1:
- Run
./client.py 49557 -o c1
to start client C1.
- Run
- Bob:
- Enter your query Q, a set of space-separated values, the same width as a database row.
- Enter k, the number of results.
- C1:
- Enter the database name
testdb.enc.csv
- Enter the database name
- Bob:
- Choose the output method for the result.
p
to print,c
for CSV.
- Choose the output method for the result.