Re: Definition of "Zero Knowledge"

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

In article <9309191615.AA18299@netcom4.netcom.com>,
Doug Merritt <doug@netcom.com> wrote:
: 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.

So, with such a translated algorithm, even if I had the complete
source code, I would be unable to determine what it does? If you
create one of these, be sure to submit it to the Obfuscated C
contest; it'll be the ultimate! :-)

: 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.

Got a good reference for ZPT? Something that the mathematically
inclined, who wants just the facts, all the facts, and none of
the BS that passes for explanations and which usually obscures
more than it clarifies?