Verified Set Operation (VSOlib) Library

VSOlib implements efficient cryptographic protocols for verifiable delegation of computation over outsourced sets. The main protocols implemented by the library has been described in the paper "Implementation of verified set operation protocols based on bilinear accumulators", presented at the 15th International Conference on Cryptology and Network Security (CANS 2016). The library represents an ongoing work and might be modified and improved in the future. If you want to cite this work please cite the published paper.

License and Warranty

We release the library to the public under the GPL license WITHOUT ANY WARRANTY. The library is a prototype and must NOT be used in production environments.

Downloading and installing VSOlib

The latest version of the library can be downloaded here and can be installed by using the distutils-compliant setup.py module:

% tar xvf vsolib-0.3.2.tar.gz
% cd vsolib-0.3.2
% ./setup build
% ./setup install

The setup module also supports a few unittest scripts for quick testing:

% ./setup build_ext --inplace
% ./setup test

The current version of the library has been tested on Debian- and Fedora-based Linux distributions. We tested it on Debian Jessie and Stretch, Ubuntu 16.04 and Fedora 24.

Dependencies

VerSOp is mainly implemented in Python 3, plus a few C/C++ extensions. Using the libraries requires to install the NTL library for big integers arithmetic and algorithms, and the Charm-Crypto and PBC libraries for pairing cryptography. Both NTL and Charm-Crypto depend on the GMP library, that can be easily installed from the official repository of the adopted Linux distribution. Charm-Crypto also requires SSL development libraries, that are also usually available on the official repositories.

NTL is available from official repositories of many Linux distributions, but we suggest installing the latest version from the official website. Please refer to the official documentation for details on all NTL configuration and installing options. We tested the library against NTL 10.1.0 compiled with the following configure options: NTL_GMP_LIP=on NTL_EXCEPTIONS=on NTL_THREADS=on SHARED=on

Charm-Crypto depends on the PBC libraries. As these libraries only depends on GMP, downloading and compiling them from the official website should be quite easy.

We provide some scripts to automatically install such dependencies in your home directory here.

VSOlib also includes sample programs that let users issue operations to an in-memory set collection through command-line interfaces. These programs require additional third-party Python libraries that are are also available on pipy:

pyparsing for parsing set operation queries;
python-prompt-toolkit for the command line interface;
msgpack-python for data serialization.

Running the authenticated set collections example application

We provide a few network applications that allow users to test the implemented protocols by using a prompt. We assume that the library has been installed correctly and the scripts have been made available in a directory included in the PATH environment variable (if you installed the library through distutils they should be already available). After the first setup phase we will use three independent terminals to emulate the three parties (server, owner, user).

System setup

Create a directory for the tests. As an example, we use a vso-tmp directory in the user's home. After opening a terminal in the home directory, create the vso-tmp directory:
```
% mkdir vso-tmp
% cd vso-tmp
% mkdir .vso-sc
```

The local hidden directory .vso-sc is the default path that our commands use to read and write configuration files and cryptographic material.

Create the configuration file by using the vso-sc-config write-conf command:
```
% vso-sc-config write-conf -o .vso-sc/config
```

The configuration file can be modified to execute protocol variants, such as different serialization protocols, elements compression and cache sizes as well as network parameters.

Generate a random key and extract its public key: here we use the MNT224 asymmetric pairing setting of the charm library and generate a key that is able to handle sets with 1000 elements (q=1000):
```
% vso-sc-config compute-sk MNT224 -o .vso-sc/sk
% vso-sc-config compute-pk -q 1000 -g G1 -i .vso-sc/sk -o .vso-sc/pk
```
Owner setup. The owner creates the initial accumulation tree and digest. Use the vso-sc-owner setup command to initialize the accumulation tree and the digest. The -a and -d options define the destination paths for the accumulation tree and for the digest:
```
% vso-sc-owner setup -a .vso-sc/auth -d .vso-sc/digest
```

Note that:

the default size of the set collection (the number of sets, not their cardinality) is 100
the default labels used to refer the sets are '0', ..., '(size - 1)'

In the following we show how to execute the three command-line programs in different terminals. Note that the order of the execution of the three programs must be server, owner, users:

the server starts services for receiving update and query operations;
the owner creates a persistent connection to the update service of the server and starts a service to distribute the digest;
the user sends query and digest requests to the server and the owner.

Running the Server

Use the vso-sc-server start command to create services for update and query operations (the default settings use the 9091 and 9092 TCP ports for updates and queries, respectively). The server will remain in foreground and will show verbose outputs when receiving inputs if options --show-log-info or --show-log-debug are used:

    % vso-sc-server start --show-log-info

Executing the Owner CLI

Use the vso-sc-owner start command to execute the command line interface of the owner application. The application also binds the service to distribute the digest to users (the default settings use the 9090 TCP port).

    % vso-sc-owner start

To exit from the command-line interface use CTRL+d or use the quit command. The program waits for values to be inserted or deleted from the database by using the insert and delete commands. The requested updates will be forwared as a single update operation to the server on the commit comand. You can use show to see the pending update operations and cancel to undo them. Syntax of insert and delete is as following:

    >> insert|delete <label1>,...,<labelN> <value1> ... <valueN>

The command creates a local queue of values to be added or removed to the sets referenced by the given labels. As an example:

    >> insert 1,5,10 hello world
    Operation accepted
    >> show 
    Insertions:
    {'1': {'world', 'hello'}, '10': {'world', 'hello'},
     '5': {'world', 'hello'}}
    Deletions:
    {}
    >> insert 5,10 bye
    Operation accepted
    >> show
    Insertions:
    {'1': {'world', 'hello'}, '10': {'bye', 'world', 'hello'},
     '5': {'bye', 'world', 'hello'}}
    Deletions:
    {}
    >> commit
    Adding values:
    {'1': {'world', 'hello'},
    '10': {'bye', 'world', 'hello'},
    '5': {'bye', 'world', 'hello'}}
    Update accepted by the server
    >> delete 5 bye
    Operation accepted
    Deleting values:
    {'5': {'bye'}}
    Update accepted by the server

Note that the current version of the server and owner programs keep all modifications only in memory. Thus, closing any of the two will cause inconsistencies between the cryptographic information that represent the state of the database.

Executing the User CLI

Use the vso-sc-user command to execute the command line interface of the user.

    % vso-sc-user

To exit from the command-line interface use CTRL+d or use the quit command. Use the query and update commands to issue queries to the server or to request the new version of the digest to the owner. On startup, the user application automatically sends a digest request to the owner. To update the digest execute the update command. The program shows if the digest has been modified (note that the digest changes for each update executed by the owner):

    (user) >> update
    Updating digest
    Digest unchanged

    (owner) >> insert 50 hello
    (owner) >> commit

    (user) >> update
    Updating digest
    Digest changed

The user program supports hierarchical set union and intersection operations. The server automatically selects the correct set operation proof protocols as described in Sections 4 and 6 of the paper. It returns to the user both the result of the query and the cryptographic proof.

    (user) >> query 10 and 1
    Verified result is
    ['world', 'hello']
    (user) >> query 5 or (10 and 1)
    Verified result is
    ['world', 'bye', 'hello']

If the proof is invalid, the program notifies it to the user (as an example, if the owner executed an update and the user did not request the new digest):

    (owner) >> insert 1 bye
    (owner) >> commit
    
    (user) >> query 10 and 1
    Invalid proof
    (user) >> update
    Updating digest
    Digest changed
    (user) >> query 10 and 1
    Verified result is
    ['world', 'bye', 'hello']