## London-ish Lattice Coding & Crypto Meetings

Cong Ling and myself are starting London-ish Lattice Coding & Crypto Meetings. Please help us spread the word.

Lattice-based approaches are emerging as a common theme in modern cryptography and coding theory. In communications, they are an indispensable mathematical tool to construct powerful error-correction codes achieving the capacity of wireless channels. In cryptography, they are used to building lattice-based schemes with provable security, better asymptotic efficiency, resilience against quantum attacks and new functionalities such as fully homomorphic encryption.

We are setting up meetings on lattices in cryptography and coding in the London area. 1 These meetings are inspired by similar meetings held in Lyon 2 and are aimed at connecting the two communities in the UK with a common interest in lattices, with a long-term goal of building a synergy of the two fields.

The meetings will consist of several talks on related topics, with a format that will hopefully encourage interaction (e.g. longer than usual time slots).

## Tentative program

For details (as they become available) see website.

11:00 – 12:30: Achieving Channel Capacity with Lattice Codes Cong Ling

13:30 – 15:00: Post-Quantum Cryptography Nigel Smart

15:00 – 16:30: Lattice Coding with Applications to Compute-and-Forward Alister Burr

16:30 – 18:00: A Subfield Lattice Attack on Overstretched NTRU Assumptions Martin Albrecht

## Venue

Room 611
(Dennis Gabor Seminar Room)
Department of Electrical and Electronic Engineering
Imperial College London
South Kensington London
SW7 2AZ

## Registration

Everyone is welcome. Two caveats:

1. Speakers are told the audience is somewhat familiar with lattices.
2. Please send us an email at c.ling@imperial.ac.uk, so that the size of the room fits with the number of participants.

## Footnotes:

1

Our definition of London includes Egham, where Royal Holloway’s main campus is located.

## GSW13: 3rd Generation Homomorphic Encryption from Learning with Errors

This week our reading group studied Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based by Craig Gentry, Amit Sahai and Brent Waters: a 3rd generation fully homomorphic encryption scheme.

The paper is partly motivated by that multiplication in previous schemes was complicated or at least not natural. Let’s take the BGV scheme where ciphertexts are simply LWE samples $a_i, b_i = -\langle a_i, s\rangle + \mu_i \cdot \lceil q/2\rfloor + e_i$ for $a_i \in \mathbb{Z}_q^n$ and $b_i \in \mathbb{Z}_q$ with $\mu_i$ being the message bit $\in \{0,1\}$ and $e_i$ is some “small” error. Let’s write this as $c_i = (a_i, b_i) \in \mathbb{Z}_q^{n+1}$ because it simplifies some notation down the line. In this notation, multiplication can be accomplished by $c_1 \otimes c_2$ because $\langle c_1 \otimes c_2, s \otimes s\rangle \approx \mu_1 \cdot \mu_2$. However, we now need to map $s \otimes s$ back to $s$ using “relinearisation”, this is the “unnatural” step.

However, this is only unnatural in this particular representation. To see this, let’s rewrite $a_i, b_i$ as a linear multivariate polynomial $f_i = b_i - \sum_{j=1}^n a_{ij} \cdot x_j \in \mathbb{Z}_q[x_1,\dots,x_n]$. This polynomial evaluates to $\approx \mu$ on the secret $s = (s_1,\dots,s_n)$. Note that evaluating a polynomial on $s$ is the same as reducing it modulo the set of polynomials $G = (x_1 - s_1,\dots, x_n - s_n)$.

## Lecturer Position in the Information Security Group

My department is hiring a new lecturer whose interests are related to, or complement, current strengths of the ISG. If you have questions get in touch either as suggested below or — if that works better for you — with me.

Lecturer in Information Security

[…]

Applications are invited for the post of Lecturer in the Information Security Group at Royal Holloway, University of London

Applications are invited from researchers whose interests are related to, or complement, current strengths of the ISG. We are particularly interested in applicants who will be able to help drive forward research related to Internet of Things (IoT) security.

Applicants should have a Ph.D. in a relevant subject or equivalent, be a self-motivated researcher, and have a strong publication record. Applicants should be able to demonstrate an enthusiasm for teaching and communicating with diverse audiences, as well as show an awareness of contemporary issues relating to cyber security.

This is a full time and permanent post, with an intended start date of 1st September, 2016, although an earlier or slightly later start may be possible. This 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.

For an informal discussion about the post, please contact Prof. Keith Mayes on keith.mayes@rhul.ac.uk.

To view further details of this post and to apply please visit https://jobs.royalholloway.ac.uk/. The Human Resources Department can be contacted with queries by email at: recruitment@rhul.ac.uk or via telephone on: +44 (0)1784 41 4241.

Please quote the reference: 0216-068

Closing Date: Midnight, 1st April 2016

Interview Date: To be confirmed

We particularly welcome female applicants as they are under-represented at this level in the Department of Information Security within Royal Holloway, University of London.

## fplll days 1

We’ll have a first fplll coding sprint aka “fplll days” from June 20 to June 24 at ENS Lyon.

The idea of fplll days is inspired by and might follow the format of Sage Days which are semi-regularly organised by the SageMath community. The idea is simply to get a bunch of motivated developers in a room to work on code. Judging from experience in the SageMath community, lots of interesting projects get started and completed.

We intend to combine the coding sprint with the lattice meeting (to be confirmed), so we’d be looking at 3 days of coding plus 2 days of regular lattice meeting. We might organise one talk per coding day, to give people a reason to gather at a given time of the day, but the focus would be very much on working on fplll together.

If you’d like to attend, please send an e-mail to one of the maintainers e.g. me.

## Cysignals

If you’ve written a fair amount of Cython code in your time, chances are that you got frustrated by

1. buggy C/C++ code crashing your Python shell and
2. the fact that you cannot interrupt C/C++ functions.

For example, the following Cython code cannot be interrupted:

while True:
pass


On the other hand, if you have written Cython code in Sage, then you might have come across its nifty sig_on(), sig_off() and sig_check() macros which prevent crashes and allow your calls to C/C++ code to be interrupted. Sage had signal handling — crashes, interrupts — forever (see below).

Cysignals is Sage’s signal handling reborn as a stand-alone module, i.e. it allows to wrap C/C++ code blocks in sig_on() and sig_off() pairs which catch signals such as SIGSEGV. Using it is straight-forward. Simply add

include "cysignals/signals.pxi"


to each Cython module and then wrap long-running computations in sig_on() / sig_off() pairs or check for signals with sig_check(). See the cysignals documentation for details.

We have a first pre-release out. Pre-release because we haven’t switched Sage to the new, stand-alone code yet. Once this is done, we’ll publish version 1.0 since some version of this code has been in use on many different systems for at least decade.

## Writing (Crypto) Papers and Version Control

Academics write. Academics in my field also tend to write in groups of two to five people. Back in the dark days — which I’m told are not over for many researchers — this used to involve mailing LaTeX sources around, forgetting to attach the right file, “I take the editing token for file.tex” e-mails, questions like “Where is the most recent version of the draft?” and so on. In some cases, I’m told authors actually sat down together and did grammar fixes in a meeting. In a word, it was horrible.

Judging from anecdotal evidence, it is not that bad anymore. Many people now use some sort of revision control to write their papers, with either Subversion or Git being the tool of choice. However, my impression is that we don’t use the tools available to us to the extent we should. So let me try to make my case for a better practice of collaborative writing for (crypto) academics.

## Lucky Microseconds: A Timing Attack on Amazon’s s2n Implementation of TLS

Over the summer, Kenny Paterson and me spent some time looking at Amazon’s (Amazon Web Services – Labs to be precise) implementation of TLS. This implementation — called s2n — was released in June with the intent of providing a clean, easy to read, small implementation of a core subset of the TLS protocol.