README.md 4.77 KB
Newer Older
Aditya Damodaran's avatar
Aditya Damodaran committed
1
2
3
4
<!--
SPDX-FileCopyrightText: 2021 University of Luxembourg
SPDX-License-Identifier: GPL-3.0-or-later
SPDXVersion: SPDX-2.2
Aditya Damodaran's avatar
Aditya Damodaran committed
5

Aditya Damodaran's avatar
Aditya Damodaran committed
6
7
8
9
Authors: 
       Aditya Damodaran, aditya.damodaran@uni.lu
       Alfredo Rial, alfredo.rial@uni.lu
-->
Aditya Shyam Shankar Damodaran's avatar
Aditya Shyam Shankar Damodaran committed
10
11
# Unlinkable Updatable Hiding Databases and Privacy-Preserving Loyalty Programs

Aditya Damodaran's avatar
Aditya Damodaran committed
12
This repository contains the source code for an implementation of the HD (Unlinkable Updatable Hiding Database) primitive described in our paper titled "Unlinkable Updatable Hiding Databases and Privacy-Preserving Loyalty Programs", to be published at PETS 2021. It also includes an implementation of the Privacy-Preserving Loyalty Program protocol put forward in this paper, which uses the aforementioned primitive. 
13
14

These implementations were used to measure the storage and computation costs of the cryptographic operations in our primitive and the protocol, for the _Efficiency Analysis_ sections of our paper.
Aditya Shyam Shankar Damodaran's avatar
Aditya Shyam Shankar Damodaran committed
15
16


Aditya Damodaran's avatar
Aditya Damodaran committed
17
## Installation
Aditya Shyam Shankar Damodaran's avatar
Aditya Shyam Shankar Damodaran committed
18

Aditya Damodaran's avatar
Aditya Damodaran committed
19
### Virtual Machine (Vagrant)
20
21
22
23
24
25
You can the use `Vagrantfile` file in this repository to spin up a virtual machine with a pre-configured execution environment using Vagrant: https://www.vagrantup.com.

You must first install Vagrant, and then run the following command from the root directory of this repository:
```bash
$ vagrant up
```
Aditya Shyam Shankar Damodaran's avatar
Aditya Shyam Shankar Damodaran committed
26

Aditya Damodaran's avatar
Aditya Damodaran committed
27
28
Once the virtual machine is ready, log in with `vagrant:vagrant`.

29
The code will then be accessible from the `/vagrant` directory, in the virtual machine window that shows up after the script downloads and installs all prerequisites.
Aditya Shyam Shankar Damodaran's avatar
Aditya Shyam Shankar Damodaran committed
30

Aditya Damodaran's avatar
Aditya Damodaran committed
31
32
### Manual Installation (Ubuntu)

Aditya Shyam Shankar Damodaran's avatar
Typo    
Aditya Shyam Shankar Damodaran committed
33
Instructions are available [here](doc/install_bionic.md).
Aditya Shyam Shankar Damodaran's avatar
Aditya Shyam Shankar Damodaran committed
34

Aditya Damodaran's avatar
Aditya Damodaran committed
35
### Manual Installation
36
Our code requires Python 3.6, and the Charm-Crypto library (v0.50) built with the Relic Toolkit (v0.5.0), as described on these pages:
Aditya Shyam Shankar Damodaran's avatar
Aditya Shyam Shankar Damodaran committed
37

38
1. Relic Toolkit: https://jhuisi.github.io/charm/relic.html#charm-with-relic
39

40
41
42
43
   (Download Relic from its [github repository](https://github.com/relic-toolkit/relic) and checkout the version identified by commit id `0534bd5cc7`.)
2. Charm-Crypto:  https://jhuisi.github.io/charm/install_source.html#platform-install-manual
   
   (Download Charm from its [github repository](https://github.com/JHUISI/charm))
44
45
> Note: Charm-Crypto additionally requires PBC (v0.5.14) and GMP (v6.2.1). 

Aditya Damodaran's avatar
Aditya Damodaran committed
46
Finally, use the following command to install Openpyxl (v3.0.6) and Texttable (v1.6.3): 
47
48
49
```bash
$ python3 -m pip install -r requirements.txt
```
Aditya Shyam Shankar Damodaran's avatar
Aditya Shyam Shankar Damodaran committed
50
51


Aditya Damodaran's avatar
Aditya Damodaran committed
52
## Usage
Aditya Shyam Shankar Damodaran's avatar
Aditya Shyam Shankar Damodaran committed
53
```bash
54
55
56
57
58
59
60
61
62
Usage: python3 ./protocol.py [-h] [-k K] [-r] N

positional arguments:
  N                    Database size (100-65000)

optional arguments:
  -h, --help           show this help message and exit
  -k K, --keylength K  Paillier Encryption key size (Supported values: 1024, 2048)
  -r, --randomise      Randomise database state 
Aditya Shyam Shankar Damodaran's avatar
Aditya Shyam Shankar Damodaran committed
63
```
Aditya Damodaran's avatar
Aditya Damodaran committed
64
### Examples
65
66
67
68
69
 - Run tests against a database of size N = 100, random database values, and a Paillier key length of 2048 bits:
   ```bash
   $ python3 ./protocol.py -k 2048 -r 100
   ```

Aditya Damodaran's avatar
Aditya Damodaran committed
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
- Run tests against a database of size N = 16000, and a Paillier key length of 2048 bits:
  ```bash
  $ python3 ./protocol.py -k 2048 16000
  ```

- Run tests against a database of size N = 65000, random database values, and a Paillier key length of 2048 bits:
  ```bash
  $ python3 ./protocol.py -k 2048 -r 65000
  ```

### Results
The program prints measurements to console, and also appends these measurements to a file named `UUHD-PPLS-Timing-Data.xlsx`. 

```
+----+---------+---------------------+--------------+---------------------+
| N  | DB Size | Paillier Key Length | First Update | Computation of Vcom |
+====+=========+=====================+==============+=====================+
| 10 | 100     | 2048                | 0.384        | 0.001               |
+----+---------+---------------------+--------------+---------------------+
+----------------+--------------+--------------+--------------+----------+
| 1 Entry Update | 1 Entry Read | 5 Entry Read | Registration | Purchase |
+================+==============+==============+==============+==========+
| 0.000          | 4.271        | 14.013       | 0.385        | 7.642    |
+----------------+--------------+--------------+--------------+----------+
+------------+-------------------+------------------+------------------+-------+
| Redemption | 1 Entry Profiling |     5 Entry      |     10 Entry     | Setup |
|            |                   |    Profiling     |    Profiling     |       |
+============+===================+==================+==================+=======+
| 5.806      | 6.245             | 33.575           | 61.165           | 0.366 |
+------------+-------------------+------------------+------------------+-------+
```

## License
This project is licensed under the GPLv3 license.

## Acknowledgements
106

Aditya Damodaran's avatar
Typos    
Aditya Damodaran committed
107
This research was supported by the Luxembourg National Research Fund (FNR) CORE
Aditya Shyam Shankar Damodaran's avatar
Typo    
Aditya Shyam Shankar Damodaran committed
108
project “Stateful Zero-Knowledge” (Project code: C17/11650748).