This week's study group looked at the powerful tool and burgeoning tongue-twister that is indistinguishability obfuscation, with specific focus on the forthcoming Eurocrypt '14 paper titled 'Replacing a Random Oracle: Full Domain Hash From Indistinguishability Obfuscation' by Hohenberger, Sahai and Waters (HSW). Since the work of Garg et al. last year there has been a flurry of work on obfuscation (25 papers on ePrint in 2013 with 'obfuscation' in the title and two whole sessions at TCC 2014 devoted to it), and naturally this will be a well-attended topic at all the major conferences this year.
The idea of full-domain hash (FDH) signatures dates back to 1993 and Bellare-Rogaway's seminal 'Random Oracles are Practical' paper. The idea allows construction of a signature scheme from any trapdoor permutation (TDP) by simply signing the hash of a message using the trapdoor: σ = g-1sk(H(m)). Verification simply employs the inverse of this permutation using the public key. The idea is that the hash function maps an arbitrary message space to the domain (and co-domain) of the permutation, and when modeled as a random oracle, this scheme is secure for any TDP. The proof, employing a reduction to the adversary's success against a TDP challenger, was influential and straightforward: for all but one of the (unique) queries to the RO, the reduction algorithm chooses a random value from the domain and outputs gpk(t), and at one query point m* it programs the output of the RO to be z* = gpk (t*) where z* was the value given by the TDP challenger.
Since this landmark work, a number of 'FDH-like' schemes have appeared, such as the seminal Boneh-Franklin IBE scheme and Boneh-Lynn-Shacham signatures, which both utilise the 'random oracle programming' idea in their proof method. The idea of the HSW paper is to provide a replacement hash function for the random oracle without modifying the underlying signature construction. To do this, the authors utilise an indistinguishability obfuscator and constrained PRFs. More information on indistinguishability obfuscation can be found in Essam's blog post of Joop's study group last October, and many of the recent papers on obfuscation provide a concise overview of indistinguishability obfuscation. A major challenge in the field of obfuscation is dealing with the black-box impossibility results, and basically this paper manages to avoid these issues because the hash function constructions are inherently black-box. The idea of a constrained PRF is that it is only defined on a subset of the usual input space, and HSW focus on puncturable PRFs meaning PRFs that can be defined on all bit strings of a certain length, except for any polynomial-size set of inputs.
The main idea of the proof for selectively secure FDH signatures is that the hash function is an obfuscation of gpk(F(K,m)) where gpk is the public direction of the TDP, F is a puncturable PRF and K the key for this PRF. Since the scenario is selective security, the proof involves hopping from this hash function to an obfuscation of the 'punctured version' of the hash function, and since the input/output behaviour is the same this hop is dealt with by the security of indistinguishability obfuscation. In essence, this punctured version fixes a point (that is programmed to be the signature security game challenge) such that the only way an adversary can win is by defeating the PRF itself. This result is particularly neat because it essentially follows the same strategy as the original RO proof. In the adaptive case things get slightly more complicated, as in past proofs the hash function needs to operate in two modes: a 'normal' mode where the hash function parameters are chosen at random, and a 'partitioning' mode where the parameters are chosen in such a way that inversion is possible for a large fraction of points. However obfuscation can defeat this difficulty too, because the description of the hash function itself can be obfuscated. The paper demonstrates the power of indistinguishability obfuscation and the methods used may well be useful in circumventing or expanding on the black-box impossibility results in the literature.
The idea of full-domain hash (FDH) signatures dates back to 1993 and Bellare-Rogaway's seminal 'Random Oracles are Practical' paper. The idea allows construction of a signature scheme from any trapdoor permutation (TDP) by simply signing the hash of a message using the trapdoor: σ = g-1sk(H(m)). Verification simply employs the inverse of this permutation using the public key. The idea is that the hash function maps an arbitrary message space to the domain (and co-domain) of the permutation, and when modeled as a random oracle, this scheme is secure for any TDP. The proof, employing a reduction to the adversary's success against a TDP challenger, was influential and straightforward: for all but one of the (unique) queries to the RO, the reduction algorithm chooses a random value from the domain and outputs gpk(t), and at one query point m* it programs the output of the RO to be z* = gpk (t*) where z* was the value given by the TDP challenger.
Since this landmark work, a number of 'FDH-like' schemes have appeared, such as the seminal Boneh-Franklin IBE scheme and Boneh-Lynn-Shacham signatures, which both utilise the 'random oracle programming' idea in their proof method. The idea of the HSW paper is to provide a replacement hash function for the random oracle without modifying the underlying signature construction. To do this, the authors utilise an indistinguishability obfuscator and constrained PRFs. More information on indistinguishability obfuscation can be found in Essam's blog post of Joop's study group last October, and many of the recent papers on obfuscation provide a concise overview of indistinguishability obfuscation. A major challenge in the field of obfuscation is dealing with the black-box impossibility results, and basically this paper manages to avoid these issues because the hash function constructions are inherently black-box. The idea of a constrained PRF is that it is only defined on a subset of the usual input space, and HSW focus on puncturable PRFs meaning PRFs that can be defined on all bit strings of a certain length, except for any polynomial-size set of inputs.
The main idea of the proof for selectively secure FDH signatures is that the hash function is an obfuscation of gpk(F(K,m)) where gpk is the public direction of the TDP, F is a puncturable PRF and K the key for this PRF. Since the scenario is selective security, the proof involves hopping from this hash function to an obfuscation of the 'punctured version' of the hash function, and since the input/output behaviour is the same this hop is dealt with by the security of indistinguishability obfuscation. In essence, this punctured version fixes a point (that is programmed to be the signature security game challenge) such that the only way an adversary can win is by defeating the PRF itself. This result is particularly neat because it essentially follows the same strategy as the original RO proof. In the adaptive case things get slightly more complicated, as in past proofs the hash function needs to operate in two modes: a 'normal' mode where the hash function parameters are chosen at random, and a 'partitioning' mode where the parameters are chosen in such a way that inversion is possible for a large fraction of points. However obfuscation can defeat this difficulty too, because the description of the hash function itself can be obfuscated. The paper demonstrates the power of indistinguishability obfuscation and the methods used may well be useful in circumventing or expanding on the black-box impossibility results in the literature.
No comments:
Post a Comment