Plenary Speakers

Abstract: Basing security of encryption on NP-hardness is a longstanding challenge in the foundations of cryptography. Under standard complexity-theoretic assumptions, such encryption should be secure even if the adversary had access to a statistical zero-knowledge (SZK) oracle, which is believed to have the ability to solve some intractable problems but not NP-complete ones.

I will show some examples of classical and newer public-key encryption schemes that are vulnerable to SZK attacks, and some for which an SZK attack is not known. I will then speculate about the role of “statistical-to-computational gaps” in building SZK-resilient public-key encryption.

Bio: Andrej Bogdanov is professor of Computer Science and Engineering and member of the Institute of Theoretical Computer Science and Communications at the Chinese University of Hong Kong. His research interests are in cryptography, pseudorandomness, and sublinear-time algorithms.

Andrej obtained his Ph.D. from UC Berkeley in 2005. Before joining CUHK in 2008 he was a postdoctoral researcher at the Institute for Advanced Study in Princeton, at DIMACS (Rutgers University), and at ITCS (Tsinghua University). He was a visiting professor at the Tokyo Institute of Technology in 2013 and at the UC Berkeley Simons Institute for the Theory of Computing in 2017 and 2021.

Abstract: In this talk we consider extremal vertex-sets in graphs. For a property Π, the extremal vertex-sets are either the inclusion-wise minimal or the inclusion-wise maximal vertex-sets with property Π. We establish bounds on the largest number of such extremal vertex-sets a graph may have, discuss enumeration algorithms, and their use in exponential time algorithms.

Bio: Serge Gaspers is a Professor at UNSW Sydney. His expertise is in exponential time algorithms and parameterized complexity. In his study of intractable computational problems, he designs algorithms for NP-hard problems, analyses their running time, and makes fine-grained complexity classifications. These computational problems have applications in Boolean satisfiability and constraint satisfaction, networks and graphs, and algorithmic decision theory.

Before joining UNSW as a DECRA and then a Future Fellow, he held postdoctoral positions at TU Wien (Austria), Univerisidad de Chile (Chile), and Université Montpellier II (France), and he obtained a PhD under the supervision of Fedor V. Fomin at Universitetet i Bergen (Norway).

Abstract: Zero-Knowledge proofs (ZKPs) are cryptographic proof systems which allow a prover to convince a verifier about the knowledge of a secret without revealing any secret information. Lattice-based zero-knowledge proofs have the additional conjectured property of being resistant against quantum attacks. Lattice-based cryptography is an area of post-quantum cryptography where the security of the crypto schemes is based on mathematical hard problems around lattices. Secure zero-knowledge proofs from lattices are not obvious and require several mathematical techniques from different mathematical disciplines. In this talk I will address the main challenges of secure constructions of lattice-based zero-knowledge proofs.

Bio: Veronika Kuchta received her Diploma degree in Mathematics at the Heidelberg University in Germany in 2010. She reseived her PhD in applied cryptography at the University of Surrey, United Kingdom in 2016. She worked as a postdoc at the Universite libre de Bruxelles in Belgium from 2016-2018. From 2018 till 2020 she has been a Research Fellow at Monash University in Melbourne, Australia. Since December 2020 she has joined The University of Queensland, School of Mathematics and Physics as a lecturer in mathematical cryptography. Her research interests focus on the different areas of mathematical cryptography, post-quantum cryptography and its applications to the real-world.

Abstract: Differential privacy (DP) provides a rigorous framework for releasing data statistics while bounding information leakage. It is currently a de facto privacy framework that has received significant interest from the research community and has been deployed by the U.S. Census Bureau, Apple, Google, Microsoft, and others. However, DP analysis often assumes a perfect computing environment and building blocks such as random noise distribution samplers. Unfortunately, a naive implementation of DP mechanisms can invalidate their theoretical guarantees.

In this talk, I will highlight two attacks based on implementation flaws in the noise generation commonly used in DP systems: floating-point representation attack against continuous distributions and timing attacks against discrete distributions. I will then show that several state-of-the-art implementations of DP are susceptible to these attacks as they allow one to learn the values being protected by DP. Our evaluation demonstrates success rates of 92.56% for floating-point attacks in a machine learning setting and 99.65% for end-to-end timing attacks on private sum. I will conclude with suggested mitigations, emphasising that a careful implementation of DP systems may be as important as it is for cryptographic libraries.

The talk is based on joint work with Jiankai Jin (The University of Melbourne), Eleanor McMurtry (ETH Zurich) and Benjamin Rubinstein (The University of Melbourne). To appear in IEEE Symposium on Security and Privacy 2022.

Bio: Olya Ohrimenko is an Associate Professor at The University of Melbourne which she joined in 2020. Prior to that she was a Principal Researcher at Microsoft Research in Cambridge, UK, where she started as a Postdoctoral Researcher in 2014. Her research interests include privacy and integrity of machine learning algorithms, data analysis tools and cloud computing, including topics such as differential privacy, verifiable and data-oblivious computation, trusted execution environments, side-channel attacks and mitigations. Recently Olya has worked with the Australian Bureau of Statistics and National Bank Australia. She has received solo and joint research grants from Facebook and Oracle and is currently a PI on an AUSMURI grant. Olya holds a Ph.D. degree from Brown University and a B.CS. (Hons) degree from the University of Melbourne. See https://people.eng.unimelb.edu.au/oohrimenko/ for more information.

Abstract: I'll talk about two ways mathematics can improve election security: cryptographic proofs and statistical auditing. First, I'll describe the errors we found in the SwissPost/Scytl/iVote mixing and decryption zero knowledge proofs - I'll explain how the proofs were supposed to work, what the errors were, and how to fix them. Second, I'll discuss recent work extending statistical auditing techniques to complex Australian-style preferential elections. I'll conclude with some examples of current practice in Aus to show you how much Australian electoral practice needs more input from Australian mathematicians.

Joint work with Thomas Haines, Sarah Jamie Lewis, Olivier Pereira, Michelle Blom, Andrew Conway, Philip Stark, Peter Stuckey, Ron Rivest and Damjan Vukcevic.

Bio: Vanessa Teague is the CEO of Thinking Cybersecurity and Associate Prof (Adj.) in the Research School of Computer Science at the Australian National University. Her research focuses primarily on cryptographic methods for achieving security and privacy, particularly for issues of public interest such as election integrity and the protection of government data. She was part of the team (with Chris Culnane and Ben Rubinstein) who discovered the easy re-identification of doctors and patients in the Medicare/PBS open dataset released by the Australian Department of Health. She has co-designed numerous protocols for improved lection integrity in e-voting systems, and co-discovered serious weaknesses in the cryptography of deployed e-voting systems in New South Wales, Western Australia and Switzerland. She lives and works on Wurundjeri land in Southeastern Australia (near Melbourne).

Abstract: Markov chains can be useful as algorithms for approximate sampling from large combinatorial sets. In many situations, they can also be used for approximate counting, by reduction to sampling. The good news is that Markov chain algorithms are sometimes the only known polynomial-time sampling algorithm for a given problem. However, the bad news is that quite often the polynomial runtime bounds that we are able to prove have very high degree, making these algorithms unappealing in practice.

I will discuss the use of Markov chains, as well as alternative approaches, for sampling or counting colourings or independent sets in a given graph, and for sampling graphs with given degrees.

Bio: Catherine Greenhill started her academic career as an undergraduate at the University of Queensland, before obtaining a D.Phil. from the University of Oxford (1992). She held postdoctoral positions at the University of Leeds and at the University of Melbourne, then joined UNSW in 2002. Today she is a Professor and head of the Combinatorics group in the School of Mathematics and Statistics, UNSW Sydney. Catherine's research interests lie in asymptotic, probabilistic and algorithmic combinatorics. She was awarded the Christopher Heyde Medal by the Australian Academy of Science in 2015. Her work lies at the interface between discrete mathematics, theoretical computer science and probability, and has been applied by researchers in various areas including physics and cryptography.

Abstract: In 1976, Appel and Haken announced a proof of the 4-colour theorem that fundamentally relied on extensive computer calculations that could never be verified by hand. Despite the vehement negative reactions to this announcement by various prominent mathematicians and philosophers and their dire warnings about the death of proof, mathematics has somehow survived its predicted collapse. Combinatorics in particular has not only survived, but has grown enormously over the last 50 years, not despite the use of the computers, but at least partly because of the use of computers.

Computational combinatorics is an umbrella term describing a style of research that involves “combining pure mathematics, algorithms and computational resources to solve problems in pure combinatorics”. This broad term encompasses many computational tasks, including direct search for examples or counterexamples, construction of databases of combinatorial objects, experimenting with small cases to develop or fine-tune conjectures consistent with the data, and so on.

Almost all of my own research could be described as computational combinatorics, but often the final papers downplay (or even omit) details of the computations that were instrumental in finding the results. In this talk, I will describe some of the computational techniques, tools and software that I have used, focusing on my research into binary matroids and cubelike graphs as illustrative examples throughout.

No specific prior knowledge of binary matroids or cubelike graphs is needed to follow the talk, because it turns out that both binary matroids and cubelike graphs are essentially just sets of vectors in a binary vector space, just viewed from different perspectives (which will be fully explained).

Bio: Gordon Royle completed his PhD at UWA in 1987 under the joint supervision of Cheryl Praeger and Brendan McKay. He then spent 18 months at the University of Waterloo, working with Ron Read and Chris Godsil, before spending two years at Vanderbilt University in Nashville. He was then offered a continuing position in the Computer Science department at UWA, and has remained at UWA ever since, though moving from Computer Science to the department of Mathematics and Statistics in 2008. His research interests are centred around graph theory, especially algebraic graph theory and graph polynomials, but also related areas such as groups acting on graphs, finite geometries and matroid theory. One unifying thread throughout his research is the extensive use of computation, occasionally massive computation, as an integral part of the research process.

Abstract: Plane substructures in drawings of graphs are an active area of research. Among other things, they may be useful to prove structural or combinatorial results on the underlying graphs. For example, a lower bound on the number of combinatorially different simple drawings of the complete graph has been shown under the assumption that each such drawing contains a plane Hamiltonian cycle. However, it is still open whether this assumption holds as finding plane substructures in those drawings turns out to be surprisingly difficult.

In my talk, I discuss recent improvements on lower bounds for the number of pairwise disjoint edges and the length of plane paths in simple drawings of complete graphs. A main ingredient is a special class of simple drawings that we call generalized twisted drawings. These have surprising properties and might also be of interest for other questions.

Bio: Birgit Vogtenhuber studied mathematics and computer science in Vienna and Graz and was then offered a tenure track position at Graz University of Technology, where she is an associate professor since 2019. Always having enjoyed collaborating with different people, she has made multiple long-term research visits to universities in Europe and the Americas and organized several research workshops.

Birgit's research interests revolve around drawings of graphs and their abstractions. She works on combinatorial questions, for instance on the existence of plane substructures in simple drawings of graphs, the number of triangulations, crossing numbers, or Erdős–Szekers type questions. She also investigates complexity-theoretic and algorithmic questions like extendability of drawings of non-complete graphs or realizability of rotation systems as drawings of specific graph classes.

Abstract: It can be useful to sample from a class of objects uniformly at random, for instance in order to test algorithms. This can be easy if the objects can be counted in appropriate ways. Even approximate counts can be sometimes be used for exactly uniform sampling, for instance via rejection sampling. We discuss a family of algorithms that are useful for generating random graphs with given degrees, and related structures such as Latin rectangles and statistical contingency tables. These algorithms achieve a precisely uniform distribution, and using recent ideas they can be implemented so as to run very efficiently provided that the objects being generated are not very "dense".

Bio: Nick Wormald is a Professor of Mathematics at Monash University, having joined the School of Mathematics in 2013 as an Australian Laureate Fellow. After gaining a PhD at the University of Newcastle, he held appointments at University of Waterloo, then Louisiana State University, the Universities of Newcastle, Auckland and Melbourne, and again Waterloo as a Canada Research Chair.

Nick specialises in random graphs and probabilistic combinatorics, graph theory, enumeration, the analysis of graph algorithms, Steiner trees, and other areas in combinatorics, and has also worked on the optimisation of underground mine access networks.