From: Anonymous <anon@anon.efga.org>
Date: Wed, 26 Nov 1997 09:31:35 +0800
To: cypherpunks@cyberpass.net
Subject: Re: Quoting Portions of a Signed Document
Message-ID: <199711260118.UAA25213@server1.efga.org>
MIME-Version: 1.0
Content-Type: text/plain



Monty Cantsin writes:

01> It would be neat if you could quote people and prove that they signed
02> the particular paragraph quoted without supplying the entire text.  Is
03> there a way to do this?  (It seems impossible, but so does mental
04> poker.)
05> 
06> A crude approach would be to sign every paragraph or line separately,
07> but that's obviously inelegant.
08> 
09> Monty Cantsin
10> Editor in Chief
11> Smile Magazine
12> http://www.neoism.org/squares/smile_index.html
13> http://www.neoism.org/squares/cantsin_10.htm

An easy way to do this works only if the quoted paragraph comes from
the very end of the text.  You can supply the cumulative hash of all
the material before the quoted part, then the quotation itself, which
goes all the way to the end of the document.  From this the hash of the
whole document can be calculated, and the signature checked.

A more general approach calculates the document hash in a line oriented
way.  Normally we start at the top and work down through the document
to get the hash, which is signed.  Instead, we would calculate a hash
for each line of the document separately, and then combine them using a
tree.

In the example above hashes would be calculated for lines 1-13.  Call these
H1A - H13A.  Then second level hashes could be calculated by taking H1A
through H13A in pairs:

	H1B = hash(H1A,H2A)
	H2B = hash(H3A,H4A)
	H3B = hash(H5A,H6A)
	...
	H6B = hash(H11A,H12A)
	H7B = H13A

We repeat this until we have one hash for the whole document:

	H1C = hash(H1B,H2B)
	H2C = hash(H3B,H4B)
	H3C = hash(H5B,H6B)
	H4C = H7B

	H1D = hash(H1C,H2C)
	H2D = hash(H3C,H4C)

	H1E = hash(H1D,H2D)

We sign the final hash, H1E.

Now you can extract a paragraph, say lines 6 and 7 above.  The hashes
H6A and H7A can be calculated from this.  Supply the other hashes needed
to calculate the final hash: H5A, H8A, H1C, H2D, will be enough.  This
will allow calculating H1E and the signature can be verified.  The
required number of hashes will generally be logarithmic in the size of
the missing part of the document.