"If A wishes to confirm B's public enciphering key, then A need only know the first half of the public file, (which is where YB appears) and H(second half of public file) which is only 100 bits long. A can compute H(public file) knowing only this information, and yet A only knew half the entries in the public file. In a similar fashion, A does not really need to know all of the first half of the public file, for H(first half of public file) = F( H(first quarter of public file), H(second quarter of public file) All A needs to know is the first quarter of the public file (which has YB), and H(second quarter of public file). By applying this concept recursively, A can confirm YB in the public file knowing only R, log 2 n intermediate values, and YB itself. The information needed to authenticate YB, given that R has already been authenticated, lies along the path from R to YB and will be called the authentication path.


Alright past Ben listen up. What you are describing here is Tree Authentication ya dingus. Read a book once in a while - get some sun. To be fair to you it wasn't as well explained in "PROTOCOLS FOR PUBLIC KEY CRYPTOSYSTEMS," you had to read Merkle's Thesis, "SECRECY, AUTHENTICATION, AND PUBLIC KEY SYSTEMS"... pages 41, 41a, 41b, and 42.

Initial Values & Assumptions:

YB = Y5

Log2 Intermediate Values = H(6,6,Y), H(7,8,Y), and H(1,4,Y)...these values are your authentication path

R (Merkle Root) = H(1,8,Y)

GOAL: Only use these initial values to get to the Merkle Root!

"Therefore, to authenticate Y5 required only that we have previously authenticated H(1,8,Y), and that we transmit Y5, H(6,6,Y), H(7,8,Y), and H(1,4,Y). That is, we require 100 log2 n bits of information to authenticate an arbitrary Y ..."

If you hash Y5 the output is H(5,5,Y). We can now use our first log2 intermediate value. The first one circled is H(6,6,Y). If we concatenate H(5,5,Y) and H(6,6,Y) and hash them together the output is H(5,6,Y). Now let's use our second log2 intermediate value, which is H(7,8,Y). We can now concatenate H(5,6,Y) with H(7,8,Y) and hash them together which yields H(5,8,Y). For the grand finale, we use out last log2 intermediate value which is H(1,4,Y). If we concatenate H(5,8,Y) and H(1,4,Y) and hash them together we should get the Merkle Root, which is H(1,8,Y).

See ya soon future Ben.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.