Brainfreeze

Inspiration

Fully homomorphic computing is a hip new crypto trick that lets you compute on encrypted data. It's pretty wild, so I wanted to try something wild with it.

FHE has been getting getting super fast - boolean operations now only take tens of milliseconds, down from minutes or hours just a few years ago. Most applications of FHE still focus on computing known functions on static data, but it's fast enough now to host a real language all on its own. The function I'm homomophically evaluating is eval, and the data I'm operating on is code. "Brainfreeze" is what happens if you think about this too hard too long.

What it does

Brainfreeze is a fully-homomorphic runtime for the language https://en.wikipedia.org/wiki/Brainfuck.

How I built it

I wrote Python bindings for the TFHE C library for fast FHE. TFHE only exposes boolean operations on single bits at a time, so I wrote a framework for assembling and evaluating virtual homomorphic circuits in Python.

Then I wrote an ALU for simple 8-bit arithmetic, and a tiny CPU for dispatching on Brainfuck's 8 possible operations.

Does it work?

No! I didn't have time to finish the entire instruction set - only moving the data pointer (< and >) and incrementing and decrementing the data (+ and -) work right now :-/. It turns out that computers are complicated and I don't remember as much of 6.004 as I thought I did.

Could it work?

Definitely at small scales! But there are some severe limiting factors. FHE guarantees - mathematically - to leak absolutely no information about the data it's operation on, and that results in a sort of catastrophically exponential branching nightmare because the computer has to execute every possible instruction on every possible memory address during every single clock cycle, because it's not sure which is the "real" data or the "real" instruction and which is just noise.

Built With

• python
• tfhe