Proving set membership in less than $\log{N}$ bandwidth 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:


Generate a Merkle tree containing all of the items.
Give the client the Merkle root, (32 bytes) out of band.
Give the client the item, then the branch leading to the Merkle root.
The client hashes the item, then hashes each Merkle branch, starting at the bottom. 
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.
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