CACR offers an active research environment with faculty conducting
research in many areas of cryptography and information security,
both theoretical and applied. There are several ongoing
multi-disciplinary projects with participation from faculty and
students in the departments of Combinatorics and Optimization (C&O),
Computer Science (CS), Electrical and Computer Engineering (E&CE),
Physics (PHY), and Pure Mathematics (PMath). There are also a
number of collaborative projects sponsored by industry.
The following are some research groups and labs at the University of
Waterloo that are led by CACR faculty members:
The following is a sampling of the research areas that are
represented at CACR. Further information can be obtained from the
personal web sites of faculty members, and by
browsing through our technical reports.
Security for Pervasive Computing
Pervasive computing environments allow users to seamlessly interact
with embedded computers, depending on the users' current
context. These new environments raise a variety of privacy and
security challenges. For example, context-sensitive services can
easily leak information about a user's context or uncertainty about a
user's context might lead to wrongfully disclosed information.
In our research, we examine pervasive computing environments for
security and privacy challenges. We address these challenges by
applying cryptographic algorithms in new ways and by implementing and
evaluating these algorithms in prototype applications.
The recent discovery of collision-finding algorithms for many popular hash
functions has led to an increased interest in the development and analysis
of hash functions. Recent work includes analysis of multicollision attacks
on hash functions and analysis of reductions among fundamental
problems involving hash functions.
Pseudorandom sequences have many important applications in
communications and cryptography. Randomness of a sequence refers
to the unpredictability of the sequence. Any deterministically
generated sequence used in practical applications is not truly
random. The course of this research has two directions.
Sequence design for wireless code division multiplexing (CDMA)
communication systems. In wireless CDMA systems, multiple users
share a common channel. The problem is to find good signal sets
having low correlation (decreasing interferences among users in
the detection process), large linear span (for providing certain
security features for the users who are assigned those sequences,
e.g. preventing cloning of cell phones), and a large number of
sequences (so that more users can be supported). These problems
have many connections with combinatorics and Boolean functions.
For example, sequences having 2-level autocorrelation corresponds
to cyclic Hadamard difference sets, and the polynomial functions
used to generate binary sequences correspond to Boolean functions.
Constructions of Boolean functions with high nonlinearity (against
linear cryptanalysis), high order correlation immunity or resilience
(against various correlation attacks and differential cryptanalysis),
and high algebraic immunity (against algebraic attacks) for both stream
cipher and block ciphers are also being pursued.
Sequence design for applications in stream ciphers and
pseudorandom number generators. Since tranmission errors are
more likely in wireless communications than in wireline
communications, stream ciphers are preferred over block ciphers.
CACR researchers are designing pseudorandom sequence generators with
good randomness properties which can be efficiently and securely
implemented in hardware. Also being studied are the pseudorandom number
generators that arise from the sequence generators.
Computational Number Theory
In the last twenty-five years, computational number theory and
cryptology have become closely intertwined. Number theory provides
most of the hard computational problems that can be used to guarantee
the security of public-key cryptographic schemes. The main aim of
computational number theory is the design, implementation, and analysis
of algorithms for solving problems in number theory. Apart from algorithms
for problems arising in cryptography such as the integer factorization
problem or the discrete logarithm problem in various structures,
this includes algorithms for computing fundamental invariants in algebraic
number fields and algebraic function fields.
CACR researchers have made many contributions to the discrete logarithm
problem in finite fields, elliptic curves and hyperelliptic curves. We
have also studied combinatorial approaches to generic algorithms for the
discrete logarithm problem, and considered "low hamming weight" variants
of the problem.
Distributed Cryptographic Protocols
Many cryptographic tools can be adapted to a distributed setting
where the authority to perform a certain cryptographic computation
is shared among various entities in a network. For example, we might
desire a certain threshold of entities in order to compute a signature,
decrypt a ciphertext, etc. The simplest example of this type of scheme is
a "secret sharing scheme", in which an authorized subset of entities
(say at least t out of n) is required in order to reconstruct
a certain secret, where each entity holds a "piece" of the secret called
The advantage of a distributed protocol (as compared to a one-to-one
protocol) is increased security against attacks (since there is no longer
a single point of failure) and fault-tolerance (the desired action can be
completed even if some of the entities are not functioning correctly).
Many types of cryptographic protocols have been investigated in a
distributed setting, including oblivious transfer and broadcast
Distribution of keys by a trusted authority to users in a network is
a fundamental tool in enabling secure communication. Security of
key distribution schemes can be based on computational assumptions;
however, it is also possible to design schemes that are "unconditionally
secure". Schemes of this type are proven secure using combinatorial or
information-theoretic techniques, independent of the computing power of
Of particular interest are key distribution schemes for sensor networks,
where it is imperative to minimize storage requirements and computational
costs. In this setting, it may not be appropriate to ensure that every
pair of nodes shares a common key, so efficient methods for establishing
secure multi-hop communication paths are necessary.
Cryptographic Computations - Algorithms,
Architectures and Fault Tolerance
Many cryptosystems are based on computations in very large finite fields.
Dedicated hardware realization of processors or accelerators for such
computations requires a large number of logic gates. A number of CACR
researchers are working towards development of efficient algorithms for
cryptographic computations. These algorithms are in turn mapped onto
high performance and/or resource constrained architectures to meet
requirements of various applications - from web servers to smart-cards.
Research is also being carried out to devise efficient schemes for
performing correct cryptographic computations in presence of hardware
faults caused by defects of silicon devices or malicious acts of
Side-Channel Attacks and Countermeasures
Side-channel attacks reveal information about cryptographic keys
by capture and analysis of electromagnetic emission or power dissipation
from embedded systems. A side-channel analysis laboratory has been
established which supports the verification of countermeasures and
attacks through real measurement of electromagnetic emissions and
power. Software-based and VLSI countermeasures to thwart side-channel
attacks in wireless embedded systems are being investigated.
Copyright protection is a fundamental goal of digital rights management.
Two methods of copyright protection are broadcast encryption and tracing.
Broadcast encryption ensures that an encrypted broadcast can be decrypted
only by designated authorized receivers. Tracing schemes use certain
codes to allow pirated data or decoders to be traced back to their
Security in Ad Hoc Networks
Internet, wireless networks, and ad hoc networks have vastly differing
characteristics such as the availability of a fixed infrastructure,
the network topology, the capabilities of network nodes, and the
availability of a centralized authority. These variations result in
different requirements and constraints for implementing security
features such as key distribution, authentication, encryption, and
In general, an ad hoc network does not have a fixed infrastructure,
the network topology changes frequently, and the nodes have limited
computational, bandwidth, and power resources. In practice, ad hoc
networks may be associated with Personal Area Networks (PANs), as for
instance wireless communications among PDAs, cellular phones, and
laptops using the Bluetooth protocol, or sensor networks.
CACR researchers are developing applications-based security protocols
for authentication among nodes in an ad hoc network and for authenticated
key distributions or session key establishment. Symmetric, hybrid
(for example, public-key cryptography with passwords), and asymmetric
(i.e., public-key approach using threshold cryptography and identity-based
schemes) solutions are being sought. Both single-hop and multi-hop scenarios
are being considered. The performance of our proposed solutions will
be evaluated through simulations.
Cryptography in a Quantum World
The true limitations and capabilities of an information processing
device are determined by the laws of physics, and therefore we must
ask how quantum technologies affect the theory and practice of
providing information security objectives.
In some cases quantum theory allows us to perform tasks previously
believed to be infeasible, such as finding discrete logarithms in
general groups or factoring large numbers. If large-scale quantum
computers will be built (and fault-tolerant quantum error correction
suggests that there is no fundamental obstacle) computationally
secure cryptography will require an understanding of which problems
are tractable and which are intractable on a quantum computer.
Quantum information also has special properties which allow tasks
previously believed to be impossible. Quantum mechanics implies an
intrinsic, quantifiable, trade-off between the amount of information
an eavesdropper extracts from a physical system and the amount of
disturbance caused to the system. Thus, eavesdropping can be detected
with high probability, and this opens the door for a wide range of new
cryptographic tasks whose security is guaranteed by quantum mechanics.