# Needed: signature over a collection of hashes

I'm looking for some kind of crypto-based data structure that will allow me to produce a signature over a set of hashes. Call this a SignedSetOfHashes. I want to be able to distribute the SignedSetOfHashes (which should be smaller than simply a vector of all the hashes and a digital signature.) I then want anyone to be able to verify that hash H is in the SignedSetofHashes having only the SignedSetOfHashes and a public key that matches the private key used to create the signature.

One idea I had was multiplying all of the hashes together in a field and signing the residue. Then I could verify any of the hashes are in by showing that the residue is divisible by any of the hashes. Of course, I could verify the signature without having any of the hashes.

Is there an existing approach to do this?

-
You wrote "such that I can verify that any of the hashes is in the set (..) without having to distribute all of the hashes". Is the verification to be performed by you based on all the hashes and the data structure; by you based on the data structure only; or by those that received the data structure? And is that verification supposed to convince you, or those others? Is it your objective to hide the hashes from the others, or/and to reduce the amount of data to distribute/keep? –  fgrieu Feb 9 '14 at 18:27
What is the reason you don't want to distribute the hashes? Is it because of space (for example, we're talking about a lot of hashes), or is it because you don't want anyone else to be able to deduce them (apart from testing the signature against the hash, which they can obviously do)? –  poncho Feb 9 '14 at 18:30
Also, from a technical point, multiplying all the hashes together in a field won't work; one of the properties of a field is that any nonzero element is divisible by any other nonzero element. That approach will likely need a ring... –  poncho Feb 9 '14 at 18:31

I am not quite sure if I exactly get what you are looking for, but I'll give it a try.

This answer refers to the original question before the edit

I'm looking for some kind of crypto-based data structure that will allow me to produce a signature over a set of hashes such that I can verify that any of the hashes is in the set at a later point in time without having to distribute all of the hashes.

One possible approach to produce a signature for a sequence of messages $(m_1,\ldots,m_n)$ (or hash values) is to build a Merkle tree from this sequence.

The idea of a Merkle tree is to assign the messages $m_i$ to the leaves of a binary tree from left to right, and do the hashing recursively upwards, starting from the lowest level in the tree.

More formally, a Merkle tree is a complete binary tree, together with a cryptographic hash function $H:\{0,1\}^*\rightarrow \{0,1\}^{\ell}$ and an assignment $\phi:N\rightarrow \{0,1\}^{\ell}$, where $N$ is the set of nodes of the tree. The assignment $\phi$ for the label of the nodes is recursively defined, where $v_P$ is the parent node and $v_L$ and $v_R$ the left and right child respectively. Furthermore, $x$ is a string that is assigned to a leaf. $$\phi(v_P):= \begin{cases} H(\phi(v_L)||\phi(v_R)) & \text{if v_P has two children};\\ H(\phi(v_L)) & \text{if v_P has one child};\\ H(x) & \text{if v_P is a leaf.} \end{cases}$$ Additionally, define the authentication path $A_v=\{a_i|0<i\leq h\}$ of a leaf $v$ as the set containing all values $a_i$. The value $a_i$ at height $i$ is defined to be the label of the sibling of the node of height $i$ at the unique path from $v$ to the root.

Note that if your values $(m_1,\ldots,m_n)$ are already hashes, then you can directly assign these values to the leaves (without hashing them again). Subsequently, the $m_i$ are denoted as messages (irrespective if they are messages or hash values).

Put differently, a Merkle tree can be used to release a message $m_i$ and the coresponding authentication path $A_{m_i}$ such that everybody is able to verify that $m_i$ "is in the tree", but does not require access to the all the remaining messages.

Now take a secure signature scheme and sign the root-hash of the Merkle tree. Then given the signature, $m_i$ and $A_{m_i}$ it can be checked that $m_i$ is in the signed sequence $(m_1,\ldots,m_n)$ without requiring all the other messages $m_j$, $j\neq i$. Basically, from $m_i$ and $A_{m_i}$ one recomputes the root hash and checks the digital signature.

However, note that this does not ensure a real hiding of the remaining messages $m_j$. If the remaining messages have a short length and/or are known to come from a small set, one can mount a brute-force attack by simply hashing all possible values and check whether the result matches the root hash.

This can be prevented if one does not use simple hashes for the leaf nodes, but uses commitments instead. This approach is for instance applied in redactable signatures (RS) or content extraction signatures (CES).

How does this related to what you seek

You do not have to distribute all hashes, but for every value $m_i$ a "proof" that the value is in the set (the Merkle tree) you have to distribute $(m_i,A_{m_i})$. The advantage is that if you use the commitment based approach as applied in RS or CES, nobody can test against your signature to check if a given value is in the set, unless you want to explicitly allow that by providing $(m_i,A_{m_i})$.

EDIT (to answer the edited question)

Any approach that will give you cryptographic security guarantees that you will not encounter false positives (such as cryptographic accumulators, Merkle trees, vector commitments, zero-knowledge sets, etc.) will require to provide a "witness" for every value to be able to check against the structure.

If you tolerate a larger false-positive probability you can use for instance Bloom filters to represent your set and allow set membership queries without any witnesses.

-
I'm aware of Merkle Trees. They require that each hash be distributed with additional material that it can use to perform the proof. It's close to what I want and I thought about using them, but they're not quite what I want. –  vy32 Feb 9 '14 at 20:29
@vy32 You could use any other type of cryptographic accumulator or commitment to a set (such as a vector commitment, zero knowledge set, etc.) and sign it, but you will always need to compute a witness for the membership for every element to test for. One thing that does not need this is a bloom filter (allowing set membership queries) which you could sign. But this does not achieve cryptogrpahic security (large false positive probability). –  DrLecter Feb 9 '14 at 20:33
thanks. I did an analysis of Bloom filters for this purpose several years ago and we were not happy with the results. Against even a modest adversary, it is possible to produce hash values that alias to valid hashes in the Bloom. That is, it is possible to create false positives more-or-less at will. –  vy32 Feb 10 '14 at 3:52

By a counting or entropy argument, a technique as in the question can only provide moderate space savings compared to sending the list of hashes, unless we allow that a value appears to be in the set of hashes, when it really is not, much as if we truncated the hashes.

Borrowing the notation in that other answer, assume there are $n\ge1$ distinct hashes in the set, hashes are $l$ bits, and evenly distributed. By counting how many such sets there are, we get that any exact representation of a set requires on average at least $$\log_2\Big({{{2^l}!}\over{(2^l-n)!\cdot n!}}\Big)\text{bits}.$$ When $n\ll2^{l/2}$ which I guess is the intend, that's a saving of $\approx\log_2(n!)$ bits compared to the $n\cdot l$ bits required by a straight transmission of the hashes. E.g. for $n={10^7}$, $l=128$, we are talking about a saving of 17%.

Much of this saving could also be obtained in practice by sorting the hashes by increasing order, replacing all except the first hash by its difference with the previous (resulting in appreciably smaller numbers), then applying some compression according to the expected distribution of what remains. With arithmetic coding, we can obtain the optimum saving, within a few bits so that fixed-width numbers can be used.

-