Postdoc Position at Royal Holloway on Key Exchange

Carlos and I have a postdoc position on designing cryptographic key exchange protocols that support incorporating key material from, erm, … diverse sources. This is part of a consortium that looks at integrating some quantum cryptography with post-quantum cryptography, but there is no need to think so narrowly about the problem. That is, the project is about incorporating randomness from wherever it might come and what security goals can be achieved depending on what is compromised. More generally, if you enjoy cryptographic protocols, not limited to key exchange protocols, this might be a fitting postdoc position. Get in touch with Carlos or me, if you’re unsure on whether the position is a good fit.

 Location: Egham Salary: £39,479 to £41,743 per annum – including London Allowance Closing Date: Tuesday 12 March 2019 Interview Date: To be confirmed Reference: 0219-048

The Information Security Group at Royal Holloway University of London is seeking to recruit a postdoctoral research assistant (PDRA) to work in the area of cryptography. The position is available for immediate start, for up to 26 months (until 31 March 2021).

The PDRA will work alongside Prof. Carlos Cid, Dr. Martin Albrecht and other cryptographic researchers at Royal Holloway on topics connected to the design and analysis of cryptographic key exchange protocols that support incorporating key material from diverse sources. This post is part of the AQuaSec project, a Innovate UK-funded research project with 17 partners from industry and academia, aiming to develop technologies for quantum-safe communications by integrating post-quantum cryptography with techniques from quantum cryptography.

Applicants for this role should have already completed, or be close to completing, a PhD in a relevant discipline, with an outstanding research track record in cryptography. Applicants should be able to demonstrate scientific creativity, research independence, and the ability to communicate their ideas effectively in written and verbal form. Salary is £39,479 per annum, inclusive of London Allowance. This post is appointed at Grade 7, Spine point 34.

Established in 1990, the Information Security Group at Royal Holloway was one of the first dedicated academic groups in the world to conduct research and teaching in information security. The ISG is today a world-leading interdisciplinary research group with 20 full-time members of staff, several postdoctoral research assistants and over 50 PhD students working on a range of subjects in cyber security, in particular cryptography.

In return we offer a highly competitive rewards and benefits package including:

• Generous annual leave entitlement
• Training and Development opportunities
• Pension Scheme with generous employer contribution
• Various schemes including Cycle to Work, Season Ticket Loans and help with the cost of Eyesight testing.
• Free parking
• Competitive Maternity, Adoption and Shared Parental Leave provisions

The post is based in Egham, Surrey where the College is situated in a beautiful, leafy campus near to Windsor Great Park and within commuting distance from London.

To view further details of this post and to apply please visit https://jobs.royalholloway.ac.uk. For queries on the application process the Human Resources Department can be contacted by email at: recruitment@rhul.ac.uk. Informal enquiries can be made to Prof. Carlos Cid at carlos.cid@rhul.ac.uk.

Closing Date: Midnight, 12 March 2019

Interview Date: To be confirmed

PS: I will have two more postdoc positions, on lattice-based cryptography in the next few weeks/months.

10 PhD Positions at Royal Holloway’s Centre for Doctoral Training in Cyber Security

At Royal Holloway we are now taking applications for ten fully-funded PhD positions in Information Security. See the CDT website and the ISG website for what kind of research we do. In particular, check out our past and current CDT students to get an idea of how broad and diverse the areas of information security are in which they work.

Note that most of these positions are reserved for UK residents, which does, however, not mean nationality (see CDT website for details) and there might also be some wiggle room for EU residents.

Postdoc at Royal Holloway on Lattice-based Cryptography

I am looking for a postdoc to join us to work on lattice-based cryptography. This postdoc is funded by the EU H2020 PROMETHEUS project for building privacy preserving systems from advanced lattice primitives. At Royal Holloway, the project is looked after by Kenny Paterson and me. Feel free to e-mail me with any queries you might have.

The ISG is a nice place to work; it’s a very friendly environment with strong research going on in several areas. We got people working across the field of information security including several people working on cryptography. A postdoc here is a 100% research position, i.e. you wouldn’t have teaching duties. That said, if you’d like to gain some teaching experience, we can arrange for that as well.

Also, if you have e.g. a two-body problem and would like to discuss flexibility about being in the office, feel free to get in touch.

 Location Egham Salary £36,654 per annum – including London Allowance Closing Date Monday 17 September 2018 Interview Date To be confirmed Reference 0818-334

The ISG is seeking to recruit a post-doctoral research assistant to work in the area of cryptography. The position is available now and will run until the end of 2021.

The PDRA will work alongside Dr. Martin Albrecht and other cryptographic researchers at Royal Holloway on topics in lattice-based cryptography. This post is part of the EU H2020 PROMETHEUS project (http://prometheuscrypt.gforge.inria.fr) for building privacy preserving systems from advanced lattice primitives. Our research focus within this project is on cryptanalysis and implementations, but applicants with a strong background in other areas such as protocol/primitive design are also encouraged to apply.

Applicants should have already completed, or be close to completing, a PhD in a relevant discipline. Applicants should have an outstanding research track record in cryptography. Applicants should be able to demonstrate scientific creativity, research independence, and the ability to communicate their ideas effectively in written and verbal form.

In return we offer a highly competitive rewards and benefits package including generous annual leave and training and development opportunities. This is a full time fixed term post is based in Egham, Surrey where the College is situated in a beautiful, leafy campus near to Windsor Great Park and within commuting distance from London.

Informal enquiries can be made to Martin Albrecht at martin.albrecht@royalholloway.ac.uk.

To view further details of this post and to apply please visit https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0818-334. For queries on the application process the Human Resources Department can be contacted by email at: recruitment@rhul.ac.uk.

Closing Date: Midnight, 17th September 2018

Interview Date: To be confirmed

NTT Considered Harmful?

In a typical Ring-LWE-based public-key encryption scheme, Alice publishes

$(a, b) = (a, a \cdot s + e) \in \mathbb{Z}_q[x]/(x^n+1)$

(with $n$ a power of two1) as the public key, where $s, e$ are both “small” and secret. To encrypt, Bob computes

$(c_{0}, c_{1}) = (v \cdot a + e', v \cdot b + e'' + \textnormal{Encode}(m))$

where $v, e', e''$ are small, $m$ is the message $\in \{0,1\}^n$ and $\textnormal{Encode}(\cdot)$ some encoding function, e.g. $\sum_{i=0}^{n-1} \lfloor \frac{q}{2} \rfloor m_i x^i$ . To decrypt, Alice computes

$c_{0} \cdot s - c_{1} = (v \cdot a + e')\cdot s - v \cdot (a\cdot s + e) + e'' + \textnormal{Encode}(m),$

which is equal to $e' \cdot s - v \cdot e + e'' + \textnormal{Encode}(m)$. Finally, Alice recovers $m$ from the noisy encoding of $m$ where $e' \cdot s - v \cdot e + e''$ is the noise. In the Module-LWE variant the elements essentially live in $\left(\mathbb{Z}_q[x]/(x^n+1)\right)^k$, e.g. $a$ is not a polynomial but a vector of polynomials.

Thus, both encryption and decryption involve polynomial multiplication modulo $x^n+1$. Using schoolbook multiplication this costs $\mathcal{O}(n^2)$ operations. However, when selecting parameters for Ring-LWE, we can choose $q \equiv 1 \bmod 2n$ which permits to use an NTT to realise this multiplication (we require $\equiv \bmod 2n$ to use the negacyclic NTT which has modular reductions modulo $x^n+1$ baked in). Then, using the NTT we can implement multiplication by

1. evaluation (perform NTT),
2. pointwise multiplication,
3. interpolation (perform inverse NTT).

Steps (1) and (3) take $\mathcal{O}(n \log n)$ operations by using specially chosen evaluation points (roots of one). Step (2) costs $\mathcal{O}(n)$ operations.

This is trick is very popular. For example, many (but not all!) Ring-LWE based schemes submitted to the NIST PQC competition process use it, namely NewHope, LIMA (go LIMA!), LAC, KCL, HILA5, R.EMBLEM, Ding Key-Exchange, CRYSTALS-KYBER, CRYSTALS-DILITHIUM (sorry, if I forgot one). Note that since steps (1) and (3) are the expensive steps, it makes sense to remain in the NTT domain (i.e. after applying the NTT) and only to convert back at the very end. For example, it is faster for Alice to store $s, e$ in NTT domain and, since the NTT maps uniform to uniform, to sample $a$ in NTT domain directly, i.e. to just assume that a random vector $a$ is already the output of an NTT on some other random vector.

This post is about two recent results I was involved in suggesting that this is not necessarily always the best choice (depending on your priorities.)

Warning: This is going to be one of those clickbait-y pieces where the article doesn’t live up to the promise in the headline. The NTT is fine. Some of my best friends use the NTT. In fact I’ve implemented and used the NTT myself.

10 PhD Positions at Royal Holloway’s Centre for Doctoral Training in Cyber Security

At Royal Holloway we have ten PhD positions in Information Security. The catch is that almost all of those positions are reserved for UK residents. Note that this does not mean nationality, see funding page (there might also be some wiggle room in some cases). For more information see the CDT website and the ISG website for what kind of research we do.

Welcome to the EPSRC Centre for Doctoral Training (CDT) in Cyber Security at Royal Holloway. The Centre was established in 2013, and has as its main objective to produce cohorts of highly-trained researchers with a broad understanding of cyber security.

The CDT is hosted by the Information Security Group (ISG), and provides multidisciplinary training to annual cohorts of around ten students each. The students follow a 4-year doctoral programme: the first phase consists of a taught component comprising 25 per cent of the programme. The remaining three years follow the more traditional path of doctoral studies, with each student undertaking research in an advanced topic in the field of cyber security. See the CDT Course of Study page for more information about the programme.

CDT recruitment typically runs from November to April, to select students for the CDT cohort to start the following September. Selected applicants are awarded fully-funded PhD studentships (stipend and College fees) for four years. We consider applications from candidates with undergraduate and masters qualifications in a wide range of disciplines, including, but not limited to, mathematics, computer science, and electrical and electronic engineering.

We are now open to receive applications for students to start their PhD studies in September 2018.

Postdoc at Royal Holloway on Post-Quantum Cryptography in Hardware

Together with Carlos Cid, we have a two-year postdoc position available. The position is focused on hardware implementations of post-quantum cryptography such as lattice-based, code-based, hash-based or mq-based schemes. If you are interested, feel free to get in touch with Carlos or me. If you know of somone who might be interested, we would appreciate if you could make them aware of this position.

Large Modulus Ring-LWE and Module-LWE

Our paper Large Modulus Ring-LWE ≥ Module-LWE — together with Amit Deo — was accepted at AsiaCrypt 2017. Here’s the abstract:

We present a reduction from the module learning with errors problem (MLWE) in dimension $d$ and with modulus $q$ to the ring learning with errors problem (RLWE) with modulus $q^{d}$. Our reduction increases the LWE error rate $\alpha$ by a quadratic factor in the ring dimension $n$ and a square root in the module rank $d$ for power-of-two cyclotomics. Since, on the other hand, MLWE is at least as hard as RLWE, we conclude that the two problems are polynomial-time equivalent. As a corollary, we obtain that the RLWE instance described above is equivalent to solving lattice problems on module lattices. We also present a self reduction for RLWE in power-of-two cyclotomic rings that halves the dimension and squares the modulus while increasing the error rate by a similar factor as our MLWE to RLWE reduction. Our results suggest that when discussing hardness to drop the RLWE/MLWE distinction in favour of distinguishing problems by the module rank required to solve them.

Our reduction is an application of the main result from Classical Hardness of Learning with Errors in the context of MLWE. In its simplest form, that reduction proceeds from the observation that for $\mathbf{a}, \mathbf{s} \in \mathbb{Z}_{q}^{d}$ with $\mathbf{s}$ small it holds that

$q^{d-1} \cdot \langle{\mathbf{a},\mathbf{s}}\rangle \approx \left(\sum_{i=0}^{d-1} q^{i} \cdot a_{i}\right) \cdot \left(\sum_{i=0}^{d-1} q^{d-i-1} \cdot s_{i}\right) \bmod q^{d} = \tilde{a} \cdot \tilde{s} \bmod q^{d}.$

Thus, if there exists an efficient algorithm solving the problem in $\mathbb{Z}_{q^d}$, we can use it to solve the problem in $\mathbb{Z}_{q}^d$.

In our paper, we essentially show that we can replace integers mod $q$ resp. $q^d$ with the ring of integers $R$ of a Cyclotomic field (considered mod $q$ resp. $q^d$). That is, we get the analogous reduction from $R_{q}^d$ (MLWE) to $R_{q^d}$ (RLWE). The bulk of our paper is concerned with making sure that the resulting error distribution is sound. This part differs from the Classical Hardness paper since our target distribution is in $R$ rather than $\mathbb{Z}$.