Studying integer (whole number) solutions to polynomial equations is the oldest field in mathematics, containing problems that have remained unsolved for millennia. Furthermore, its applications to cryptography and security make it one of the most high-impact areas of pure mathematics. Cryptosystems rely on the computational hardness of mathematical problems to protect our data. The realm of integer solutions to polynomial equations is a natural source of hard problems to underpin modern cryptosystems. For example, it can claim credit for the development of elliptic curve cryptography (ECC). This is a public key cryptographic system that has been widely used for over a decade by big players such as the USA National Security Agency and Microsoft. For instance, ECC is used to protect our credit card details when we make purchases over the internet. Cybersecurity is of crucial national importance in protecting data at the individual, corporate and state level and its role in daily life is increasing as more of our economic, administrative and social interactions take place online. The deep knowledge of elliptic curves needed for the development of ECC was gained by pursuing blue sky research in mathematics, of which the most famous recent example is Andrew Wiles' 1995 proof of Fermat's Last Theorem. This concerns one particular family of polynomial equations, namely x^n+y^n = z^n. When n=2, this is Pythagoras' equation relating the side lengths of a right-angled triangle. There are infinitely many integer solutions to this equation (e.g. x = 3, y = 4, z = 5) and we even have a formula for them. However, when n is greater than 2, the behaviour is very different. Fermat conjectured in 1637 that there were no positive integer solutions to the equation x^n+y^n = z^n for n greater than 2. The proof of this fact took more than 350 years and required the development of very advanced mathematical techniques. In September 2019, Google announced that they had achieved 'quantum supremacy', having developed a quantum computer that performed a task in 200 seconds where a top-range supercomputer would take 10,000 years. This stunning achievement presents a looming crisis for the cryptosystems protecting our data. A quantum computer that can solve the mathematical problems underlying current cryptosystems in seconds rather than millennia would be able to decrypt encrypted data and compromise its security. Security agencies and technology companies are urgently seeking new, and harder, mathematical problems to underlie post-quantum cryptographic systems and they are keen to collaborate with mathematicians to achieve this. My proposal is to study integer solutions to a much larger and more complex class of polynomial equations than elliptic curves, using a wide variety of techniques from number theory, algebra, geometry and analysis. The modern approach looks first for so-called local solutions and then investigates whether a collection of them can be patched together to form a global (meaning integer) solution. However, this local-global method is not always successful. I will study the reasons for its failure and conduct a statistical analysis of the frequency of these failures within families of equations. I will break new ground by tackling cases that have so far been untouched due to their complexity: the 'wild' in my title is an adjective used by mathematicians to describe mathematical objects whose behaviour is particularly difficult to handle. Recent breakthroughs in number theory mean the time is ripe to grapple with these wild problems. I will collaborate with leading cryptographers to explore possibilities arising from my research for new hard mathematical problems that can be used to underpin cryptosystems that can resist attacks by quantum computers.

The main theme that underlies this research project is automatedreasoning, an applied sub-discipline of mathematical logic. Logichas found applications in many areas of computer sciencesuch as the verification of digital circuits, reasoning aboutprograms and knowledge representation. One of the most fundamentalaspects in this context is to automatically decide whether aparticular formula is a logical consequence of a given set ofassumptions. The set of assumptions may describe complex relationsbetween diseases and their symptoms, and one possible reasoning taskwould be to confirm or reject a diagnosis based on observed symptomsand medical history.In this research project, we investigate applications ofmathematical logic in knowledge representation. One of the primechallenges in this area is to design logical formalisms that strikea balance between the two conflicting goals of expressiveness (theability to formally represent the application domain) andcomputational tractability. The family of modal logics, conceived ina broad way, combines both aspects and serves as the mathematicalfoundation of a large number of knowledge representation formalisms.The core ingredient of modal logic is the possibility to qualifylogical assertions to hold in a certain way. Depending on thecontext, we may for instance stipulate that assertion holds `alwaysin the future', `with a likelihood of at least 50%' or `normally'.Together with names for individual entities, this allows us toformulate assertions like `the likelihood of congestion on Queen'sRoad is greater than 30%', and complex knowledge bases arise bycombining different logical primitives. Automated reasoning thenallows us to mechanically verify e.g. the consistency of scientifichypotheses against an existing knowledge base. Our goal is to builda modular and practical knowledge representation system that allowsto represent and reason about knowledge represented in this way,based on a large and diverse class of logical primitives, includinge.g. the coalitional behaviour of agents, quantitative uncertainty,counterfactual reasoning and default assumptions. This goes waybeyond the current state of the art, where only logical primitiveswith a relational interpretation are supported by automated tools.Recent research has shown these new logical features can beaccounted for in a uniform way by passing to a more generalmathematical model, known as `coalgebraic semantics'. This richerframework does not only provide a uniform umbrella for a largenumber of reasoning principles, but also supports a richmathematical theory that has by now matured to the extent which putsthe development of automated tools within reach. The researchchallenge that this proposal addresses is the further development of thesetheoretical results as to bring them to bear on practical applications.As a concrete case study, we will use the Cool system to formalisequantitative models in Systems Biology.

Running elections is challenging while maintaining election integrity and increased voter confidence. Recent examples have shown that both traditional and online voting systems are not sufficient resilient to achieve this, e.g. 2022 Nigeria election (e.g., voting starting late, accusations of vote tampering, and technical issues with the voting devices), 2020 US presidential election (e.g., unsubstantiated claims and voter mistrust over voting device corruption and doubts over election integrity), 2019 Moscow election (e.g., cryptographic issues), and 2011-2013 Norway elections (e.g., software inaccuracies, voters voting twice - online and in-person). In 2020 the European Commission for democracy through law has highlighted in their CDL-AD(2020)025-e report that dispute-resolution is an essential requirement for successful elections. Their focus has been on providing an overview of the types of disputes that appear in polling stations and the legal mechanisms to handle complaints. The 2022 UK Tory leadership election (that used online voting) and the UK House of Commons divisions raise interesting challenges that have not been previously addressed. This project will build the foundations for real-world dispute-resolution in voting by formalizing disputes, types and timing of dispute evidence, and introducing definitions to accurately model those disputes and their context. Moreover, it will propose novel dispute-resolution mechanisms to completely solve or mitigate those disputes. Research into dispute-resolution has been so underdeveloped, as there are few voting protocols that are known or believed to satisfy dispute-resolution. The project will enhance existing academic protocols (e.g., Helios, Belenios, Selene, JCJ/Civitas) and real-world systems (e.g., ElectionGuard, Swiss Postal Voting) to satisfy dispute-resolution. To ensure the confidence in our analysis, we'll provide where appropriate machine-checked proof guarantees for the novel mechanisms and updated protocols and systems.

Most modern cryptographic constructions are accompanied by a proof of security, in which the difficulty of violating the security of the construction (e.g., distinguishing ciphertexts for an encryption scheme) is reduced to the difficulty of solving a certain algebraic problem. Cryptographic proofs of security - also called reductions - thus lie at the heart of provable security, yet writing and verifying cryptographic reductions is currently a time-intensive and manual process, with most reductions highly individualised for a specific primitive or algebraic setting. By identifying proof techniques common to many settings, the landscape of both reductions and the hardness assumptions that constructions rely on for security can be vastly simplified. In a previous project, we demonstrated that certain proof techniques could also be applied outside of the settings for which they were originally intended, and moreover could be applied to show the equivalence of certain ad-hoc assumptions and more well-established assumptions. Thus, rather than avoid ad-hoc assumptions by providing new constructions or writing new reductions, we demonstrated that the security of a variety of existing constructions - which had relied previously on these ad-hoc assumptions for security - could now be considered secure under a milder assumption. In this work, we will formalise techniques that are common across different proofs in a fashion that makes them easier to reuse, verify, and apply to new settings. This will not only make reductions easier to both write and understand, but also expand the applicability of useful proof techniques.

Subgraph-finding problems involve identifying patterns in structured data. In theory these problems should be computationally hard for an algorithm to solve, but in practice intelligent constraint-based algorithms can quickly solve even large problems. This research will uses scientific (rather than purely mathematical) techniques to increase our understanding of this gap between theory and practice, and will allow us to design better algorithms in the future. The research is based upon analysing proof logs, which are a mathematical description of how an algorithm reached its answer.