Estimation Code For Offline Simon's Algorithm

This code estimates the cost of running an offline Simon's attack [1] against the ciphers Chaskey [2], Prince [3], and Elephant [4].

The details of the attack are presented in the associated paper [5].

It consists of two main components

• Q# code to compute circuit costs for the ciphers themselves and linear algebra
• A Python script to assemble the results into the cost of the full attack

Dependencies

-Dotnet core 3.1, available here: https://dotnet.microsoft.com/download -Qsharp sdk 0.13.20102604 (later versions will need changes to the C# code portions). Installation instructions here: https://docs.microsoft.com/en-us/quantum/quickstarts/ Can be run with dotnet new -i Microsoft.Quantum.ProjectTemplates -Python 3 -SageMath 8.1

How to Build

cd /path/to/MicrosoftQuantumCrypto dotnet build -c MinimizeT

This builds the MicrosoftQuantumCrypto library.

cd /path/to//Simon dotnet build

This builds the Q# estimation circuits.

How to run

cd /path/to//Simon dotnet run

This runs the Q# estimation circuits for:

• 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 a matrix for a range of dimensions from 4 to 64 with approximately even width (saved to /RankCalculationEven/)
• Computing the rank of the matrices needed for the offline Simon attack (saved to /RankCalculation/)

If estimations already exist, this will append the new data to the existing estimations.

To find the full costs for the offline Simon attack and the quantum exhaustive key search, run:

cd /path/to/folder python3 attack_cost.py

This will print the results to the console. It starts with query-limited versions of the attacks, then tries a query-unlimited version.

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 The Simon resource estimator references these directly, so to use a different option, you will need to modify 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 (microsoft/qsharp-runtime#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".

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 a new code to PiRhoThetaRaw. 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 easily changed; COST_METRIC can be changed to ALL_GATES or T_GATES; and COST_MODEL can be switched from G_COST to DW_COST

Contributors

• Xavier Bonnetain
• Samuel Jaques

MicrosoftQuantumCrypto library, resource estimation, and PLU decompositions:

• Christain Paquin
• Michael Naehrig
• Fernando Virdia

References

[1] Xavier Bonnetain, Akinori Hosoyamada, María Naya-Plasencia, Yu Sasaki, André Schrottenloher: Quantum attacks without superposition queries: The offline Simon’s algorithm.

[2] Nicky Mouha, Bart Mennink, Anthony Van Herrewege, Dai Watanabe, Bart Preneel, Ingrid Verbauwhede: Chaskey: An efficient MAC algorithm for 32-bit microcontrollers.

[3] Julia Borghoff, Anne Canteaut, Tim Güneysu, Elif Bilge Kavun, Miroslav Knežević, Lars R. Knudsen, Gregor Leander, Ventzislav Nikov, Christof Paar, Christian Rechberger, Peter Rombouts, Søren S. Thomsen, Tolga Yalçın: PRINCE - A low-latency block cipher for pervasive computing applications.

[4] Tim Beyne, Yu Long Chen, Christoph Dobraunig, Bart Mennink: Elephant v1.1

[5] Xavier Bonnetain, Samuel Jaques: Quantum period finding against symmetric primitives in practice.