Storage Cost Simulation of Grappa

This repository contains the code to simulate the storage and communication cost of Grappa when implemented with different interval schemes. This is an artifact that accompanies our paper called "Group Key Progression: Strong Security for Shared Persistent Data".

Installation

The python packages listed in requirements.txt need to be installed.

For example, you can create a virtual environment and install them there as follows:

$ python3 -m venv venv
$ . venv/bin/activate
$ pip3 install -r ./requirements.txt

Running the simulator

Run with the following instructions:

$ python3 sim.py --sets 10 --reps 10000 --nr-users 500 --nr-admins 5 --add-user 0.01 --rem-user 0.01 --upd-user 0.489895 --add-admin 0.0001 --rem-admin 0.0001 --upd-admin 0.489895 --rot-keys 0.00001 --max-chain-len 10000 --interval-type all --verbose progress

Help page:

$ python3 sim.py --help
usage: simulate [-h] [--sets SETS] [--reps REPS] [--nr-users NR_USERS] [--nr-admins NR_ADMINS] [--add-user ADD_USER] [--rem-user REM_USER] [--upd-user UPD_USER] [--add-admin ADD_ADMIN] [--rem-admin REM_ADMIN] [--upd-admin UPD_ADMIN] [--rot-keys ROT_KEYS] [--max-chain-len MAX_CHAIN_LEN]
          [--interval-type {trivial,dhash,dsskg,ggm1,all}] [--verbose {progress,info,debug,warning,error}]

Simulate GKP costs

options:
  -h, --help            show this help message and exit
  --sets SETS
  --reps REPS
  --nr-users NR_USERS
  --nr-admins NR_ADMINS
  --add-user ADD_USER
  --rem-user REM_USER
  --upd-user UPD_USER
  --add-admin ADD_ADMIN
  --rem-admin REM_ADMIN
  --upd-admin UPD_ADMIN
  --rot-keys ROT_KEYS
  --max-chain-len MAX_CHAIN_LEN
  --interval-type {trivial,dhash,dsskg,ggm1,all}
  --verbose {progress,info,debug,warning,error}

The values for flags --add-user, --rem-user, --upd-user, --add-admin, --rem-admin, --upd-admin, and --rot-keys are percentages (between 0 and 1) and need to add up to 100%.

The results in our paper were produced with the following call. Note that this simulation took multiple hours on a machine with 44 physical cores.

$ python3 sim.py --sets 100 --reps 100000 --nr-users 500 --nr-admins 5 --add-user 0.01 --rem-user 0.01 --upd-user 0.489895 --add-admin 0.0001 --rem-admin 0.0001 --upd-admin 0.489895 --rot-keys 0.00001 --max-chain-len 10000 --interval-type all --verbose progress

Remark on computation time

The simulation for the results in the paper took multiple hours on a machine with 44 physical cores.

You can make tradeoffs to reduce the computation time as follows:

• Reduce the number of sets: This leads to less stable numbers as costs depend on the sequence of randomized operations, and fewer sets means averaging the results across fewer randomized operation sequences.
• Reduce the number of reps: This reduces how many epochs are simulated. The fewer epochs you simulate, the less the numbers will reflect the true trends for every interval scheme. Note that reducing the reps always reduces the overall costs (i.e., if you change the number of reps, the cost numbers must be evaluated relative to each other, rather than as absolute numbers).

Additionally, the following parameters influence the cost, but changing them changes the evaluated scenario:

• Changing the probability of expensive operations: --rot-keys (rotate keys), --rem-admin (remove admin), and --rem-user (remove user) all rotate key material and hence directly increase storage. Grappa is designed around the assumption that these operations are more rare than others (in particular, --upd-user and --upd-admin are intended to be very frequent and cheap key refreshing operations that give PCS). Changing these operation probabilities of course heavily influences the resulting costs. Above, we picked probabilites that seem reasonable for our envisioned applications. While these values should not be changed when reproducing our simulation results, we encourage anyone adopting Grappa to re-run the simulator for their specific application and operation probabilites.
• Changing the maximum chain length --max-chain-len influences how many key rotations are required after exhausting a chain. The "correct" value for this parameter is such that chains are rarely exhausted but are instead rotated explicitly before due to an operation that requires chain rotation for security. Too short chains lead to unnecessarily many chain rotations, which increases the cost. Too long chains lead to unnecessary costs for most interval schemes (not for "trivial", which always has the worst case cost) as they need to precompute values based on the maximum chain length at the creation of a new chain. A good value can be found empirically through simulations. The simulator prints the average chain/interval length of simulations. For even more detailed information, increase the verbosity to print different operations.

Remark on verbosity

Change --verbose to modify the output of the simulator. Note that setting this to info or debug is not recommended for large simulations, as it will produce an extremely large amount of output and significantly slow down the simulator. Instead, reduce the number of sets and repetitions a lot (e.g., --sets 1 --reps 1000) for a deeper understanding of Grappa, or debugging.

Code organization

The code is structured as follows:

• sim.py: Implements the CLI, prepares arguments, and post-processes the output in a Pandas dataframe.
• interval_schemes/: This folder contains all simulated interval scheme implementations. The Grappa simulator can use any of them for the underlying interval scheme during cost simulations.
  • trivial_scheme.py: Implements the "trivial" interval scheme (see paper), which stores independent keys for every epoch.
  • dkr_hash_scheme.py: Implements hash-based dual-key regression (DKR), called D[H, F] in the paper. It derives keys using two hash-chains, running in opposite directions, which may be rotated.
  • dkr_sskg_scheme.py: Implements SSKG-based dual-key regression (DKR), called D[S, F] in the paper. It derives keys using the SSKG tree structure that allows fast-forwarding key derivation at the cost of increasing storage. The SSKG trees may also be rotated.
  • ggm1_scheme.py: Implements GGM trees, where interval extensions share GGM trees for the extended interval without attempting to merge them with existing GGM trees. We call this construction GGM1 in the paper. GGM trees may be rotated.
  • The following two files provide shared resources to all above DKR implementations:
    • generic_scheme: This implements the interval scheme syntax (as a class), which all implementations follow (by instantiating said class).
    • utils.py: a few generic helper functions to pretty-print output.
• grappa_sim.py: Implements our GKP instantiation Grappa, which is based on interval schemes. It follows the GKP syntax and calls the interval scheme operations based on which group operations are performed. Note that we do not simulate the CGKA-related costs, which are shared among all interval schemes. Instead, we track the communication and storage costs of the underlying interval scheme.