Show HN: ArcaneVM – A Fully Homomorphically Encrypted Brainfuck Virtual Machine

github.com

7 pointsmax05633 comments

Very neat, I didn't know that it was possible to run completely general computation under homomorphic encryption.

> As a result, ArcaneVM is very very very slow.

Anyone know how the runtime complexity scales under homomorphic encryption?

It is indeed possible thanks to the logic gates built in to some of the schemes.

At least in ArcaneVM I think it's something like O(N^N) where N is the number of instructions in the program. The VM has no context on which instruction is supposed to be run when so every instruction needs to be "executed" at every step. It's absurdly slow and it doesn't help that the FHE algorithms themselves leave a lot to be desired when it comes to speed.

The level of evil here is inspiring.

Reply on news.ycombinator.com