3
$\begingroup$

Though there are many papers available on application of Simon's algorithm for symmetric encryption, nothing is clear on implementation - like how to build the oracle, how many PT-CT combinations are required, what exactly is the hidden string 's' (key or just difference between two messages). Can anyone please explain in simple terms or give a reference (for circuit, github code)?

$\endgroup$

1 Answer 1

5
$\begingroup$

Mathematically speaking, Simon's algorithm is a very efficient algorithm for the solution of the hidden subgroup problem for a subgroup of order 2 of the group $C_2^n$. It can only be implemented if the function $f$ under consideration can be accessed via a quantum oracle that can evaluate $f$ on superpositions of inputs. I personally find the AWS blog with Daniel Simon a very well written description of the idea.

The oracle

From a cryptanalytic point of view, Simon's algorithm approaches should not be thought of as practically realisable attacks in any way, but rather heavily overengineered Gedankenexperimenten with a very unrealistic adversary. It is not usually specified how an adversary might access an oracle of the sort required for Simon's algorithm. Possibly one could conceive of implementing the classical algorithm on a quantum computer at some point in the future; possibly an adversary might be able to clone everything about your implementation nut not be able to directly recover the key. These and other means of accessing the oracle all seem implausible.

Data requirement

Each run of Simon's algorithm has identical input of a single uniform superposition of $n$-qubits which can be measured as each of the $2^n$ possible inputs equiprobably. A superposition of possible outputs is produced from this which we measure to get precisely 1 output value per run. The input register is then transformed to a $n$-qubit value which is measured to get an $n$-bit value $z$ that provides 1-bit of information about $s$ according to the equation $z\cdot s=0$ where $\cdot$ represents the $\mathbb F_2$ scalar product on $(\mathbb F_2)^n$. To uniquely identify $s$ there would need to be $n$ linearly independent values of $z$ so that at last $n$ runs of the algorithm would be required. The probability of getting a full rank set of equations tends quickly to 1 with just $O(1)$ more runs.

The meaning of $s$

The value $s$ defines the generator of the hidden subgroup, but can be adapted to take a range of meanings in a cryptanalytic context. Its interpretation will depend on how the function $f(x)$ relates to a particular cryptographic primitive, but can encompass linear, differential, and linear-differential parameters.

Circuit reference

As a quantum algorithm, there is not really any GitHub implementation that I know of, but there is a good section of the qiskit manual that deals with realising Simon's algorithm as a quantum circuit.

ETA 20220707

Particular examples

The paper Using Simon's algorithm to attack symmetric-key primitives is an example of an unrealistic attack scenario where an attacker is provided access to quantum implementation of a permutation of $n$-bit values and asked to determine if the permutation is a 3-round Feistel network. Using at most $2n$ calls to the permutation with a balanced superposition of all inputs, the paper shot how this can be achieved using the circuit diagram on page 8. This is not relevant to the security of a classical implementation of a Feistel cipher unless someone engineers a method to clone the classical implementation to quantum hardware, but is not able to recover any details of the implementation while doing so. Such a process would be very strange indeed.

$\endgroup$
11
  • $\begingroup$ Thanks Daniel for a very detailed reply which makes better understanding of Simon's algorithm. It is still not clear whether Simon's algorithm for cryptanalysis is unrealistic even when adversary has access to all sorts of quantum attack (superposition of inputs, quantum implementation of cryptographic primitives). But, some researchers claim that they are able to decrypt Even-Mansour construct and 3 round Feistel networks. But they have not provided any example (with circuit). Please share your views on "realistic" and if it is realistic, where to look for implementation. $\endgroup$
    – Kathiresan
    Jun 27, 2022 at 10:57
  • $\begingroup$ Can you give me a reference for these claims? $\endgroup$
    – Daniel S
    Jun 27, 2022 at 16:40
  • $\begingroup$ Here are some references. arxiv.org/pdf/1603.07856.pdf and ieeexplore.ieee.org/document/6400943 $\endgroup$
    – Kathiresan
    Jun 29, 2022 at 5:43
  • $\begingroup$ I've added comments on the 3-round Feistel paper, but cannot pass the Evan-Mansour paywall. $\endgroup$
    – Daniel S
    Jul 7, 2022 at 8:22
  • $\begingroup$ @DanielS Here's a reference which contains both an attack on 3-round Feistel and key recovery on Even-Mansour: arxiv.org/abs/1602.05973. $\endgroup$ Jul 8, 2022 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.