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)?
$\begingroup$
$\endgroup$
New contributor
Kathiresan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
