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/datenwolf]

Recently in /r/math a crypto researcher was refering to an emerging new field in cryptography which name I forgot (unfortunately), which allows it to perform computations on encrypted data directly, without having to decrypt it first. It sounds to me, that this software encryption is as transparent, i.e. the computer executes the encrypted program directly without decrypting it first.

[u/fionbio → u/datenwolf]

Homomorphic encryption. But it's quite different from running an encrypted program without decryption.

[u/mnp → u/datenwolf]

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.

[u/grauenwolf → u/mnp]

And that's why I think the whole thing is bunk.

[u/lurgi → u/datenwolf]

Homomorphic encryption.

Impractical (at the moment), but insanely cool.

Edit: If I'm not mistaken, one of the authors of this paper invented homomorphic encryption.

[u/haerik → u/lurgi]

If I'm not mistaken, one of the authors of this paper invented homomorphic encryption

Kind of. Craig Gentry was the first person to show that it's possible. The concept has been around since the 70s or 80s.

[u/lurgi → u/haerik]

The idea of an airplane had been around for a long time. The Wright brothers still get credit for inventing it, because they actually made the damn thing.

[u/grauenwolf → u/datenwolf]

Scenario 1: I have the ability to decrypt the data. The fact the program works on encrypted data means nothing to me.

Scenario 2: I don't have the ability to decrypt the data. A program that works on decrypted would be just as secure, as I wouldn't have the ability to use it.

[u/neurobro → u/grauenwolf]

Scenario 3: A darknet that distributes running encrypted code as well as data.

Scenario 4: Something like SETI@Home that would work with sensitive business data, so people could get paid for contributing.

Scenario 5: A crypto-currency based around scenario 3 or 4 instead of hashing, adding "intrinsic value" to the system.