Computer Scientists Develop ‘Mathematical Jigsaw Puzzles’ to Encrypt Software
From the post:
UCLA computer science professor Amit Sahai and a team of researchers have designed a system to encrypt software so that it only allows someone to use a program as intended while preventing any deciphering of the code behind it. This is known in computer science as “software obfuscation,” and it is the first time it has been accomplished.
It was the line “…and this is the first time it has been accomplished.” that caught my attention.
I could name several popular scripting languages, at the expense of starting a flame war, that would qualify as “software obfuscation.” 😉
Further from the post:
According to Sahai, previously developed techniques for obfuscation presented only a “speed bump,” forcing an attacker to spend some effort, perhaps a few days, trying to reverse-engineer the software. The new system, he said, puts up an “iron wall,” making it impossible for an adversary to reverse-engineer the software without solving mathematical problems that take hundreds of years to work out on today’s computers — a game-change in the field of cryptography.
The researchers said their mathematical obfuscation mechanism can be used to protect intellectual property by preventing the theft of new algorithms and by hiding the vulnerability a software patch is designed to repair when the patch is distributed.
“You write your software in a nice, reasonable, human-understandable way and then feed that software to our system,” Sahai said. “It will output this mathematically transformed piece of software that would be equivalent in functionality, but when you look at it, you would have no idea what it’s doing.”
The key to this successful obfuscation mechanism is a new type of “multilinear jigsaw puzzle.” Through this mechanism, attempts to find out why and how the software works will be thwarted with only a nonsensical jumble of numbers.
The paper has this title: Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits by Sanjam Garg and Craig Gentry and Shai Halevi and Mariana Raykova and Amit Sahai and Brent Waters.
Abstract:
In this work, we study indistinguishability obfuscation and functional encryption for general circuits:
Indistinguishability obfuscation requires that given any two equivalent circuits C_0 and C_1 of similar size, the obfuscations of C_0 and C_1 should be computationally indistinguishable.
In functional encryption, ciphertexts encrypt inputs x and keys are issued for circuits C. Using the key SK_C to decrypt a ciphertext CT_x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually.
We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps:
- We describe a candidate construction for indistinguishability obfuscation for NC1 circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles.
- We show how to use indistinguishability obfuscation for NC1 together with Fully Homomorphic Encryption (with decryption in NC1) to achieve indistinguishability obfuscation for all circuits.
- Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.
When a paper has a table of contents following the abstract, you know it isn’t a short paper. Forty-three (43) pages counting the supplemental materials. Most of it very heavy sledding.
I think this paper has important implications for sharing topic map based data.
In general as with other data but especially with regard to subject identity and merging rules.
It may well be the case that a subject of interest to you exists in a topic map but if you can’t access its subject identity sufficient to create merging, it will not exist for you.
One can even imagine that a subject may be accessible for screen display but not for copying to a “Snowden drive.” 😉
BTW, I have downloaded a copy of the paper. Suggest you do the same.
Just in case it goes missing several years from now when government security agencies realize its potential.
[…] Another Word For It Patrick Durusau on Topic Maps and Semantic Diversity « Subject Identity Obfuscation? […]
Pingback by Cryptology ePrint Archive « Another Word For It — July 30, 2013 @ 10:30 am