Lars Schlieper

Lars Schlieper

We present an in-place implementation of the cryptographic permutation \textbf{Gimli}, a NIST round 2 candidate for lightweight cryptography, and provide an upper bound for the required quantum resource in depth and gate-counts. In particular, we do not use any ancilla qubits and the state that our circuit produces is not entangled with any input. This offers further freedom in the usability and allows for a widespread use in different applications in a plug-and-play manner.

Alexander May, Lars Schlieper, Jonathan Schwinger

Let $f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ be a Boolean function with period $\vec s$. It is well-known that Simon's algorithm finds $\vec s$ in time polynomial in $n$ on quantum devices that are capable of performing error-correction. However, today's quantum devices are inherently noisy, too limited for error correction, and Simon's algorithm is not error-tolerant. We show that even noisy quantum period finding computations may lead to speedups in comparison to purely classical computations. To this end, we implemented Simon's quantum period finding circuit on the $15$-qubit quantum device IBM Q 16 Melbourne. Our experiments show that with a certain probability $τ(n)$ we measure erroneous vectors that are not orthogonal to $\vec s$. We propose new, simple, but very effective smoothing techniques to classically mitigate physical noise effects such as e.g. IBM Q's bias towards the $0$-qubit. After smoothing, our noisy quantum device provides us a statistical distribution that we can easily transform into an LPN instance with parameters $n$ and $τ(n)$. Hence, in the noisy case we may not hope to find periods in time polynomial in $n$. However, we may still obtain a quantum advantage if the error $τ(n)$ does not grow too large. This demonstrates that quantum devices may be useful for period finding, even before achieving the level of full error correction capability.

Alexander May, Lars Schlieper

We study quantum period finding algorithms such as Simon and Shor (and its variants Ekerå-Håstad and Mosca-Ekert). For a periodic function $f$ these algorithms produce -- via some quantum embedding of $f$ -- a quantum superposition $\sum_x |x\rangle|f(x)\rangle$, which requires a certain amount of output qubits that represent $|f(x)\rangle$. We show that one can lower this amount to a single output qubit by hashing $f$ down to a single bit in an oracle setting. Namely, we replace the embedding of $f$ in quantum period finding circuits by oracle access to several embeddings of hashed versions of $f$. We show that on expectation this modification only doubles the required amount of quantum measurements, while significantly reducing the total number of qubits. For example, for Simon's algorithm that finds periods in $f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ our hashing technique reduces the required output qubits from $n$ down to $1$, and therefore the total amount of qubits from $2n$ to $n+1$. We also show that Simon's algorithm admits real world applications with only $n+1$ qubits by giving a concrete realization of a hashed version of the cryptographic Even-Mansour construction. Moreover, for a variant of Simon's algorithm on Even-Mansour that requires only classical queries to Even-Mansour we save a factor of (roughly) $4$ in the qubits. Our oracle-based hashed version of the Ekerå-Håstad algorithm for factoring $n$-bit RSA reduces the required qubits from $(\frac 3 2 + o(1))n$ down to $(\frac 1 2 + o(1))n$. We also show a real-world (non-oracle) application in the discrete logarithm setting by giving a concrete realization of a hashed version of Mosca-Ekert for the Decisional Diffie Hellman problem in $\mathbb{F}_{p^m}$, thereby reducing the number of qubits by even a linear factor from $m \log p$ downto $\log p$.