Cryptographic hardware has found many uses in ubiquitous and pervasive security de-
vices with a small form factor, e.g. SIM cards, smart cards, electronic security tokens,
and soon even RFIDs. With applications in banking, telecommunication, healthcare, e-
commerce and entertainment, these devices use cryptography to provide security services
like authentication, identi¯cation and con¯dentiality to the user.
However, the widespread adoption of these devices into the mass market, and the lack
of a physical security perimeter have increased the risk of theft, reverse engineering, and
cloning. Despite the use of strong cryptographic algorithms, these devices often succumb to
powerful side-channel attacks. These attacks provide a motivated third party with access to
the inner workings of the device and therefore the opportunity to circumvent the protection
of the cryptographic envelope. Apart from passive side-channel analysis, which has been the
subject of intense research for over a decade, active tampering attacks like fault analysis have
recently gained increased attention from the academic and industrial research community.
In this dissertation we address the question of how to protect cryptographic devices
against these kinds of attacks. More speci¯cally, we focus our attention on public key
algorithms like elliptic curve cryptography and their underlying arithmetic structure. In our
research we address challenges such as the cost of implementation, the level of protection,
and the error model in an adversarial situation. The approaches that we investigate all
apply concepts from coding theory, in particular the theory of cyclic codes. This seems
intuitive, since both public key cryptography and cyclic codes share ¯nite ¯eld arithmetic
as a common foundation.
The major contributions of our research are (a) a generalization of cyclic codes that
allow embedding of ¯nite ¯elds into redundant rings under a ring homomorphism, (b) a new
family of non-linear arithmetic residue codes with very high error detection probability, (c)
a set of new low-cost arithmetic primitives for optimal extension ¯eld arithmetic based on
robust codes, and (d) design techniques for tamper-resilient ¯nite state machines.