A basis for all cryptography

October 28, 2015 by Larry Hardesty, Massachusetts Institute of Technology

"Indistinguishability obfuscation" is a powerful concept that would yield provably secure versions of every cryptographic system we've ever developed and all those we've been unable to develop. But nobody knows how to put it into practice.

Last week, at the IEEE Symposium on Foundations of Computer Science, MIT researchers showed that the problem of indistinguishability obfuscation is, in fact, a variation on a different cryptographic problem, called efficient functional encryption. And while computer scientists don't know how to do efficient functional encryption, either, they believe that they're close—much closer than they thought they were to indistinguishability obfuscation.

"This thing has really been studied for a longer time than obfuscation, and we've had a very nice progression of results achieving better and better functional-encryption schemes," says Nir Bitansky, a postdoc in MIT's Computer Science and Artificial Intelligence Laboratory who wrote the conference paper together with Vinod Vaikuntanathan, an associate professor of electrical engineering and computer science. "People thought this is a small gap. Obfuscation—that's another dimension. It's much more powerful. There's a huge gap there. What we did was really narrow this gap. Now if you want to do obfuscation and get all of crypto, everything that you can imagine, from standard assumptions, all that you have to do is solve this very specific problem, making functional encryption just a little bit more efficient."

In computer science, "obfuscation" means disguising the operational details of a computer program so that it can't be reverse-engineered. Many obfuscation techniques have been proposed, and many have been broken.

So computer scientists began investigating the idea theoretically. The ideal obfuscation scheme would take the source code for a program and rewrite it so that it still yields a working program, but it is impossible to determine what operations it was executing.

Theorists quickly proved that ideal obfuscation would enable almost any cryptographic scheme that they could dream up. But almost as quickly, they proved that it was impossible: There's always a way to construct a program that can't be perfectly obfuscated.

Fuzzy details

So they began investigating less-stringent theoretical principles, one of which was indistinguishability obfuscation. Rather than requiring that an adversary have no idea what operations the program is executing, indistinguishability obfuscation requires only that the adversary be unable to determine which of two versions of an operation it's executing.

Most people recall from algebra, for instance, that a x (b + c) is the same thing as (a x b) + (a x c). For any given values, both expressions yield the same result, but they'd be executed differently on a computer. Indistinguishability obfuscation permits the adversary to determine that the program is performing one of those computations, but not which.

For years, the idea of indistinguishability obfuscation lay idle. But in the last few years, computer scientists have shown how to construct indistinguishability-obfuscation schemes from mathematical objects called multilinear maps. Remarkably, they also showed that even the weaker notion of indistinguishability obfuscation could yield all of cryptography.

But multilinear maps are not well understood, and it's not clear that any of the proposed techniques for building them will offer the security guarantees that indistinguishability obfuscation requires.

Tip of the iceberg

Functional encryption, on the other hand, has for decades been a popular research topic in cryptography. It's a method for performing some operation on an encrypted file, with an intelligible result, but without leaking any further information about the file's contents. It could, for instance, allow a server hosting a wealth of encrypted e-mails to decrypt just the senders' names, for search purposes.

With a standard encryption scheme, encryption time is proportional to the length of the file being encrypted. That's what Bitansky and Vaikuntanathan mean by "efficient." But the best functional-encryption schemes aren't quite that good: Their encryption efficiencies also include a factor proportional to the size of the result of the operation. If the operation were the decryption of the sender's name, that factor would be pretty small. But in principle, it could be much larger.

Bitansky acknowledges that researchers may have underestimated the difficulty of eliminating that extra factor. "It could be that our initial view of the world was false," he says. "Maybe this is not such an easy problem. Maybe this is the real gap, and it could take a very long time to solve. But I'm an optimist."

"Our current candidate constructions for IO [indistinguishability ] are all based on very new and not-well-understood assumptions that may very well be broken in the near future—and indeed, many of them have been broken," says Rafael Pass, an associate professor of at Cornell University. "Functional encryption is a significantly simpler-looking primitive, so this work opens a new avenue for getting secure constructions of IO."

"The technical approach is simple and beautiful, and I expect it will have lots of other applications," Pass adds.

Explore further: Computer scientists develop 'mathematical jigsaw puzzles' to encrypt software

More information: Indistinguishability Obfuscation from Functional Encryption. eprint.iacr.org/2015/163.pdf

Related Stories

The future of encryption

October 23, 2015

If you want to protect valuable information, wouldn't you keep it under lock and key?

Beefing up public-key encryption

February 18, 2013

Most financial transactions on the Internet are safeguarded by a cryptographic technique called public-key encryption. Where traditional encryption relies on a single secret key, shared by both sender and recipient, public-key ...

Recommended for you

Coffee-based colloids for direct solar absorption

March 22, 2019

Solar energy is one of the most promising resources to help reduce fossil fuel consumption and mitigate greenhouse gas emissions to power a sustainable future. Devices presently in use to convert solar energy into thermal ...

EPA adviser is promoting harmful ideas, scientists say

March 22, 2019

The Trump administration's reliance on industry-funded environmental specialists is again coming under fire, this time by researchers who say that Louis Anthony "Tony" Cox Jr., who leads a key Environmental Protection Agency ...

The taming of the light screw

March 22, 2019

DESY and MPSD scientists have created high-order harmonics from solids with controlled polarization states, taking advantage of both crystal symmetry and attosecond electronic dynamics. The newly demonstrated technique might ...

29 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

gkam
1.6 / 5 (7) Oct 28, 2015
Our national agancies measure their computers by the acre.

We have no chance against Big Brother.
Hyperfuzzy
3 / 5 (2) Oct 28, 2015
Would it not be simpler to define an AI that owns all objects. Communication allowed only with this object, any other object would be discarded. The object defined from a new type of byte, using a set of primes to define the total message that only the object may decode, i.e defined set of primes somewhere in the message that only one object has access and defined within the message. Existing code is buggy and built among a group of programmers which is never safe. The AI builds the code that only the AI can decode. Each communication checks the source and the sender and the route. The tunnel would actually be part of this object. Note that both the message and the operating code is secure. Package sent anywhere but only one defined receiver at a time, traced, unique, ... binary to new encoding unlike present objects, the byte string only make sense to a single enabled object. Even if stolen, each transmission must fit a given pattern of transmission, i.e. the object knows
Whydening Gyre
5 / 5 (2) Oct 28, 2015
Would it not be simpler to define an AI that owns all objects. ... Existing code is buggy and built among a group of programmers which is never safe. The AI builds the code that only the AI can decode. Each communication checks the source and the sender and the route. The tunnel would actually be part of this object. Note that both the message and the operating code is secure. Package sent anywhere but only one defined receiver at a time, traced, unique, ... binary to new encoding unlike present objects, the byte string only make sense to a single enabled object. Even if stolen, each transmission must fit a given pattern of transmission, i.e. the object knows.

This, and the article, was rather fuzzy to me. However, it kinda sounds like the way reality works...:-)
TheGhostofOtto1923
4 / 5 (8) Oct 28, 2015
Our national agancies measure their computers by the acre.

We have no chance against Big Brother.
-Why, when I was a 20yo grunt designing, fabriicating, and operating high-tech spy equipt directly for macnamara I learned all about computer acreage. This is before I went crazy with guilt for having killed all those gooks by proxy while I was spending my evenings in a cushy hotel in bangkok.

Ill tell ya, I certainly had my fill of killing by then.

But I forgot all about it when I got to watch an SR71 crash in the desert from the roof of a nearby hangar, where I just happened to be at the time, eating leftovers from my free dinner at the rotary courtesy my 'congressional airman of the month' award.

Woohoooo! What a spectacular life Ive led!

Hey where ya goin?
big_hairy_jimbo
4.3 / 5 (6) Oct 28, 2015
That sounds familiar Otto hehehehehe

Think I saw you, when I was a radio operator at Area 51, when they brought the Roswell UFO in. I just popped out of my office for a quick smoke, when they were removing the "beings" from the craft, think I saw you filming on a shoddy, shake and bake, movie camera, instead of a high class scientific grade camera. The Americans have had a thing about "illegal aliens" ever since!!!!!
antigoracle
4.2 / 5 (5) Oct 28, 2015
Our national agancies measure their computers by the acre.

We have no chance against Big Brother.
-Why, when I was a 20yo grunt designing, fabriicating, and operating high-tech spy equipt directly for macnamara I learned all about computer acreage. This is before I went crazy with guilt for having killed all those gooks by proxy while I was spending my evenings in a cushy hotel in bangkok.

Ill tell ya, I certainly had my fill of killing by then.

But I forgot all about it when I got to watch an SR71 crash in the desert from the roof of a nearby hangar, where I just happened to be at the time, eating leftovers from my free dinner at the rotary courtesy my 'congressional airman of the month' award.

Woohoooo! What a spectacular life Ive led!

Hey where ya goin?

Ha..ha..gskam couldn't have said it better.
No really. The guy's not just a liar, he's an even bigger idiot.
Bloodyorphan
not rated yet Oct 28, 2015
Randomize the IO channels to obfuscate them.
I.E. ... Don't encrypt/read the input in a linear fashion, encrypt the output file cursor offsets using random/key based primes based on the input cursor position.

It would surely make their lives a lot harder if not impossible.

You'd need to block read the input which would limit your randomization, but modern levels of memory allow for very large block sizes, most files would be read into memory in their entirety.
Hyperfuzzy
3 / 5 (2) Oct 29, 2015
Randomize the IO channels to obfuscate them.
I.E. ... Don't encrypt/read the input in a linear fashion, encrypt the output file cursor offsets using random/key based primes based on the input cursor position.

It would surely make their lives a lot harder if not impossible.

You'd need to block read the input which would limit your randomization, but modern levels of memory allow for very large block sizes, most files would be read into memory in their entirety.

That's been done.
gkam
1.6 / 5 (7) Oct 29, 2015
"Think I saw you, when I was a radio operator at Area 51"
-----------------------------------

Probably not. It is called Area 51 only by the goobers who think you pronounce the "l" in almond. It is a subsidiary airfield of the Air Force Flight Test Center, and when I was at Edwards we knew it as Groom Lake.
TheGhostofOtto1923
3.7 / 5 (6) Oct 29, 2015
"Think I saw you, when I was a radio operator at Area 51"
-----------------------------------

Probably not. It is called Area 51 only by the goobers who think you pronounce the "l" in almond. It is a subsidiary airfield of the Air Force Flight Test Center, and when I was at Edwards we knew it as Groom Lake.
Loser.
SuperThunder
2.6 / 5 (5) Oct 29, 2015
Like, say, you made a backup of all government secrets yearly, encoded it into DNA, and engineered it into kittens with latent food preferences based on the encryption key. The kittens would then go on to only like certain flavors of catfood that would act as a checksum on the "catfood preference encryption spectrum" to get the key to decode the DNA and retrieve the message. When set at large amongst kitten-kind, the checksum looks like any finicky cat amongst the set of all cats and all cat food flavors. Other cats would be constantly generating "gibberish" keys.
SuperThunder
3 / 5 (4) Oct 29, 2015
One star me if you like, I bet I could code this model before some your ridiculous ideas. The Kitten Encryption Model stands superior to the Communist AI model. I used words with non-salad meanings and everything.

...goobers who think you pronounce the "l" in almond.


Dammit, that's me. That's a real rhetorical hit to my Kitten Encryption Model.
Bloodyorphan
not rated yet Oct 29, 2015
You got an example for that Hyperfuzzy ??
Bloodyorphan
not rated yet Oct 29, 2015
Or maybe I should ask you what is obfuscated IO Hyperfuzzy ?
And why is it any issue according to this article ?
Hyperfuzzy
not rated yet Oct 29, 2015
Or maybe I should ask you what is obfuscated IO Hyperfuzzy ?
And why is it any issue according to this article ?

Cut the fiber bundle and reconnect. Add irrelevant stuff! Done! But I think it doesn't work!
Bloodyorphan
not rated yet Oct 29, 2015
So much for that discussion.
Bloodyorphan
5 / 5 (1) Oct 29, 2015
For the sake of anyone else reading these comments I'll go further and say, the problem is in the implementation of the prime engine, not the engine itself.

When using the prime engine you need to obfuscate the IO so a person using a debugger and brute force cannot rebuilt the algorithm using differential analysis.

Which means the output needs to be reversibly encrypted using an apparent randomized prime engine of it's own.

My method, would also require a compression pass before output.
gkam
1.7 / 5 (6) Oct 30, 2015
Too late.

We already paid for the machines and people of Big Brother to intrude on us and our private lives. No government will give up that power.

None.
Uncle Ira
3.4 / 5 (5) Oct 30, 2015
Too late.

We already paid for the machines and people of Big Brother to intrude on us and our private lives. No government will give up that power.

None.


You sound like one of those Tea-Party-Skippys that caused a run on aluminum wrap at the market for their anti-government hats.
gkam
1.7 / 5 (6) Oct 30, 2015
When you get experience in electronic reconnaissance let us know how you did it, Ira. Your inability to debate technical matters shows us you belong on Facebook or Twitter, not a science site.

Those with experience in this field know better.
Uncle Ira
3.4 / 5 (5) Oct 30, 2015
When you get experience in electronic reconnaissance let us know how you did it, Ira.


Well you got me there, I never did win a $25 gift certificate or free meal at the Rotary Club for my experience, non.

Your inability to debate technical matters shows us you belong on Facebook or Twitter, not a science site.


You mean technical debating like,,,,,,,

Too late.

We already paid for the machines and people of Big Brother to intrude on us and our private lives. No government will give up that power.

None.


Skippy, is that the technical stuff you are talking about?

Those with experience in this field know better.


Which is why you sound so silly with your "technical debating". Down here we call that sloganeering but you can call him "technical debating" if you feel better about it.

We already paid for the machines and people of Big Brother to intrude on us and our private lives.


You learn that in the technical debating school?
gkam
1.7 / 5 (6) Oct 30, 2015
"You learn that in the technical debating school?"
----------------------------------

No, Ira. I got it working in Electronic Reconnaissance, . . . look it up. You stay-at-home "patriots" have no real idea of how the military world works. You are completely ignorant of electronic reconnaissance. You have probably not worked with classified information or cryptographic devices from the NSA. All of your comments are personal, reflecting your ignorance of the technical topics.

Go away and play somewhere else.
TheGhostofOtto1923
3.7 / 5 (6) Oct 30, 2015
One star me if you like, I bet I could code this model before some your ridiculous ideas. The Kitten Encryption Model stands superior to the Communist AI model. I used words with non-salad meanings and everything.

...goobers who think you pronounce the "l" in almond.


Dammit, that's me. That's a real rhetorical hit to my Kitten Encryption Model.
My god george the psychopath is right...
https://newsroom....re-back/

For once massive self-delusion proves useful-
Estevan57
4.2 / 5 (5) Oct 30, 2015
"All of your comments are personal, reflecting your ignorance of the technical topics." - gkam

Interesting comment considering your own posts start with "Our" , "we", "you", and "I".

What could you possibly know that is pertinent to modern cryptology? You have been out of the service for 47 years.

http://dictionary...h/almond

It is pronounced both ways, dumbass.
gkam
1.8 / 5 (5) Oct 30, 2015
Made you look.

You were really, really hoping I would be wrong.

I was never "in" cryptography, we just used their machines. I stayed away from the code stuff.
Estevan57
4.2 / 5 (5) Oct 31, 2015
Uh, actually you were wrong. But then again how could I possibly pit your magnificence against the humble people of the Cambridge dictionary.
Dumbass.

gkam
1.6 / 5 (7) Oct 31, 2015
Uh,actually, I was correct. My dictionary lists the correct pronunciation first,and the also-used second. Guess which one is first in my dictionary?

You folk who think almonds come from factories have to go to the growers to get the real pronunciation, not the ad executives in New York City. They also pronounce turbine as "tur-byne", while professionals say "tur-bin". Which one are you?

[ah-muh nd, am-uh nd; spelling pronunciation al-muh nd]

Examples
Word Origin

noun
1.
the nutlike kernel of the fruit of either of two trees, Prunus dulcis (sweet almond) or P. dulcis amara (bitter almond) which grow in warm temperate regions.
2.
the tree itself.
3.
a delicate, pale tan.
4.
anything shaped like an almond, especially an ornament.
gkam
1.6 / 5 (7) Oct 31, 2015
It was my old dictionary which included the pronunciation of the "L". This new one does not even include your version.

Who is the D(Estevan)ss?
Estevan57
4.2 / 5 (5) Oct 31, 2015
Have you considered that growers pronounce it differently than you do? Or most Americans for that matter.

So you are saying that the Almond Board of California pronounces it incorrectly?
https://www.youtu...oardofCA

The site keeps cutting out my 5 links that show pronunciation, but the one above has 25 sites with the American version.

So now you are an expert on agriculture, but pronounce your local major cash crop incorrectly. Too damn funny. Dumbass.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.