Proving set membership in less than $\log{N}$ bandwidth

Question

I have an unchanging set of unique items, and I want my server to show one of those items to a client, then cryptographically prove that the item is part of the set.

How I do this currently:

1. Generate a Merkle tree containing all of the items.
2. Give the client the Merkle root, (32 bytes) out of band.
3. Give the client the item, then the branch leading to the Merkle root.
4. The client hashes the item, then hashes each Merkle branch, starting at the bottom.
5. If the hash at the end equals the Merkle root, the item is in the set.

The problem with this is that it takes $2\cdot 32 \cdot \log_2{N}$ bytes of bandwidth (where $N$ is the number of items in the set.) Is it possible to do this is in a smaller space?

The scheme needs one additional property, which is that once you have all of the items, it must be possible to determine that you have all of the items in the set.

Other factors:

• The set isn't private - it's okay if the scheme reveals information about other members of the set.

Answer 1

Depending on your trust assumptions about this server, you might be able to use cryptographic accumulators which provide constant-sized (non)membership proofs.

However, as far as I know, no efficient strong accumulator scheme has been developed yet. Most accumulator constructions rely on the RSA assumption where the server knows the factorization $n = pq$ of the modulus $n$ and, as a result, can compute fake membership proofs for any element $x$ by taking the accumulator $acc$ and computing a fake proof $mem = {acc}^{x^{-1} \pmod {\phi(n)}}$. The proof is verified by checking that ${mem}^x = acc$, which is true because the server faked the proof by inverting $x$.

This happens because the server can easily compute $\phi(n) = (p-1)(q-1)$ and invert $x$.

To fix this problem, a trusted setup phase is necessary that generates a modulus $n$ of unknown factorization and gives it to the server, without giving the server the factors $p$ and $q$.

Also note that pairing-based accumulators need a trusted setup phase. However, I suspect they would be faster in practice than RSA, if you want non-membership proofs!

You might find the following accumulator papers useful:

• One-way accumulators: A decentralized alternative to digital signatures
• Collision-free accumulators and fail-stop signature schemes without trees
• Cryptographic accumulators: Definitions, constructions and applications
• Universal Accumulators with Efficient Nonmembership Proofs
• Accumulators from Bilinear Pairings and Applications to ID-based Ring Signatures and Group Membership Revocation

The following paper proposes using a certain kind of group called a class group to construct a strong accumulator. I am not sure how it constructs (non)membership proofs though.

Secure Accumulators from Euclidean Rings without Trusted Setup

Answer 2

This is in continuation to Alin's answer, describing accumulators in the context of class groups.

Class groups provide a setting where computing roots is computationally difficult. That is, given $x \in \mathbb{Z}$ and $g^x \in G$, it is computationally infeasible to compute $g$. This is the same setting provided by RSA modulus, but with one key difference: there is no trusted setup.

Accumulator are built in the following way. Let $S$ be the set of items you have, and assume all the items are prime numbers. Pick a random element $g$ in the group $G$. With high probability this element generates a large cyclic subgroup of $G$, but let's leave that aside for now. Define the accumulator of the set $S$ by $w_S = g^{\prod_{s\in S} s}$, and make this group element known to the client. Now, in order to prove to a client that some $x$ is in $S$, simply compute and send $w_{x,S} = g^{\prod_{s\in S\setminus \{x\}} s}$. The client can verify the computation by checking that $(w_{x,S})^x = w_S$.

The cryptographic assumption (i.e. that computing roots is computationally infeasible) imply that the prover could not construct the witness $w_{x, S}$ unless $x \in S$. Note that we also use the assumption that the elements in $S$ are prime here: if a composite number $c = ab$ is in $S$, the prover can create a (false) proof that $a$ and $b$ are in $S$.

This scheme can also be used in order to give a constant size proof of membership of many items: to prove $x_1, ..., x_n \in S$, simply construct the witness $g^{\prod_{s\in S \setminus \{x_1, ..., x_n\}} s}$.

Non-membership can be proved as well. Since the items in $S$ are prime, if $x$ is not in $S$ then $x$ and $y=\prod_{s \in S} s$ are co-prime, meaning there exists $a, b \in \mathbb{Z}$ such that $ax+by =1$. Hence, the prover may send the client these $a, b$, and the client in turn can verify $(g^x)^a \cdot w_S^b = g$. Non-membership proofs can be batched as well, using a similar trick.

A good review on class group cryptography is "Buchmann, J. and Hamdy, S., 2001. A survey on IQ cryptography. In Public-Key Cryptography and Computational Number Theory (pp. 1-15)".