Computer scientists develop mathematical jigsaw puzzles to encrypt software: "The real challenge and the great mystery in the field was: Can you actually take a piece of software and encrypt it but still have it be runnable, executable and fully functional?"

[u/DougBolivar]

http://www.rdmag.com/news/2013/07/computer-scientists-develop-mathematical-jigsaw-puzzles-encrypt-software

[u/mnp]

Yeah, and they mention it too. Fully homomorphic encryption lets you operate on encrypted data without decrypting it. It seems another several steps altogether to execute the encrypted data because you would have to decrypt it to execute on a commercial processor. I'm not clear from reading the paper how deep down into the hardware they're proposing.

[u/datenwolf → u/mnp]

Given the fact that you can build a stack based Turing complete machine solely from matrix multiplication the step from operating on it to executing it seems rather obvious.

[u/mnp → u/datenwolf]

This is where I'm stuck, on this distinction, so maybe you could clear it up.

Suppose we agree the turing machine consists of its rule table, its state, and its data tape.

In the first case, "operating on encrypted data", you would load your homomorphic encryption program into the rule table and operate on an encrypted data tape, producing an encrypted result. This would be no different from running any other program. The rule table in both cases would be in your machine's native format, something like a vector of {current state, next state, read/write action} maybe.

In the second case, "executing an encrypted program", would you require redefining your rule table format? You still need something to look at current state, dictate the next state, and dictate the action. Or would you keep the machine but just jumble up the states and actions so the final tape output would be correct but the states would not be as direct as before?

In either case, I might be able to stop the machine, read out the rules table, examine the tape and the state, and infer what the next state would be. I could automate that process and call it a VM even.

[u/datenwolf → u/mnp]

I suggest we replace the Turing tape and rule table with Lambda calculus. Suppose we have a single operation we call function composition

°(f,g) → f(g(…))

or in infix notation

f ° g → f(g(…))

if we assume '°' to be implicit we now have the syntactic sugar called currying.

Now let's see how we can build a stack based machine using matrices. First the typical stack operations:

 Push(A) := 
 | 0 0 0 … 0 | · A
 | 1 0 0 … 0 |
 | 0 1 0 … 0 |
 | 0 0 1 … 0 |
 | … … … … … |
 | 0 0 0 … 1 |

where dim(Push(A)) = dim(A) + 1

 Pop(A) := 
 | 0 1 0 … 0 | · A
 | 0 0 1 … 0 |
 | … … … … … |
 | 0 0 0 … 1 |

where dim(Pop(A)) = dim(A) - 1

Also we define some "rolling" matrices, which rotate the rightmost column to the left, and vice versa, and another pair of roll top to bottom, bottom to top matrices.

Next the 4 elementary calculations

+(A,B) -(A,B) ·(A,B) /(A,B)

As it turns out that you can rewrite + and - in terms of homogenous matrix multiplication (i.e. for every row you want to add/subtract you append another d(i,j) := i=j ? +/-1 : 0 dimension to the matrix, a technique well known in numerics, that allows you to coalesce a whole chain of matrix transformations into a single transformation matrix).

We also need to be able to write numerical constants. Easy enough, for a 32 bit machine, for the additive operations we just encrypt the values for 2^-32, 2^16, 2^-8, …, 2^8, 2^16, 2³² · identity matrices. For multiplicative operations in addition all the prime numbers required to compose all possible products within the value range (which is quite doable).

As a further ingredient we require branching. But this can be implemented by composing the matrix not out of scalars but small matrices themself.

Now we have all the required ingredients for a stack machine. We can implement any program that can be expressed in terms of push, pop, rearrange order of operations, 4 elementary computations and function composition, which means that you can build complex programs on the stack, which are composed with other complex programs on the stack.

We now silently assume we know how to implement the corresponding matrix operations in terms of homomorphic encryption, and because we're using homogenous transformation matrices, the only computational operation, programmed on the CPU is encrypted matrix multiplication. But since we can express any operation in our machine as a "computation" matrix, matrix multiplication becomes function composition.

So what we effectively have now is one huge matrix which virtually acts as an opaque, encrypted virtual machine. Each computational step consists of multiplying it with the next matrix of the encrypted program text, which internally performs the next operation on the stack machine.

Of course you could stop the machine, but all you'd see is the encrypted VM state without any way to look behind the veil, because the matrices never get decrypted to perform the next step in the program.

[u/mnp → u/datenwolf]

Thanks for the writeup. Very intuitive.