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.
Privacy-preserving communications
networks
Privacy-preserving communications networks allow people to communicate
with each other, and to access online information, without automatically
revealing personal information such as their Internet addresses. The
largest such network (Tor) sees
about 500,000 users daily. However, Tor is pushing the limits of its
scalability, and it is unlikely that Tor's current design could handle
millions or tens of millions of users.
Our group works on many aspects of these networks, with the goal of
improving their security, privacy, efficiency, and scalability. We have
a considerable amount of experience in this topic, and a number of our
improvements have been incorporated into the standard Tor software.
Security for Pervasive Computing
Environments
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.
Hash Functions
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
computational
problems involving hash functions.
Off-the-Record Messaging
Off-the-Record Messaging, or
OTR, enables people to use existing instant messaging systems while
maintaining the security and privacy of the contents of their messages.
Our flagship implementation, an OTR plugin for the Pidgin instant
messenger, is used by hundreds of thousands of people around the
world. There are independent libraries and plugins written by third
parties in a variety of programming languages, including Java,
Javascript, Scheme, Python, and Go, implementing our OTR protocol.
We continue to work on a number of aspects of OTR, including user
interface improvements, robustness to user errors, and a version of OTR
suitable for group communication.
Pseudorandom Sequences
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.
Censorship Resistance
Free and open communications on the Internet are a boon to the exchange
of ideas, information, culture, and democracy around the world.
Unfortunately, a number of national governments aim to restrict the
ability of their citizens to freely communicate. Censorship resistance
technologies use information hiding techniques to allow communication
between a citizen inside a censored regime and the outside. There have
been a number of recent approaches to this problem, including
Telex, a project between our
group and a group at the University of Michigan.
Our work on censorship resistance explores the topic both from the
technical side of designing, developing, and deploying censorship
resistance technologies, but also from the economic and political side,
examining the motivations of the censor and the resister, and analyzing
the game-theoretic aspects of their interactions.
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.
Private Information Retrieval
Private Information Retrieval, or PIR, enables people to perform online
queries to databases while protecting the privacy of their queries even
from the database operators themselves. Long considered too impractical
for real-world use, our group and others have shown that PIR can indeed
be practical for many realistic scenarios.
Our group works on creating PIR protocols that are computationally and
communicationally efficient, while also providing for Byzantine
robustness: the ability to withstand database servers that provide
erroneous results, either through faults or through malice. Our group
has produced PIR
protocols that can withstand the largest possible number of
misbehaving servers, while being thousands of times faster than previous
work.
A major challenge in this area is that the cost of performing the
private query increases with the size of the underlying database. While
we have shown success in implementing PIR systems that can efficiently
handle databases in the gigabyte range for a small number of
simultaneous clients, in order to achieve large-scale deployment, we are
working on new protocols that can efficiently handle many more
simultaneous queries, as well as larger, terabyte-sized databases.
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
a share.
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
encryption.
Efficient Zero-Knowledge Proofs
A common building block in privacy-preserving systems is the
zero-knowledge proof (ZKP). In a ZKP, one party in the protocol
(the prover) convinces another party (the verifier) of the truth of some
statement, without revealing any more information. For example, the ZKP
may assert that "the prover is authorized to access this website",
without revealing the identity of the prover. Another example is the
assertion that "the prover knows the correct password", without
revealing the password itself to the verifier (or to an
eavesdropper).
There are a number of useful simple statements—for example, that
the prover knows a particular private key—for which efficient ZKPs
are known. There are known ways to combine these simple statements using
connectives such as AND, OR, and NOT, in order to form more complex
statements, with correspondingly less efficient proofs. For certain
kinds of complex statements, there are batch techniques that can be used
to lower the cost of proving and/or verifying the complex statement to
not much more than that of a simple statement; however, in general,
complex ZKPs have high cost.
Our group has developed new batch
techniques that make a larger variety of complex ZKPs
more efficient. We are also developing a software library that can be
easily used by programmers without expertise in ZKPs to prove
and verify simple, complex, and batched statements.
Key Distribution
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
an adversary.
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
attackers.
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
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
rightful owners.
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
integrity checking.
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.