Just adding a simpler explanation of
Functional Encryption Fully Homomorphic Encryption before proceeding to Functional Encryption and Indistinguishability Obfuscation as it is easier to explain that way. Taken mainly from http://crypto.stanford.edu/craig/easy-fhe.pdf The above is a paper by Craig Gentry (one of the pioneers in this field), and he gives a very easy to follow Alice example with some math.
Fully Homomorphic Encryption
Excluding the math
Functional Encryption Fully Homomorphic Encryption is something like this:
Lets say there is some Unencrypted Data - UD. There is an encryption of the Unencrypted Data called Encrypted Data - ED. We perform some analysis/manipulations (lets call the analysis a function F) on UD get some unencrypted output - UO.
The question posed/answered by Functional Encryption is - Can one run the analysis/manipulation function F, on the encrypted data ED, and get a corresponding encrypted output - EO, SUCH THAT if one decrypts EO, one can get the unencrypted output defined above - UO?
A simple diagram (process 1 should give the same output as process 2):
Unencrypted Data UD -> passed through some analysis function F -> gives Unencrypted Output UO.
a) Unencrypted Data UD -> encryption algorithm -> Encrypted Data ED [This process is on a trusted environment]
b) Transfer ED anywhere. -> Perform analysis function F on ED -> Get EO (Encrypted Output). [Can be done anywhere including a non trusted environment, say the cloud]
c) Get EO. -> decryption algorithm -> Get UO (Unencrypted Output) [On a trusted environment]
A working scheme at the bit level just needs to support ADD, SUBTRACT and MULTIPLY as explained in the above paper. And if it works at the bit level, it can be generally extended to all computation.
As an extension, given general recursion, one might even encrypt the analysis function F, such that even what analysis is being performed is not known to untrusted environments.
Answer to the comment below, since I don't have enough reputation to comment!
Your question did strike me, while writing the above answer. Possibly the above example is bit too simple and the concept a bit abstract.
Generally speaking there is a one-to-one correspondence between plain text and encrypted text to ensure decryption.
So lets say one wanted to search the data for the text "blue". Continuing with the example above, lets say the text "blue" is encrypted to "xChd". So the functioning searching on encrypted data will search for "xChd" instead of "blue". Algorithmically speaking the functions are the same i.e. "search for some text". Individual instances of the function will search for a different phrase, depending on the context. But again I say this is too much of a high level view.
At the bit level one only has ADD (commonly known as OR), SUBTRACT (NOT and OR) and MULTIPLY (AND) - this is as described in the paper. Otherwise at the bit level we only have 3 fundamental operations - AND, OR and NOT.
Typical encryption in today's world involves generating a unique but random stream of bits which are XORed with the plain text to give encrypted text. In decryption encrypted text is XORed with the cipher to give plain text.
So what the author (Craig) and/or others are trying to achieve at the bit level is:
[AND,OR,NOT or any combination of these fundamental operations] on unencrypted input(s) give some unencrypted output(s).
Is it possible to develop an encryption scheme SUCH THAT [AND,OR,NOT or any combination of these fundamental operations] on encrypted input(s) give some encrypted output(s) that can be decrypted to give output identical to the unencrypted output(s).
In literature Fully Homomorphic Encryption is described as follows with a so called Evaluate function.
Assume the following:
a. f is a function reduced to a boolean circuit C (i.e. consists of only gates and various inputs and outputs)
b. Key pair - pk is the public key, sk is the secret key
c. UI and UO are unencrypted inputs and outputs respectively
d. EI and EO are encrypted inputs and outputs respectively.
Then FHE (Fully Homomorphic Encryption) is described as
Evaluate(pk,C,EI) gives us EO such that Decrypt(sk, EO) is identical to running circuit C on UI.
So to answer your question in FHE the function f or the circuit C are the same, because the logic or algo has to be the same. The Evaluate function requires the public key so that it can translate any unencrypted inputs/intermediates in the circuit C to the encrypted form (for example if one wanted to search for "blue", the function f may have "blue" embedded somewhere in the code, but the encrypted data would need to be searched for "xChd". Again this is a very high level example and doesn't fully correspond to the bit level, because at the bit level the Evaluate function is required to be independent of the circuit C. Further at the bit level functions are defined as having a single output - the basic gates AND, OR and NOT are all single output. The normal multi-input multi-output functions that we talk about in algorithms and high level language programs are all built from basic gates. Here the high-level analogy fails, and the public key is required by the Evaluate function. Fitting in with the asymmetric encryption public/private key model - as in I send you data encrypted with my private key and a function and my public key, FHE can be summarized as - You can compute the function on my encrypted data using my public key and send me the encrypted output).
Moving on to Functional Encryption. FE (Functional Encryption) is not defined very simply or clearly. In fact there an entire research paper dedicated to formalizing a definition of FE - http://eprint.iacr.org/2010/543.pdf
FE sounds like a bit of magic - a bit like when someone is introduced to public key/private key encryption.
In FE again there is a Master Secret Key - msk, also referred to as master key. There is a Function Key - fk, often referred to as skf, secret function key, secret token, secret key (not to be confused with the Master Secret Key). The msk/fk pair is like a private key/public pair.
Lets call unencrypted input as 'x'. Let there be any function F (or circuit of gates). Let there be an encryption of x using the msk known as E(x) [Encrypted x]. Then if we have the function key - fk we can compute F(x) using only E(x). Note that the output F(x) is not encrypted.
To state it mathematically F(x) = Decrpyt(fk, E(x)) where E(x) is Encrypt(x,msk) for a key-pair msk,fk
While it may look very counter-intuitive, the catch is that the size or length of E(x) is a function of the size of the function F and typically not scaling linearly. Intuitively one can think of it as the algorithm or logic of Function F is being mapped onto the Decryption algorithm. Also note that the output of Decrypt(fk, E(x)) is not encrypted. Hence we have achieved encryption of the algorithm! I can give any third party some encrypted input and a function key, and the third party can get the result of running the function on unencrypted data. For example a spam filter can decide whether a mail is spam or not, without decrypting the email and also without knowing what my algorithm for deciding spam is.
In FHE example above a dictionary attack can be launched easily because there is a one-to-one correspondence between between the unencrypted data and encrypted data (there are encryption schemes which do not always generate the same output for the same input - in fact almost all the encryption schemes that are widely used ssl, ssh etc do not generate the same output for the same input always, but we will not go into that here), commonly words can be arranged in order of occurrence and easily guessed. But with FE nothing can be guessed! Both the data and algorithm are secure!
The main advantage of FE is that one can generate different function keys for different functions. And we can give different persons access to different functions by distributing function keys appropriately. Everyone need not know everything [Of course if they collude, then it is a problem]. A subclass of FE is ABE(Attribute Based Encryption). ABE was formalized first and then later generalized to FE. In ABE different people get different levels of access to information. The encrypted information is publicly available. However the information that each person can decrypt is dependent on the key that they hold. So in a full product launch one can issue keys such that engineering can see only the drawings, sales can only see artistic renditions of the final product and description of the features it offers and management can see everything. See this contrived example here - http://www.cs.uiuc.edu/class/fa07/cs498mmp/presentations/john.pdf The biggest advantage of ABE is that it makes key distribution and management easier compared to the current public key infrastructure.
A very nice slightly mathematical introduction to both FHE and FE is here http://outsourcedbits.org/2013/10/06/how-to-search-on-encrypted-data-part-1/ and here http://outsourcedbits.org/2012/06/26/applying-fully-homomorphic-encryption-part-1/
The relation between FE and FHE is explored here https://www.usukita.org/sites/default/files/func_enc.pdf
However the problem with FE was that it was implementable only for a few functions. It could not be implemented for any general or arbitrary function. That is where Indistinguishability Obfuscation (IO) comes in. The author above is incorrect about the definition of IO.
According to the original paper (http://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf) Let there be two implementations of the same functionality F (boolean circuit) i.e. F1 and F2. Given the obfuscations of F1 and F2, IO is achieved if it is impossible (there is negligible probability of success) to distinguish which is the obfuscation of F1 and which is the obfuscation of F2 (which obfuscation is the result of obfuscating F1 and which obfuscation is the result of obfuscating F2).
As mentioned above IO the only use of IO so far is that it is used as a stepping stone in achieving full general FE for any function. Full FE was achieved first here - https://eprint.iacr.org/2013/451.pdf There is no such thing as "use IO to obfuscate a program".
So far all these developments do not seem to be making much in terms of practical uses and even to some extent conceptually, especially in terms of protecting code and algorithms (as opposed to data which is currently protected quite well. breach of data happens mainly via the code used to compute on it). Leaving aside the huge computing resources required to implement these there are still various security leaks in the above protocols that will make it difficult to thwart a powerful adversary. See http://outsourcedbits.org/2013/10/30/how-to-search-on-encrypted-data-part-3/ and http://windowsontheory.org/2014/01/14/progress-and-challenges-in-code-obfuscation-part-ii/ The cutting edge of security in protecting code is probably something that is described here http://outsourcedbits.org/2013/12/20/how-to-search-on-encrypted-data-part-4-oblivious-rams/