Re: Do Gap-CDH groups exist?
- From: "Amitabh" <amitabh123@xxxxxxxxx>
- Date: 2 Mar 2007 12:17:50 -0800
On Feb 9, 5:17 pm, "Matthew Green" <matthewdgr...@xxxxxxxxx> wrote:
On Feb 2, 9:03 am, "jiangwu.m...@xxxxxxxxx" <jiangwu.m...@xxxxxxxxx>
wrote:
On Feb 1, 6:58 am, Kristian Gjøsteen <kristiag+n...@xxxxxxxxxxxx>
wrote:
jiangwu.m...@xxxxxxxxx <jiangwu.m...@xxxxxxxxx> wrote:
Not under current definition. The definition requires that whatever
can be computed by accessing internal data of A can be computed by
accessing B as an oracle. In this example, with g^a, one can compute
something like g^{ax}, which cannot be computed by using B as an
oracle. Hiding 'a' secret is necessary but not sufficient for A to be
an obfuscator of B.
Make the trivial modification:
Obf(C): (g^a,bilinear-pairing(x, g^a)) and
C: (g^a,bilinear-pairing(x,g)^a) ?
Since the program A''' can be recovered from the output of B''',
we are done. Or?
This is a tempting idea. It seems that given full access to the
obfuscated program Obf(C) an Adversary learns "no more" than he would
if given oracle access to C; and therefore the obfuscation proof
holds. (This is a very rough paraphrase of the definition of
obfuscation.)
The problem is that this isn't quite enough to prove that you've
obfuscated something, since C is a "learnable" circuit. Wee (and
Barak, I believe) point out that "obfuscation" isn't a sufficient
definition in the case of learnable circuits. For example, nothing
about that proof actually shows that it's impossible to recover the
secret "a" from the program Obf(C)---- you need to prove that
separately. And if you can prove that separately, then the
"Obfuscation" proof is not really important.
Moreover, there are a bunch of impossibility results showing that it
is really hard to "obfuscate" some kinds of useful programs. The
positive results we do have (point functions, re-encryption, etc.) all
have one thing in common: there's no way to efficiently "test" that
the obfuscated circuit actually does the same thing as the oracle.
Any deterministic program that computes a bilinear pairing is going to
run afoul of these results.
So the question then is: what is a better, alternative definition of
obfuscation that covers what you want to do. And the answer is: I
don't really know. (All of the above comes with the disclaimer that
I'm still trying to understand these ideas myself :)
I am also trying to understand the notion of obfuscators. However, I
feel that the
"virtual black-box" property is too strong a requirement. A weaker
formalization would require that no "useful predicate" can be obtained
from the obfuscated program (some "useless predicates" are ok). For
instance the hard-core bit of a key that is being obfuscated. If I am
not mistaken, all negative results consider obfuscation under the
virtual black-box property.
I remember reading a paper by Goldwasser et. al. ("On the
impossibility of obfuscation with auxiliary input") that claims that
the decryption algorithm of any cipher (symmetric/asymmetric) cannot
be obfuscated, However, under a weaker definition, decryption using a
private key in an IBE may be considered as a "restricted" obfuscation
of decryption under the master key. Any comments ?
.
- Prev by Date: Re: The crazy encryption madmans codebook
- Next by Date: Re: NSA releases newly declassified crypto docs
- Previous by thread: NSA releases newly declassified crypto docs
- Next by thread: Proper evaluation of surrogate factoring
- Index(es):
Relevant Pages
|
