A couple of years ago, I was at a cryptography conference for work. There were folks working on all kinds of exciting things, but I found myself in a long conversation with a fellow compiler engineer that happened to be working on systems for fully homomorphic encryption (FHE). While the term is rather fancy, the idea is pretty simple to understand, which is why it’s one of those things that I turn over and over again in my head from time to time. Typically when using encryption, one can translate data to and from an encrypted form, so that it’s hard for somebody else to learn what the original data is just by looking at its encrypted version. Unfortunately, because the encryption obscures the data, you can’t use that data in any way without first decrypting it. The whole idea of homomorphic encryption is to be able to do computations on this data in its encrypted form, with the idea being that even somebody you want to keep a secret from can do computations for you on your private data, and learn nothing about your secrets, or even the results of the computations they’re doing for you in the process. Seems like a neat idea, but it feels a bit far-fetched, right? Well, this is possible today, and its getting more and more practical all the time thanks to hard-working cryptographers and compiler engineers.

This post is a continuation of my last post on The Problem of Tag where I introduced a marble machine called a tag system, and the possible behaviors they can have, namely halting, looping, and diverging. I also talked about the problem of tag, which asks whether a particular tag system operating on a particular starting sequence eventually halts, loops, or diverges. I had also alluded to the fact that tag systems are Turing complete, which is a really important “no-go” theorem when discussing the problem of tag – in particular, it means that there is no fully general solution to the problem. That is, there’s no algorithm that always runs in a finite amount of time that correctly decides which behavior a particular tag system has on a particular string. I’m not going to actually prove this result here, but considering a very naive approach gives some intuition of why this might be true. Consider an algorithm that simulates the running of the tag system:

Sometime last year, I was reading up on a longstanding open math problem that turns out to have a really deep connection with computability theory [1]. For the unfamiliar reader, this is a corner of theoretical computer science that deals with “math computers” — basically, defining mathematical objects that can do computations, and proving mathematical theorems about them. These math computers are more formally called models of computation, and there are some really common ones like state machines and context free grammars that every programmer probably encounters at some point in their career. I’m probably biased though, since I’m a compiler engineer during standard working hours, so these are kind of my bread and butter.

Lately, I’ve been reminiscing about the physics simulations I used to make back in the day. A lot of them were kind of crude, but I’m older and hopefully a bit wiser now, so hopefully I can do it a bit better this time around. Revisiting my old nerdy projects take me back to when I was first grappling with a lot of ideas that would come up over and over again in my education — I’ve heard it said that studying physics is learning a series of progressively smaller lies, and true to form by the time I finished my undergrad physics major I’d studied the same sorts of systems a bunch of times in progressively greater detail and with progressively fancier math. One such system is a gas in a box.

I recently read a fun paper Reed Solomon Codes over the Circle Group that uses circle groups to perform an important kind of error correcting code in finite fields where it’s otherwise difficult. If that sounds like gibberish to you, be not afeard! That’s not really what I’m here to talk about! While quite tangential to the contents of the paper, I was intrigued by the idea of translating circle groups into the context of finite fields, and wondered if there was a good way to understand these groups spatially, given how weird finite fields tend to be. Hence the title of the blog post!