Damn Cool Algorithms, Part 2: Secure permutations with block ciphers

It's been too long since I blogged about anything much, and way too long since I posted the first Damn Cool Algorithms post, which I promised would be a series. So here's part 2.

To start, I'm assuming you know what a permutation is - basically a shuffling of a sequence of items in a particular order. A permutation of the range 1-10, for example, is {5,2,1,6,8,4,3,9,7,10}. A secure permutation is one in which an attacker, given any subset of the permutation, cannot determine the order of any other elements. A simple example of this would be to take a cryptographically secure pseudo-random number generator, seed it with a secret key, and use it to shuffle your sequence.

What if you want to generate a really, really big permutation - one so big precomputing and storing it isn't practical or desirable? Furthermore, what if you want it to be a secure permutation? There's a really neat trick we can pull with block ciphers that allows us to generate a secure permutation over any range of numbers without first having to precompute it.

A block cipher, for anyone that ...

Apartments in Dublin

Yesterday morning, someone from the relocation company came by to pick me up and take me on a bit of a tour of Dublin, with an emphasis on the sort of neighbourhoods I might like to live in. There's a fairly wide variety of housing available here in Dublin, though if you want a garden you're more or less out of luck unless you're particularly wealthy.

One particular place that impressed me, however, were the apartments at the Gasworks - the same facility the Google offices are on. There's a lot of apartment buildings there, all fairly nice, but the really impressive one is the old Gasometer. Basically, they took a gasometer, demolished everything but the frame, then built an apartment building inside it. It's pretty big:

What's really impressive, though, is what they've done inside. The building is shaped like a torus, with a large open area in the middle. They've planted a large tree in the center, and the end effect is that you have almost a sanctuary-type environment inside. My pictures really don't do it justice, especially with the overcast weather we're having, but here they are anyway ...

First week at Google Dublin

I just finished my first week at Google Dublin. It's been a blast.

The first couple of days of general induction are a bit slow, but once you meet your team, stuff really speeds up. The sheer amount of information I've been exposed to and had to learn this week is astounding.

I'm really looking forward to next week, not to mention going down to Mountain View for more training.

Leaving NZ, again.

So, first a quick update on everything I've been leaving out on this blog: Waaaay back in February, I was offered a (phone) job interview with Google. Things proceeded well, and a while ago, I was made an offer of a job as a Site Reliability Engineer in Dublin, which I accepted. I resigned from my position in NZ, sorted out stuff for moving, and hopped on a plane.

I'm writing this entry from a Dublin internet cafe. I arrived here in Ireland mere hours ago, and I'm still exhausted and jetlagged, but I have to do something with the time until I can let myself try and sleep. Hence the sudden update.

First, for those wondering, Hayley, the love if my life, is, alas, still back in NZ for the moment. At the moment it looks like she'll be joining me up here in about 6 weeks.

When I arrived in Dublin, I was met by someone hired by Google, who drove me to my temporary accommodations provided for me for the next 30 days. Light commentary on the city was provided. Upon reaching my accommodation, I was handed off to someone else, who gave ...