Quantum Circuits for Cryptanalysis

Finite elds of the form F2m play an important role in coding theory and
cryptography. We show that the choice of how to represent the elements of these elds
can have a signi cant impact on the resource requirements for quantum arithmetic.
In particular, we show how the Gaussian normal basis representations and \ghost-bit
basis" representations can be used to implement inverters with a quantum circuit
of depth O(mlog(m)). To the best of our knowledge, this is the rst construction
with subquadratic depth reported in the literature. Our quantum circuit for the
computation of multiplicative inverses is based on the Itoh-Tsujii algorithm which
exploits the property that, in a normal basis representation, squaring corresponds
to a permutation of the coe cients. We give resource estimates for the resulting
quantum circuit for inversion over binary elds F2m based on an elementary gate set
that is useful for fault-tolerant implementation.
Elliptic curves over nite elds F2m play a prominent role in modern cryptography.
Published quantum algorithms dealing with such curves build on a short
Weierstrass form in combination with a ne or projective coordinates. In this thesis
we show that changing the curve representation allows a substantial reduction in the number of T-gates needed to implement the curve arithmetic. As a tool, we present
a quantum circuit for computing multiplicative inverses in F2m in depth O(mlogm)
using a polynomial basis representation, which may be of independent interest.
Finally, we change our focus from the design of circuits which aim at attacking
computational assumptions on asymmetric cryptographic algorithms to the design of
a circuit attacking a symmetric cryptographic algorithm. We consider a block cipher,
SERPENT, and our design of a quantum circuit implementing this cipher to be used
for a key attack using Grover's algorithm as in [18]. This quantum circuit is essential
for understanding the complexity of Grover's algorithm.