David Molnar wrote: > > 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? Using zero knowledge techniques it's possible for me to convince you that I've come up with a proof of some theorem in a way which conveys no information about the proof other than it's length. I'm essentially conjecturing that there's a technique which doesn't convey it's length, either, by having the proof string be of fixed size. I envision this as some function very carefully hand-tweaked for a particular axiomatic system so that if you know the verifying strings of two statements then you can compute the verifying string of a statement derived from them, but it's computationally infeasible to compute verifying strings for anything other than the axioms, which are known, and statements deduced from those axioms. Interestingly, looking at it again I notice that my conjecture doesn't say anything about the verifying string not leaking information about the proof, just that it should have fixed size. I hope that's a bit clearer. I stated the conjecture a little backwards for precision. > [talking about the second conjecture] > > 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. Private information retrieval sounds like it's a step in the right direction, although I haven't looked at it yet. The problem is that if the attacker can see the eventual output rather than just an encoded form of it, she can change the intermediary state of the encrypted program at any point and re-run the computation from there, making hiding program internals from her very difficult. -Bram Cohen
