I've been studying functional encryption. I recently read that a multi-input functional encryption (MIFE) implies indistinguishability obfuscation (IO).
Can someone please brief me: what is indistinguishability obfuscation (IO), and are its implications for crypto?
Here is a very interesting example quoted in GGH+13 (PDF).
Software developers will often want to release a demo or restricted use version of their software that limits the features that are available in a full version. In some cases a commercial software developer will do this to demonstrate their product; in other cases the developer will want to make multiple tiers of a product with different price points. In other domains, the software might be given to a partner that is only partially trusted and the developer only wants to release the features needed for the task.
Ideally, a developer could create a downgraded version of software simply by starting with the full version and then turning off certain features at the interface level -- requiring minimal additional effort. However, if this is all that is done, it could be easy for an attacker to bypass these controls and gain access to the full version or the code behind it. The other alternative is for a software development team to carefully excise all unused functionality from the core of the software. Removing functionality can become a very time consuming task that could itself lead to the introduction of software bugs. In addition, in many applications it might be unclear what can and cannot remain for a restricted use version.
One immediate solution is for a developer to restrict the use at the interface level and then release an obfuscated version of the program. For this application indistinguishability obfuscation suffices, since by definition a version restricted in the interface is indistinguishable from an obfuscated program with equivalent behavior that has its smarts removed at the start.
Inthe same paper they have also proved that Indistinguishability Obfuscation implies functional encryption.
A very interesting paper [CLTV14] (Obfuscation of probabilistic circuits and application) gives a construction of fully Homomorphic Encryption using sub-exponentially secure Io and PDF. That too without any circular security assumption.
Program Obfuscation is a method to scramble the program code such that it becomes unintelligible but preserves the program's functionality. The notion of indistinguishability obfuscation was proposed in [BGI+01]. Actually they first consider another notion which is called virtual black box obfuscation (VBB Obfuscation). However, they showed that VBB Obfuscation is impossible, so they proposed the concept of indistinguishability obfuscation (IO).
In 2013, [GGH+13] proposed the first candidate IO from assumptions over multilinear maps. After that, a number of its applications were proposed. For example, deniable encryption [SW14], witness encryption [GGSW13] and round optimal (2-round) MPC [GGSR13] (Actually, just review the list of IACR preprint after the appearance of the first candidate IO, you could find a great number of paper discussing applications of IO).
Currently the central problem is how to build IO from standard mathematical assumptions (e.g., LWE and Bilinear Maps). The most most recent breakthrough was made by Rachel Lin et.al. from last year through this year [Lin16][LV16][Lin16][AS16][LT17].
This Security.SE answer should be read before the answer posted here. The following block quote and FPS example are taken from the answer linked.
Functional encryption is about providing a computable circuit (obfuscated with IO) which receives as input encrypted versions of some value x, and returns F(x) for some function F, without revealing anything else about x. The authors show how they can do that for any function F which can be encoded as a circuit, and the resulting obfuscated circuit is "polynomially-sized" with regards to the original unobfuscated circuit implementing F.
The quote above, and following example, are from Tom "The Bear." He states a good example is for a FPS (first-person shooter) video game that could prevent players from cheating. The gist of his example is that each player's system only gets data from the server, rather than being able to read from an opponent's device.
The most obvious theoretical comparison is to homomorphic encryption. This involves performing computations on encrypted data without decryption first. An additional comparison is in formal methods for software engineering, such as the HACMS project.
Drawing from DARPA's HACMS project, it's possible to segment software, and therefore functions, such that control of one component doesn't allow any control of any other component.
If you only look at these two features, that of homomorphic encryption in addition to the HACMS project you could argue that IO is practical. But when you factor in everything else, detailed by Tom in the first link of this answer, it doesn't seem very likely for the foreseeable future.
The upshot is the potential for homomorphic encryption with added safeguards against attacks such as feng shui based on rowhammer. Looking more to the future, we may see self-driving cars communicating via a cloud accessed based on proximity. Essentially each area of a road communicates with cars in that area, while performing computations to assist the self-driving cars' navigation. If IO is optimized enough to be practical, this would help secure everyone on their daily commutes.
For a better list of examples, click the HACMS link above.
You have some mathematical function.
You have some class of circuits all computing that same function.
Indistinguishability obfuscation algorithm, when given any of these circuits, will randomly transform it into any other of these circuits, with the same probability.
Informally, obfuscating a program is the process of concealing what the program is doing while at the same time preserving its functionality. Among other things this serves to protect against code tampering and reverse engineering. I found a very good example here
Obfuscation has plenty of applications. One important application would be construction of FE and FHE . Other few are constrcution of witness encryption and a NIZK [CLTV14]
