Advanced Privacy for Cryptographic Primitives and Protocols
Privacy is a fundamental property required of many cryptographic primitives and protocols. Data privacy has traditionally been considered a pillar for secure designs, and user privacy is an increasingly more sought-after property in a variety of settings.
The study of the notion of privacy in its varying strengths and contexts represents a research area the Cryptography Group focuses on.
Our results have appeared in award-winning papers and range from developing schemes satisfying increasingly stronger notions of data privacy to balancing the need for user privacy with accountability. In certain contexts, such as broadcast encryption and digital signatures, our contributions have pioneered the research on anonymity and incoercibility, a very advanced form of privacy.
Attacks on Cryptographic Protocols
Researchers in the ISG have performed and continue to perform security analyses of widely deployed cryptographic protocols, and have found cryptographic weaknesses in several of them. Examples include SSH, some TLS implementations and a mesh networking chat app advertised for use in higher-risk settings such as settings of civil unrest.
Codes and Cryptography
Codes and cryptography address different aspects of security and reliability of information. While codes tend to deal with accidental interferences, cryptography addresses the scenario of deliberate tampering. Our research in this area spans the two disciplines, often making use of combinatorial and probabilistic methods. Some of our recent and ongoing research includes fingerprinting codes for digital content protection, private information retrieval in coded and uncoded databases, storage codes for resilience and reliability, and cryptographic key management techniques for distributed environments.
Design and Analysis of Cryptographic Protocols
One of the strengths of the Cryptography Group at Royal Holloway is to design and formally analyse the security of a variety of cryptographic protocols.
This is typically done within the framework of provable security, a modern cryptography approach which allows to reason about the security guarantees of a scheme or protocol using formal definitions and rigorous proofs.
Our expertise in this area includes design and analysis of public-key encryption primitives, digital signature schemes and primitives with advanced functionalities (such as verifiable delay functions), and more complex, multi-party protocols such as secret sharing schemes, reputation systems and e-voting schemes.
In 1994, Peter Shor presented an efficient quantum algorithm for solving the computational problems (factoring and discrete logarithms in abelian groups) underpinning current public-key cryptography, invalidating their security in a world where large-scale quantum computers exist. To date, nobody has announced a sufficiently big quantum computer to run Shor's algorithm for any non-trivial problem and it remains unclear if it is at all possible. Nevertheless, recent progress in the area of quantum computing has researchers, standards bodies and governments concerned, especially given that previous transitions of cryptographic algorithms have taken about 20 years in the past. To address this issue, researchers are studying quantum-safe alternatives to the current generation of public-key cryptography. Furthermore, standards bodies have initiated processes to select algorithms for post-quantum cryptography.
As alluded to above, several candidates for post-quantum cryptography exist. However, there are still many challenges to overcome, before we can deploy these candidates with confidence. For example, these candidates have received much less scrutiny than e.g. RSA. It might be possible to find efficient quantum or even classical algorithms for solving some of the problems underlying these candidates. While this may seem unlikely, it is imperative to investigate this possibility in earnest to gain conﬁdence. Furthermore, if our schemes are secure in principle, we still need to choose parameters to ensure security well into the future. Just as we use the best available cryptanalysis to pick the required bit-size for RSA to remain secure for 50 or 100 years (in a pre-quantum world), we will have to rely on the best available cryptanalysis to pick parameters for quantum-safe schemes.
It is worth noting that quantum-safe cryptography is something rather diﬀerent to quantum key distribution (QKD), which uses quantum mechanics to establish secure keying material between two parties. The former is concerned with drop-in replacements for current-generation cryptography usable without specialised hardware, yet secure against quantum adversaries. In contrast, QKD only covers limited distances so that trusted relays are needed for larger distances, invalidating end-to-end security.
As of writing NIST is finalising its post-quantum standardisation process of public-key encryption and signature schemes. ISG researchers have made significant contributions to the process, including as part of the submission team of one of the finalists (the code-based KEM scheme “Classic McEliece”). However, even if we consider this “done” there is still much to be done to get ready for a post-quantum world. Many currently deployed solutions have no efficient post-quantum replacements yet, such as oblivious PRFs (enabling anonymous credentials), verifiable random functions (proposed for DNSSEC), private set intersection (used for privacy-preserving contact discovery), blind signatures (e-cash, e-voting, anonymous credentials). This is a next frontier for practical post-quantum cryptography, and an active area of research in the ISG.
One way of defining cryptography is as the study of the limits of computing (under adversarial conditions): what can and cannot be computed? During the last decade functionalities that were previously considered unattainable have been shown to be feasible: computing on encrypted data (fully homomorphic encryption, FHE), computing with encrypted programs (obfuscation, iO), associating secret keys to function evaluations on the plaintext (functional encryption, FE). Less generically, operations like private set intersection (PSI) have reached a level of maturity that they can be deployed in practice; secure multiparty computation (MPC) is being commercialised and building blocks (e.g. for PSI) like oblivious PRFs (OPRF) are being standardised.
This research area studies these advanced functionalities both as objects of theoretical computer science, i.e. without an immediate regard for practicality, and with a view of deploying them or variants thereof in practice. This involves studying the underlying hard (lattice) problems, devising techniques for realising certain functionalities efficiently, standards and implementations. For example, researchers in the ISG have been involved in all aspects of developing homomorphic encryption, including cryptanalysis, noise growth analysis, encoding, implementation, and investigating specific practical applications.
The Cryptography Group at Royal Holloway is interested in the study and design of secure e-voting systems.
As the primary example of a multi-party protocol, secure e-voting poses a very wide variety of challenges, from the numerous design and security requirements it needs to satisfy to its real-world implementation. These challenges, coupled with the ambition of being impactful in the context of digital democracy, makes this an extremely exciting space to work in.
Our contributions to the area include the development of cryptographically-enabled voter authentication, the study of the relation between e-voting schemes and e-auctions, and the formal analysis of the notion of vote privacy, also known as ballot secrecy, in its varying strengths.
One approach to defeating cryptographic protections is to side-step them by exploiting side-channel information from the execution of a cryptographic algorithm. This could be timing information (how long some operation takes may depend on secret data), resource utilisation (e.g. was that line loaded into cache, and if so does this tell us something about the secrets?), power consumption (e.g. did the coprocessor spin up to crank some numbers?), or plain old error messages.
Researchers in the ISG study how to exploit such side-channel leakage in order to assess the risk of cryptographic implementations. For example, one class of attacks is called “[cold boot attacks]". These attacks exploit that information in RAM is not necessarily immediately gone when the power is cut; instead a noisy version may be retained in memory for seconds (if not minutes) under deep cooling. The challenge in a second step is then to correct the errors introduced to recover the sensitive information, e.g. the secret.
Another area are lattices – whose study is a core expertise in the ISG – which are also central tools in side-channel analysis. This is because they are inherently geared towards “noisy” problems. Researchers in the ISG have applied lattice techniques to various side-channel problems to demonstrate that an attacker may use them to attack cryptographic schemes.
Social Foundations of Cryptography
Information security studies if systems satisfy the security needs of those who depend on them. The fundamental technology to assure such systems is cryptography. It is thus foundational to ask if cryptography provides the security guarantees needed and what these are. Researchers in the ISG are pursuing these foundational questions by bringing cryptography and ethnography into conversation.
While cryptography is a field that actively interrogates its foundations, these foundations are, unsurprisingly and sensibly, understood to be of the complexity-theoretic and mathematical variety. However, cryptographic security notions – and everything that depends on them – do not exist in a vacuum. While the immediate objects of cryptography are not social relations, it presumes and models them. This fact is readily acknowledged in the introductions of cryptographic papers which illustrate the utility of the work by reference to some social situation where several parties have conflicting ends but a need or desire to interact. Yet, this part of the definitional work has not received the same rigour from the cryptographic community as complexity-theoretic and mathematical questions.
This research area focuses on remedying this situation by grounding cryptographic security notions in findings from ethnographic fieldwork in adversarial situations; to establish what security means within social settings. Ethnography allows us to learn that which people do not know themselves. The exploratory nature of ethnographic enquiry, rooted in fieldwork with the group it aims to understand, is thus a key enabler in unlocking an understanding of individual and collective security needs and practices (see "Ethnography of Collective Security Needs and Practices" research area).
As a point of departure, the work carried out by ISG researchers considers large-scale urban protests to understand protesters' security needs, practices and the technologies they rely upon. Thus, while providing unique and deep insights into security needs and practices in these settings, it also analyses these technologies (see "Attacks on Cryptographic Protocols" research area) and proposes new solutions based on the findings from fieldwork (see also "Advanced Functionalities from Lattices" research area). By bringing cryptographic security notions to the field, this research area provokes a series of security questions about, for example, confidentiality and anonymity in online and offline networks, trust relations and how to establish them, onboarding and authentication practices.
Symmetric cryptography considers algorithms and schemes that provide confidentiality and/or authenticity to data, protected by a single secret key. It includes block ciphers, stream ciphers, Message Authentication Code (MAC) algorithms, and Authenticated Encryption schemes. These are some of the most widely-used building blocks in cryptography, and as such must be rigorously studied to determine whether they provide the required level of security.
In general, the most efficient known class of attacks against symmetric ciphers are statistical attacks, such as linear or differential cryptanalysis against block ciphers. In this area, researchers in the ISG have pioneered some of the fundamental techniques and continue to clarify and refine the statistics underlying these attacks and their variants.
Another class of attacks against symmetric key constructions are algebraic attacks. These attacks model the algorithm as a system of equations which is then tackled using standard algebraic techniques, e.g. Gröbner basis algorithms. Here too, researchers in the ISG made fundamental and foundational contributions to applications of algebraic techniques to symmetric key cryptanalysis.
Recent years have witnessed a spur of activity in the study of ciphers designed for algebraic platforms. That is, instead of designing block ciphers for CPUs or hardware, they are designed to be efficiently run as part of a secure computation protocol (e.g. MPC or FHE based) or in a zero-knowledge proof (ZKPoK). Used in this way these block ciphers enable many modern privacy-preserving protocols. The novel design strategies employed in these ciphers make them however interesting targets for algebraic attacks. This is an area of research pioneered by researchers in the ISG, with several contributions in new designs, and in the cryptanalysis of new proposals.