This artifact is a docker container running Ubuntu 20.04, which contains all of the code we used for the resource estimates in our paper. It was developed with Docker version 20.10.9.

Set-up

Navigate to offline-simon-docker. To build the docker image:

docker build . -t offline-simon-build

Then to create a new volume for the code, create a temporary container:

docker run -v offline-simon-vol:/app --name offline-simon-loader ubuntu:20.04 /bin/bash

then load the compressed data into the volume:

docker run --rm --volumes-from offline-simon-loader -v $(pwd)/backup:/backup ubuntu:20.04 bash -c "cd /app && tar xvf /backup/backup.tar --strip 1"

and clean up the temporary container:

docker container rm offline-simon-loader.

To start the container with all the code in the command line:

docker run --rm -it --name offline-simon-container -v offline-simon-vol:/app offline-simon-build

Within the container, navigate to /app, and call ./finish_installation.

Overview

There are two main components of the resource estimation:
- Q# code to compute circuit costs for the ciphers themselves and linear algebra, outputting them as .csv files (mainly in app/offline-quantum-period-finding/Simon)
- A Python script to assemble the results into the cost of the full attack and output them to the console (/app/offline-quantum-period-finding/attack_cost.py)

There is also the MicrosoftQuantumCrypto library, which contains some helper functions for the Q# estimation.

The docker container has pre-computed circuit cost outputs, so the python script will work immediately. Running ./recalculate_qsharp_estimates will delete the existing estimates and re-run the Q# code to produce new estimates for the individual block ciphers and linear algebra steps.

Source Code Organization and Outputs

/app/offline-quantum-period-finding/Simon

The C# code in Driver.cs starts a thread for each size of estimate and each cipher, and for the different sizes of rank calculation. Mainly this calls wrapper code in SimonResourceWrappers.qs. The code for the actual ciphers is in, e.g., Chaskey.qs, Prince.qs, and Elephant.qs, and the linear algebra code is in Matrix.qs.

The output is organized as follows:
- The Simon function for the three block ciphers, with no optimizations (saved to /FullCipherCosts/)
- The same block ciphers, with optimizations for different guess sizes (saved to /CipherCosts/)
- Grover iterations for key search (saved to /GroverCosts/)
- Computing the rank of the matrices needed for the offline Simon attack (saved to /RankCalculation/)

For each type of estimate, there is a T-depth calculation (where T-gates have depth 1 and all other gates have depth 0) and a full depth calculation (where all gates have depth 1), distinguished by the suffix "-all-gates". Common to both files are CNOT count, 1-qubit Clifford count (the count of H, X, S, Y gates), T count, M count (the count of measurements), Full width, max width, initial width, and extra width (all of which count the number of qubits, and the difference only appears for functions which are subroutines of other Q# functions. For our code, these will all display either the total number of qubits or 0). T depth and Full depth are the circuit depth under the two different metrics.

The last one or two columns are different:
- For FullCipherCosts, the last column size is a parameter of the scheme: For Chaskey, it's the number of rounds, for Elephant, it's the block size, and for PRINCE it's the block size.
- For CipherCosts, first arg is the same as size, while second arg is size of the input used for period finding (instead of amplitude amplification; see Figure 8 of the paper).
- For RankCalculation, first arg is the height and second arg is the width of the linear system being solved. second arg is always greater.
- For GroverCosts, first arg is same parameter of the cipher as before, while second arg is the number of repetitions of that cipher (which is not used in a Search-with-Two-Oracles approach)

/app/offline-quantum-period-finding/attack_cost.py

This python script will first output the costs of query-limited attacks, then it will print the costs of attacks with unlimited queries, and then the costs of an exhaustive key search with Grover's algorithm.

The outputs are formatted for a .tex table, in order as: Cipher name, size, number of queries, total gate count, T count, total depth, T depth, number of qubits. This is the same order as Table 2 in the paper.

/app/offline-quantum-period-finding/MicrosoftQuantumCrypto

This is a library of various cryptographic functions. Our project relies mainly on functions in Basics.qs, Arithmetic.qs, and ModularArithmetic.qs.

Customizations

Some of the main points you may want to customize:

Optimization strategies

The MicrosoftQuantumCrypto library can be built with any of three different optimization strategies:
dotnet build -c MinimizeT
dotnet build -c MinimizeDepth
dotnet build -c MinimizeWidth
These mainly affect which adders and which multi-input AND circuits are used.

The Simon resource estimator references these directly, so to use a different option, you will need to modify /app/offline-quantum-period-finding/Simon/ResourceEstimator.csproj. Specifically, lines including
..\MicrosoftQuantumCrypto\bin\MinimizeT\netcoreapp3.1\MicrosoftQuantumCrypto.dll
should have MinimizeT changed to one of the other options.

As well, Driver.cs makes a decision of which compiler strategy to use when allocating qubits: a depth-optimal or width-optimal. As of November 2020 there is a bug in the depth-optimal estimator (https://github.com/microsoft/qsharp-runtime/issues/419), so we opted to use a width-optimal strategy when optimizing for T count. This is is part of the GetTraceSimulator function.

The python script attack_cost.py will also need to have Q_SHARP_SUBFOLDER changed to "LowDepth" or "LowWidth" if you change to one of these other options.

Keccak

Because Pi, Rho, and Theta use a PLU decomposition, this must be created for every block size used. We only generated code for a block size of 200 bits. To change this, modify the matrixPLU.sage file. It has a hard-coded w which represents the length of a state. Modify this (e.g., w=64 for 1600-bit blocks), and run sage matrixPLU.sage and it will save new Q# code to PiRhoThetaRaw. This will require SageMath, and was originally run with version 8.1. As needed, replace the code in PiRhoTheta.qs.

Cost metrics

The script attack_cost.py chooses an optimal number of queries based on the minimum gate cost. This can be changed to optimize the depth*width cost: the global variableCOST_MODEL can be switched from G_COST to DW_COST. COST_METRIC can also be changed from ALL_GATES to T_GATES; however, during the main loops of calculation, it switches between cost metrics to compute both the T-cost and the cost of all gates. Thus, the lines from 403-418 and 447-455 would need to change in several places to switch to optimize for T-cost.

Rank Calculations

The attack_cost.py script will check the linear algebra calculations in /app/offline-quantum-period-finding/Simon/RankCalculation/ for the exact size of linear system it is trying to compute (where the sizes are in the first arg and second arg columns). If it finds the right size, it uses those numbers; if not, it estimates based on an asymptotic formula. If you want to run estimates that include different sizes of linear system, we recommend adding those sizes to the realWidths and realHeights arrays in the Driver.cs file, rather than relying on the asymptotic formulas.

The asymptotic formulas were estimated using calculations for matrices of random heights and widths. The EstimateRankCosts function in Driver.cs computed these. Currently that function is commented out, because it takes a long time to compute, but this is the function to use to verify our asymptotic formulas.

Alternate Cipher Sizes

Within the function EstimateCipherCosts of Driver.cs, the {cipherName}GuessSizes arrays contain the size of the input message that is part of the period-finding subtroutine, rather than the amplitude amplification. There are two such sizes for each parameter of the cipher (e.g., 2 sizes for each length of Elephant). Since this gives the number of chosen plaintext queries the adversary must make, the first represents a query limit fixed by the cipher's designers, and the second represents the optimal number of queries that we found with the python script.

The python script will try to find a cipher cost specifically computed for the number of queries that it tests, and if not, it will just take the last cipher cost estimate in the csv file it checks. Hence, if you modify the script so that it chooses a different optimal number of queries, you should probably add the new number to the array of {cipherName}GuessSizes and compute a new estimate for it. The difference in cost comes from how the cipher-specific optimizations can be used (e.g., not computing all of the output bits).