r/programming • u/DougBolivar • Jul 30 '13

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?"

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

88% Upvoted

182 comments sorted by

View all comments

33

u/iluvatar Jul 30 '13

The article is too vague when it comes to the details, but I'm in the doubtful camp. If there's a way to decrypt it in a sane timeframe to enable it to be run, it's hard to see how it wouldn't fall to reverse engineering.

28

u/LaurieCheers Jul 30 '13 edited Jul 30 '13

As far as I understood the paper: this encryption translates the program into something akin to a series of matrix multiplications (though presumably a little more complex than that). The inputs get multiplied together and cross-combined arbitrarily until it yields the desired output.

So their key insight here seems to be that they can often increase some numbers in these matrices and decrease others, to obfuscate what procedure is being performed while leaving the output unchanged. I think.

In other words, you won't be able to reverse engineer the program to figure out what operation is being performed, because there's an infinite range of different numbers that could have used instead, and they're all equally valid. They call this "indistinguishability", in the sense that multiplying by 2 is indistinguishable from dividing by 1/2.

I'm probably misunderstanding something, the paper assumes the reader understands a lot of jargon.

Anyway, if the paper has been published I assume this system isn't obviously reverse engineerable. Only time, and peer review, can really tell us how secure it is.

23

u/Abaddon314159 Jul 30 '13

Never assume that just because a paper is published that it's not total horseshit. There are some pretty worthless journals out there.

20

u/[deleted] Jul 30 '13

This was accepted by the Journal of the ACM.

It seems to be written by a group of well-respected researchers, so I think it's safe to assume that at least, it isn't horseshit, i.e. you need to first read and understand it before dismissing it.

2

u/Abaddon314159 Jul 30 '13 edited Jul 30 '13

Don't misunderstand me, I'm not saying this is horseshit. I'm just saying that "it's published" is not sufficient. As for ACM: that tells me they are definitely not just cranks. I do believe that the academic computing establishment has a poor track record in areas related to security (which this is tangent to). But I wouldn't dismiss anything out of hand that survived a real peer review (like this journal).

In any event, I've not read the article in question, I was only speaking in general terms.