Modulo Errors

I’m back from the Fields Institute in Toronto, where I spoke at the above workshop, on my usual topic of cyclotomic and 4-cyclotomic matrices/graphs. During the talk I described my conjecture that a graph is maximal cyclotomic if-and-only if it’s 4-cyclotomic, and after an hour at the blackboards with James McKee I now have a potential approach for proving that. So although I don’t think my talk went especially well, it’s had the desired effect!

You can find my slides here, and an audio recording may become available in the future- the conference was held in Toronto and Vancouver via videoconference (which worked well) so hopefully all the talks will be archived online.

Update 24/x/09: Audio of all talks at Fields (hence, including mine) can now be found on their website.

Tomorrow, in what seems to be becoming an annual tradition, I’ll be giving a talk on cryptography at the Geometry Club. Since it’ll be a talk-and-chalk style seminar, I don’t have any slides to make available, but many of the topics I’ll be discussing have appeared earlier on this blog or everything2. In particular, I’m planning to include:

• A brief overview of public-key cryptography: my notes from last year’s talk cover technical details in the context of (EC)DLP, or there’s this friendlier article on Diffie-Hellman key exchange and man-in-the-middle attacks.
• The problems of Authentication and Mutual Authentication at a protocol level.
• The undecidability of the secrecy problem via Post’s Correspondence Problem.
• Lattice-based cryptography- which hopefully I can summarise in a later post.

This week I’ve been at the rather swish Alan Turing building in Manchester for the MAGIC Postgraduate Conference and LMS Northern Regional Meeting.

I spoke at the former, on the subject of Integer Matrices with Constrained Eigenvalues. Here are my slides: it’s a fairly breezy 15 minute overview of the problem (which integer symmetric matrices have all eigenvalues in [-2,2]?) and its solution, covering Mahler measure, cyclotomic matrices, interlacing, and charged signed graphs. For further reading, here is the paper by McKee and Smyth (my supervisor) with their proof of the presented classification; also by Smyth is a survey on Mahler Measure of 1-variable polynomials.

In my own work I’ve generalised the idea of cyclotomicity (all eigenvalues in [-2,2]) to Hermitian matrices with algebraic integer entries from imaginary quadratic extension fields. I think I have a complete classification of these, with an alternative proof of the above rational integer case as a subcase. The results at least will hoepfully appear here at some point, although for the proofs you’ll probably have to wait for my thesis.

Yesterday I gave another postgraduate colloquium, on the basics of public key cryptography. The slideshow I used is here [pdf], although obviously it’s missing the narrative to go with it. The first part, on sharing secret colours, was lifted from the talk described here, although I discussed the discrete logarithm problem in group-theoretic terms this time.

On Friday I gave a geometry club seminar, speaking about some of the computational aspects of discrete-logarithm cryptography in general and as implemented for elliptic curves. My notes supplement rather than completely describe the talk, being heavier on the formalities and lighter on the narrative.

The topics covered are: Diffie-Hellman and one-way functions for key exchange; the generic Discrete Logarithm Problem and BSGS algorithm; scalar multiplication- addition chains, fast exponentiation, m-ary methods and windowing; group law implementations, Side-channel attacks and the Edwards form.

I’ve discussed several of these ideas elsewhere on this blog, as well as the cryptanalysis ideas I mentioned on the day but which are not in the notes. I also refered to a recent real-world example of a side-channel attack; see this story from The Register for details.

Today I gave the first of this year’s postgraduate colloquia series, The Mathematics of Being Nice- cooperation in the Prisoner’s Dilemma. You can grab the slideshow as pdf here; since the potential audience was quite broad (and I’m no expert) I think it’s fairly light technically, and thus hopefully more accessible than many of my posts here. It’s essentially the talk version of my article for iSquared, so you should invest in a copy of that if you want something that’s more fleshed out!

Tomorrow I give my first year presentation, which determines whether I’m allowed to continue my studies. At 20-30 minutes, it’s a rather condensed version of my recent geometry club talk on the point counting problem, although this time I’m skipping more quickly through the fundamentals so that I can discuss some of the algorithms in depth, and taking a (hopefully) clearer route.

Both the report itself and the OHP slides version are available (pdf). Content covered: hyperelliptic curves, points, divisors, mumford polynomials and the Picard group/Jacobian; the discrete logarithm problem; explicit group law computation; characteristic polynomial of Frobenius and Weil theorems/interval; group-theoretic approaches; Schoof’s algorithm, SEA in genus 1, genus 2 hybrid algorithms.

Today I spoke at the Geometry Club about the use of hyperelliptic curves in public key cryptography. You can find my slides here, although they were supplemented by some boardwork that you’ll have to figure out from my other postings!