Finite fields (Algebra)

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.

Recent interest in cryptographic systems has generated many mathematical results involving computations in finite fields. In particular, it is known that the use of optimal normal bases significantly reduces the complexity of computations in certain finite fields. This thesis examines three specific aspects of optimal normal bases. First, the effect of optimal normal bases on computations in finite fields is analyzed. Second, the known constructions of optimal normal bases are presented. Finally, the generators of optimal normal bases are discussed in terms of their order in the field.

A zero knowledge identification protocol is an interactive proof system that allows a person to prove that he knows a secret key associated with his identity without revealing the secret key. This type of protocol is the topic of a fairy tale, by Gustavus Simmons called the King's Dilemma, about a king and the problem he has with thieves impersonating his tax collectors. It describes a zero-knowledge identification protocol that will rid the king of his problem. I present this system, the motivation for this thesis, and the transformations from this protocol, that uses lead weights and containers, to protocols that use mathematical elements. The security of these protocols is determined by the complexity of the underlying mathematical problem, such as the knapsack and discrete logarithm problem, and three properties: completeness, soundness, and zero knowledge.

In a projective plane (PG(2, K) defined over an algebraically closed field K of characteristic p = 0, we give a complete classification of 3-nets realizing a finite group. The known infinite family, due to Yuzvinsky, arised from plane cubics and comprises 3-nets realizing cyclic and direct products of two cyclic groups. Another known infinite family, due to Pereira and Yuzvinsky, comprises 3-nets realizing dihedral groups. We prove that there is no further infinite family and list all possible sporadic examples. If p is larger than the order of the group, the same classification holds true apart from three possible exceptions: Alt4, Sym4 and Alt5.