Merkle Hash Trees for SEAL Authentication

 

We can use a Merkle hash tree for the SEAL authentication [12]. The signer chooses the SEALs randomly, places them at the leaves of a binary tree and computes each internal node as the hash of the concatenation of the two child values. The root node of the hash tree becomes the public key, hence the public key is small.

The signer computes the signature as before, but it needs to add additional verification nodes of the hash tree to the signature, such that the verifier can reconstruct all the paths from all SEALs to the root of the hash tree. Unfortunately, the overhead of these additional verification nodes can be high, as we now compute.

We assume that the disclosed SEALs are distributed randomly in the hash tree. To compute the overhead, we need to compute the probability that all the leaves below a given tree node are all empty. We set function $\pi (a,\; r,\; n)$ as the probability that $a$ leaves are empty after randomly choosing $r$ leaves among $n$ leaves (note that $\pi (a,\; r,\; n)\; =\; 0$ if ):

$\pi (a,\; r,\; n)\; =\; \prod$_i=0^r-1{n-a-in-i}

The expected number of nodes of the Merkle hash tree that need to be sent to authenticate $b$ leaf nodes depends on the depth $d$ of the hash tree. The number of expected nodes is:

$\sum$_i=1^d 2ⁱπ(2^d-i, b, 2^d ) (1 - π(2^d-i, r, 2^d - 2^d-i))

The intuition behind this formula is that we need to send a node of the tree if exactly one child has all empty leaf nodes, and the other child node has at least one chosen leaf node.

When we evaluate this probability for the schemes we list as examples 1 and 2, we would need to add $83.3$ hash tree nodes on average to authenticate the $16$ SEAL values for the scheme in the first example, and $67.5$ nodes to authenticate the $12$ SEALs in the second example. Clearly, this would increase the signature size by a factor of $6$, and increase the verification overhead.

To generalize this idea, we can construct many small hash trees of height $d$ that contain $2d$ SEALs. The public key would then contain all the root nodes of all small hash trees, and hence we reduce the size by a factor of $2d$. To authenticate each SEAL, the signer adds the $d$ verification nodes to each SEAL. Hence, the public key size is reduced by a factor of $2d$ and the signature size is expanded by a factor of $d$.