Friday, May 30, 2014

Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources

In this week's study group Gaven presented a paper that will be appearing at Crypto later in the year, titled "Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources" [BFM14]. In a nutshell, this work says that if indistinguishability obfuscation exists, then a notion of security called UCE1 security cannot be achieved.

Background

To understand what this result means, we have to go back over twenty years to the introduction of the random oracle model [BR93], a useful tool for making heuristic arguments about security. In the random oracle model algorithms have access to a truly random function (the random oracle), which plays the role a hash function will fulfil in the implemented scheme. Security is then proved with respect to this random oracle, the idea being that if the hash function "behaves like a random oracle" then the scheme will be secure in practice.

The main benefits of the random oracle model are its power and its conceptual simplicity. However it isn't without its drawbacks, the main one being that once the random oracle is instantiated with a hash function the original proof no longer applies. It has been shown [CGH98] that there exist schemes secure in the random oracle model that become insecure under any instantiation of the oracle. It could be argued that this construction (and other examples following it) is unnatural and that actual schemes with proofs in the random oracle remain unbroken, but the whole debate is really played out by now, so I'm not going to go into it.

An attempt to address these issues is the notion of Universal Computational Extractors (UCEs) [BHK13]. UCEs seek to formalise what it means to "behave like a random oracle". Schemes can then be proved secure based on the existence of a UCE rather than a random oracle, the difference being that the necessary properties of the instantiating hash are now explicit so that a scheme instantiated with a suitable hash is provably secure.

Behaving like a random oracle

The obvious definition of behaving like a random oracle would be the following game, when the adversary is given the hash key and access to either the real hash or a random oracle, and must determine which function he is interacting with.

This is clearly unsatisfiable as the adversary can query a point x to get response y, then use the hash key to evaluate for himself the hash at point x and check if the resulting value is y. To prevent this trivial win, the adversary is split into a source S and a distinguisher D, with only S having access to the function and only D having the hash key.

The source can aid the distinguisher in his task by providing leakage L. If this leakage is unrestricted then the adversary can use the same attack as before, so for the definition to be useful some restriction must be put on S's output. The restriction is that the source must be unpredictable, which roughly says that given the leakage L it is hard to identify any of the queries the source S made. If no distinguisher can tell real from random with the help of any unpredictable source, then the hash is UCE1 secure. With a UCE1-secure hash in hand, a whole bunch of primitives become achievable in the standard model. Unfortunately, the result of [BFM14] shows that a UCE1-secure hash cannot exist.

Indistinguishability obfuscation

An obfuscator is an algorithm that takes in a program and outputs an indecipherable mess of a program with the same functionality, the idea being that you can give this new program to someone and they can't work out anything about its functionality beyond what interacting with the original program in a blackbox way would reveal. It turns out this is impossible [BGI+01], but achieving a weaker notion called indistinguishability obfuscation might be possible. An indistinguishability obfuscator is an algorithm that obfuscates a circuit in such a way that the obfuscations of any two functionally equivalent circuits are indistinguishable, that is, given the obfuscation of either circuit 0 or circuit 1 an adversary can't tell which he was given. Such an obfuscator was constructed last year [GGH+13] using multilinear maps. Using an indistinguishability obfuscator, [BFM14] give an attack that breaks UCE1 security of any hash.

The attack

The source behaves as follows. First it queries its oracle at a randomly chosen point x and receives a response y. It then constructs a circuit that takes as input a hash key, evaluates H under that hash key at point x, and then outputs true if the result is y and false otherwise. The source runs the indistinguishability obfuscator on this circuit, and outputs the obfuscated circuit as its leakage L. The distinguisher D is given the hash key and the obfuscated circuit, and evaluates the circuit with the hash key as input. If the source was interacting with the real hash then the result will be true, otherwise it will almost certainly be false. Such a source and distinguisher can thus tell the real hash from a random oracle.

To break UCE1 security the source must be unpredictable, which can be shown through a standard game hopping argument. It is assumed that the output length of the hash is at least twice the key length, but this assumption is just to give high-level intuition and can be removed at the expense of simplicity. The first game is the unpredictability game where a predictor is given the leakage from S and to win must output a point in the set of queries S made. We move to a game that terminates if there exists a hash key such that the leaked obfuscated circuit evaluates to true. The probability that this bad event occurs can be bounded using the assumption to show that it is negligible, so the first two games are indistinguishable. Finally we move to a game where the source leaks an obfuscation of a circuit that always outputs false. Since the bad event of the previous game means it terminates whenever a hash key exists under which the circuit would evaluate to true, if the game does not terminate then the circuit must evaluate to false, and so in the last two games the circuit in each always outputs false. Indistinguishability obfuscation says that the obfuscation of the always false circuit in the second game and the obfuscation of the always false circuit in the last game are indistinguishable, so the games themselves are indistinguishable. In this final game S leaks no information about x, which is chosen at random, so the predictor has no information about x and hence the source is unpredictable.

Next steps

With UCE1 security unattainable but the UCE framework still a desirable tool, various modifications to the definition have been suggested, including moving from computational to statistical definitions and to split sources. Very recently it was shown [BM14] that a stronger form of unpredictability might be the answer, as it is shown that this notion is sufficient to achieve results in correlated-input secure hash functions, universal hardcore functions and PKE, and crucially a construction meeting this notion is given.

Bibliography

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)