Re: Definition of "Zero Knowledge"

[doug@netcom.com (Doug Merritt)]

From: khijol!erc@apple.com (Ed Carp)
>Thanks for the definition (but I knew that, anyway).  Sorru I wasn't clear -
>what I was looking for was examples of how zero-knowledge proof techniques
>could make source code impenetrable.

An arbitrary algorithm can be translated into a zero proof theory model
that is intractable to functionally analyze. Its operations on inputs and
outputs can take place within the realm of the intractable model, with
the inputs and outputs being transformed from the encoding of the outside
realm into an encoding useful to the realm of the model. The inputs and
outputs are the queries and answers of zero proof theory.

With such a thing, knowing every detail of the registers and instructions
being executed at all times still wouldn't tell you what you really
wanted to know.

I'm unsure whether this has been published, let alone implemented; I just
thought it was an obvious corollary back when ZPT itself was first published.
It might have been discussed in the literature at the time, but if so,
I've forgotten.

I'm also not claiming this is necessarily a useful approach in practice,
because the obvious ways of implementing such a thing would be more than
a little slow. I suspect that it could be done efficiently with a little
algorithmic cleverness, but I don't have evidence of that this instant.

I'm currently designing something with very much the same flavor, but
with somewhat different goals, and computational expense of the operators
in the model is precisely the difficulty with that, too, so far.
	Doug
--
Doug Merritt				doug@netcom.com
Professional Wild-eyed Visionary	Member, Crusaders for a Better Tomorrow

Unicode Novis Cypherpunks Gutenberg Wavelets Conlang Logli Alife HC_III
Computational linguistics Fundamental physics Cogsci SF GA VR CASE TLAs