Research

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.