# Dr Robert Granger

## Academic and research departments

Faculty of Engineering and Physical Sciences, Department of Computer Science.### Biography

Robert Granger holds an MSci from the School of Mathematics, University of Bristol (2002) and a PhD from the Department of Computer Science, University of Bristol (2006). He has held postdoctoral positions at: the Centre for Applied Cryptographic Research, University of Waterloo, Canada; his alma mater, again in the Cryptography and Information Security Group; and at the Claude Shannon Institute, University College Dublin, Ireland. Before joining the University of Surrey as a Lecturer in Secure Systems in December 2018, he was a scientist in the Laboratory for Cryptologic Algorithms, EPFL, Switzerland.

### Areas of specialism

### Affiliations and memberships

### News

### In the media

### Research

### Research interests

I am a computational number theorist whose main specialism is the number-theoretic assumptions, applications and algorithms underlying public key cryptography. I have over a decade of experience conceiving and leading often groundbreaking research projects in this area, and am an expert in foundational cryptographic security assumptions. In particular, I have designed several highly original discrete logarithm algorithms for various algebraic groups (one receiving the Best Paper Award, CRYPTO 2013) and have set several world records for discrete logarithm computations with my teams. I have a natural passion for attacking interesting and hard problems (in cryptography and elsewhere), combining deep insights with powerful mathematical and computational techniques. In addition to cryptography and cryptanalysis, number theory, algebraic geometry, algorithm design, discrete mathematics and finite field theory, I am interested in various theoretical properties of irreducible polynomials and curves over finite fields.

### Supervision

## Postgraduate research supervision

Current PhD students:

- Bruno Sterner

Previous PhD students (co-supervised):

- Benjamin Wesolowski (EPFL 2018)
- Naomi Benger (CSI 2010)

### My teaching

This year (2019/20) I am teaching

- Asymmetric Cryptography (COMM045) in the Information Security MSc,
- Foundations of Computing II (COM1033) in the CS BSc and the CIT BSc (jointly with Dr. Yunpeng Li).

I am also supervising Professional Projects (COM3001), MSc dissertations (COMM002) and Professional Training (Computer Science) placements.

Last year (2018/19) I was a supporting lecturer for Data Structures and Algorithms (COM1029) and supervised Professional Projects (COM3001) and Professional Training (Computer Science) placements.

### My publications

### Publications

^{n?l}+ O(q

^{n/2})). The main idea behind the algorithm is to associate to an equivalent problem a set of Artin-Schreier curves defined over F

_{q}whose number of F

_{qn}-rational affine points must be combined. This is accomplished by computing their zeta functions using a p-adic algorithm due to Lauder and Wan. Using the computational algebra system Magma one can, for example, compute the zeta functions of the arising curves for q=5 and l=4 very efficiently, and we detail a proof-of-concept demonstration. Due to the failure of Newton's identities in positive characteristic, the lep cases are seemingly harder. Nevertheless, we use an analogous algorithm to compute example curves for q=2 and ld7, and for q=3 and l=3. Again using Magma, for q=2 we computed the relevant zeta functions for l=4 and l=5, obtaining explicit formulae for these open problems for n odd, as well as for subsets of these problems for all n, while for q=3 we obtained explicit formulae for l=3 and n coprime to 3. We also discuss some of the computational challenges and theoretical questions arising from this approach in the general case and propose some natural open problems.

problem (DLP) in finite fields of small characteristic. Consequently, many cryptosystems

based on cryptographic pairings were rendered completely insecure, which serves as a

valuable reminder that long-studied so-called hard problems may turn out to be far easier

than initially believed. In this article, Robert Granger gives an overview of the surprisingly

simple ideas behind some of the breakthroughs and the many computational records that

have so far resulted from them.

_{q}if and only if its group order is divisible by 8 if q a ?1 (mod 4), and 16 if q a 1 (mod 4). Furthermore, we give formulae for the proportion of d ? F

_{q}\ {0, 1} for which the Edwards curve E

_{d}is complete or original, relative to the total number of d in each isogeny class

_{2n}or F×

_{3n}is a zero of the corresponding Kloosterman sum over these fields, and rigorously analyse its runtime. The test seems to have been overlooked in the literature. The expected cost of the test for binary fields is a single point-halving on an associated elliptic curve, while for ternary fields the expected cost is one-half of a point-thirding on an associated elliptic curve. For binary fields of practical interest, this represents an O(n) speedup over the previous fastest test. By repeatedly invoking the test on random elements of F×

_{2n}we obtain the most efficient probabilistic method to date to find nontrivial Kloosterman sum zeros. The analysis depends on the distribution of Sylow p-subgroups in the two families of associated elliptic curves, which we ascertain using a theorem due to Howe.

_{2r}where the coefficients of x

^{n?1}, x

^{n?2}and x

^{n?3}are zero. Our proofs involve counting the number of points on certain algebraic curvesover finite fields, a technique which arose from Fourier-analysing the known formulae for the F

_{2}base field cases, reverse-engineering an economical new proof and then extending it. This approach gives rise to fibre products of supersingular curves and makes explicit why the formulae have period 24 in n.

_{qn}), if an adversary has access to a Static Diffie-Hellman Problem (Static DHP) oracle, then by making O(q

^{1? 1/n+1}) Static DHP oracle queries during an initial learning phase, for fixed n > 1 and q ? the adversary can solve any further instance of the Static DHP in heuristic time OÜ(q

^{1? 1/n+1}). Our proposal also solves the Delayed Target DHP as defined by Freeman, and naturally extends to provide algorithms for solving the Delayed Target DLP, the One-More DHP and One-More DLP, as studied by Koblitz and Menezes in the context of Jacobians of hyperelliptic curves of small genus. We also argue that for any group in which index calculus can be effectively applied, the above problems have a natural relationship, and will always be easier than the DLP. While practical only for very small n, our algorithm reduces the security provided by the elliptic curves defined over F

_{p2}and F

_{p4}proposed by Galbraith, Lin and Scott at EUROCRYPT 2009, should they be used in any protocol where a user can be made to act as a proxy Static DHP oracle, or if used in protocols whose security is related to any of the above problems.

masking, where a certain primitive (a blockcipher or a permutation) is

preceded and followed by an easy-to-compute tweak-dependent mask.

In this work, we revisit the principle of masking. We do so alongside

the introduction of the tweakable Even-Mansour construction MEM. Its

masking function combines the advantages of word-oriented LFSR- and

powering-up-based methods. We show in particular how recent advancements in computing discrete logarithms over finite fields of characteristic 2 can be exploited in a constructive way to realize highly efficient,

constant-time masking functions. If the masking satisfies a set of simple conditions, then MEM is a secure tweakable blockcipher up to the

birthday bound. The strengths of MEM are exhibited by the design

of fully parallelizable authenticated encryption schemes OPP (nonce-respecting) and MRO (misuse-resistant). If instantiated with a reducedround BLAKE2b permutation, OPP and MRO achieve speeds up to 0.55

and 1.06 cycles per byte on the Intel Haswell microarchitecture, and are

able to significantly outperform their closest competitors.

_{2521-1}, Proceedings of the 18th IACR International Conference on Practice and Theory in Public-Key Cryptography - Public-Key Cryptography (PKC 2015). Lecture Notes in Computer Science. 9020 pp. 539-553 Springer, Berlin, Heidelberg

^{521}? 1. Using this approach, on an Intel Haswell Core i7-4770, constant-time variable-base scalar multiplication on NIST?s (and SECG?s) curve P-521 requires 1,108,000 cycles, while on the recently proposed Edwards curve E-521 it requires just 943,000 cycles. As a comparison, on the same architecture openSSL?s ECDH speed test for curve P-521 requires 1,319,000 cycles. Furthermore, our code was written entirely in C and so is robust across different platforms. The basic observation behind these speedups is that the form of the modulus allows one to multiply residues with as few word-by-word multiplications as is needed for squaring, while incurring very little overhead from extra additions, in contrast to the usual Karatsuba methods

_{21223}, and reduce the security of a genus two curve over F

_{2367}to 94.6 bits. In this paper we propose a new field representation and efficient general descent principles which together make the new techniques far more practical. Indeed, at the ?128-bit security level? our analysis shows that the aforementioned genus one curve has approximately 59 bits of security, and we report a total break of the genus two curve

_{qn}(1/3,(4/9)

^{1/3}) for computing arbitrary logarithms, but also in an heuristic polynomial time algorithm for finding the discrete logarithms of degree one and two elements when the field has a subfield of an appropriate size. To illustrate the efficiency of the method, we have successfully solved the DLP in the finite fields with 2

^{1971}and 2

^{3164}elements, setting a record for binary fields.

to arbitrary algebraic curves. It has the following surprising properties:

The loop length in Miller?s algorithm can be up to g times shorter than

for the Tate pairing, with g the genus of the curve, and the pairing is

automatically reduced, i.e. no final exponentiation is needed.

^{6120}elements, using just a single core-month. Relative to the previous record set by Joux in the field of 2

^{4080}elements, this represents a 50 % increase in the bitlength, using just 5 % of the core-hours. We also show that for the fields considered, the parameters for Joux?s L

_{Q}(1/4 + o(1)) algorithm may be optimised to produce an L

_{Q}(1/4) algorithm.

^{×}

_{q6}, for q a 1 mod 6. Our result arises from considering the Weil restriction of scalars of this group from F

_{q6}to F

_{q2}, and provides efficiency improvements for both pairing-based and torus-based cryptographic protocols. In particular we argue that such fields are ideally suited for the latter when the field characteristic satisfies p a 1 (mod 6), and since torus-based techniques can be applied to the former, we present a compelling argument for the adoption of a single approach to efficient field arithmetic for pairing-based cryptography.

way of using the algebraic tori T

_{n}in cryptography, and obtained an

asymptotically optimal n/Æ(n) savings in bandwidth and storage for a

number of cryptographic applications. However, the computational requirements of compression and decompression in their scheme were impractical, and it was left open to reduce them to a practical level. We

give a new method that compresses orders of magnitude faster than the

original, while also speeding up the decompression and improving on the

compression factor (by a constant term). Further, we give the first efficient implementation that uses T

_{30}, compare its performance to XTR,

CEILIDH, and ECC, and present new applications. Our methods achieve

better compression than XTR and CEILIDH for the compression of as

few as two group elements. This allows us to apply our results to ElGamal encryption with a small message domain to obtain ciphertexts that

are 10% smaller than in previous schemes.

_{pm}) and T6(F

_{pm}) for various p and m. Our results do not affect the security of the cryptosystems LUC, XTR, or CEILIDH over prime fields. However, the practical efficiency of our method against other methods needs further examining, for certain choices of p and m in regions of cryptographic interest.

_{3n}. Motivated by attacks on identity based encryption systems using supersingular elliptic curves, we pay special attention to the case where n is composite. This allows us to represent the function field over different base fields. Practical experiments appear to show that a function field over F

_{3}gives the best results.

^{×}

_{pn}for small p. Specifically, we obtain sharp probability estimates that allow us to select optimal parameters in cases of cryptographic interest, without appealing to the heuristics commonly relied upon in an asymptotic analysis. We also give evidence that for any fixed field size some may be weaker than others of a different characteristic or field representation, and compare the relative difficulty of computing discrete logarithms via the FFS in such cases.