In Cryptography, Advances In Program Obfuscation (2014)
quantamagazine.org
quantamagazine.org
> What must be understood is that in all these constructions, each circuit gate must map to an instance of Gentry's fully homomorphic encryption scheme, and at every clock cycle for the obfuscated circuit, all gates must be processed, regardless of whether they are "active" or not in the circuit (this is a big part of why the obfuscation theoretically works: it does not reveal active gates, by always making them all active). This[2] article gives performance result: on a rather big PC, we are up for minutes of computation. That's for each gate in the obfuscated circuit, and for each clock cycle.
> There are millions or even probably billions of gates in the envisioned circuit, given the setup of functional encryption: the "obfuscated circuit" must include asymmetric decryption and validation of zero-knowledge proofs. So now we are talking about using all the computers currently running on Earth, all collaborating on the computation, and they might make non-negligible progress towards running one instance of functional encryption within a few centuries.
This is a rapidly evolving field, though, so I'm cautiously hopeful that some genuinely novel ideas will emerge soon to overcome the current stumbling blocks.
The team’s obfuscator works by transforming a computer program into what Sahai calls a “multilinear jigsaw puzzle.” Each piece of the program gets obfuscated by mixing in random elements that are carefully chosen so that if you run the garbled program in the intended way, the randomness cancels out and the pieces fit together to compute the correct output. But if you try to do anything else with the program, the randomness makes each individual puzzle piece look meaningless.
This obfuscation scheme is unbreakable, the team showed, provided that a certain newfangled problem about lattices is as hard to solve as the team thinks it is. Time will tell if this assumption is warranted, but the scheme has already resisted several attempts to crack it, and Sahai, Barak and Garg, together with Yael Tauman Kalai of Microsoft Research New England and Omer Paneth of Boston University, have proved that the most natural types of attacks on the system are guaranteed to fail. And the hard lattice problem, though new, is closely related to a family of hard problems that have stood up to testing and are used in practical encryption schemes.
Lattice-based crypto is all the rage among snakeoil marketing (right after One-Time-Pads).
And don't get your hopes up about seeing a practical implementation of iO any time soon; it's thoroughly and utterly impractical at the moment, and will remain so for the foreseeable future.
Yes, it was (is?) one of the candidates for post-quantum public-key encryption. But that doesn't stop terrible projects from claiming to have it in their marketing today.
Also, no forward secrecy.
My understanding of OTP's implies that these must be used only once. As such they offer the same PFS as all the schemes I know of. PFS does not guarantee the secrecy of a specific message. It does guarantee that if you are able to crack one message you can't use the key to crack others. Therefore if you use an OTP only once it gives you the same guarantees.
In NP-terms, you learn whether the NP instance is true (eg a 3SAT clause is satisfiable), but learn nothing about the witness (eg the assignment to the clause's variables).
With homomorphic encryption, Alice can send some secret data to Bob in encrypted form, and let Bob carry out computation on that encrypted data. However, the result of the computation remains encrypted, and only Alice's private key can decrypt the result.
By contrast, obfuscation allows Alice to give Bob a program that contains some secret information (such as cryptographic keys) in such a way that Bob can run it (without any further interaction with Alice) on any inputs of his choice, and get the result in the clear. However, he cannot learn anything about the hidden secret information other than what is revealed by the input-output pairs he has obtained.
It's not hard to see that obfuscation gives you homomorphic encryption for free (you can probably get a rough idea of how to do it based on the somewhat imprecise descriptions above), but we don't know how to go in the other direction. (Current obfuscation candidates do use fully homomorphic encryption under the hood, but they need to rely on much more than that).
Date: 2014
Previous discussion: https://news.ycombinator.com/item?id=7153657
Ciphertext is a higher-order, or simply, highly ordered, deterministically derived version of plaintext.
Sorry, but what in the fuck are you even talking about?
Sure, the resulting ciphertext is only computationally indistinguishable from random. But the point of IND-CPA security is that one can't differentiate between two encryptions of different messages. Adding randomness gives you this.