On Sat, 4 Mar 2000, bram wrote: > I've also posted some very provocative conjectures at > > http://www.gawth.com/bram/essays/wild_cryptographic_conjectures.html > I'm not sure I understand the first one...would you help me out? > Conjecture - For any axiomatic system, there exists a function which > runs in a practical amount of time which takes as inputs a statement in > that axiomatic system and a fixed length string, OK, so we have f(statement, s) as the function prototype, so to speak. > such that given a proof of any statement in the axiomatic system it is So we are picking the statement and fixing it here? > possible in a practical amount of time to construct a > string such that the function when given the statement and the string > will return true, but it is computationally intractable to find a false > statement and a string such that the function will return true. So we do this : 1) Pick and fix a true statement, call it STATEMENT. 2) Construct a string s which depends on STATEMENT. 3) We want to know if there exists a function f( , ) such that f(STATEMENT, s) = true f(any other statement, any other string) = false The answer seems to be yes. I define the function to be that function which returns true for some particular (STATEMENT, s) pair, and false everywhere else. Since by hypothesis we said STATEMENT is a true statement, this seems to satisfy the requirement : "the function when given the statement [STATEMENT] and the string [s, constructed from STATEMENT] will return true, but it is computationally intractable to find a false statement and a string such that the function will return true." It's computationally intractable for this example because it's actually impossible. Any other pair than (STATEMENT, s) returns false. I have a feeling this isn't quite what you mean? What am I missing? >Conjecture - There is a method of encoding any program such that the >encoded form of the program can >be sent to an untrusted party and the untrusted party will be able to >determine the outputs of the program >when given any particular set of inputs but will be incapable of >determining anything about the program's >structure other than what can be deduced from the amount of time it took >to compute the answer and the >amount of memory it used. For a special case of this, check out Matthew Skala's "Limited-Diffusion Algorithm for Blind Substring Search" -- he has a neat method for creating a function which returns TRUE on an input iff it contains a particular substring, but for which it is conjectured hard to tell by inspection of the function just what that substring IS. http://www.islandnet.com/~mskala/limdiff.html There are also constructs vaguely similar to this in the field of "private information retreival". The idea is that we have a user and a database. The user wants some information out of the database, but does not want the database to know which information he wants. In one approach, the user makes up a function, and sends it to a database. This function can be evaluated by the database on whatever inputs it feels like. It is *supposed* to evaluate the function on the data it stores, and then send the result to the user. There is a trapdoor in the function such that the user can extract from its output the piece of data he wants from the database. This trapdoor prevents the database from learning what this piece of data happens to be, even though he can evaluate it on many inputs. That's a ridiculously short summary of it - the paper which uses it is by Rafail Ostrovsky and Eyal Kushilevitz and can be found at http://www.argreenhouse.com/papers/rafail/34.html Ostrovsky and others have gone on to refine "single server private information retreival" in this way; I haven't looked at their new papers yet. You might be able to repurpose some of their techniques for your conjecture. Thanks -David Molnar
