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$.

You might find the following accumulator papers useful:

* [One-way accumulators: A decentralized alternative to digital signatures](http://www.cs.stevens.edu/~mdemare/pubs/owa.pdf)  
* [Collision-free accumulators and fail-stop signature schemes without trees](https://dl.acm.org/citation.cfm?id=1754587)
* [Cryptographic accumulators: Definitions, constructions and applications](http://www-cs.ccny.cuny.edu/~fazio/pubs/FaNi03.pdf)
* [Universal Accumulators with Efficient Nonmembership
Proofs](https://www.cs.purdue.edu/homes/ninghui/papers/accumulator_acns07.pdf)

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](http://kodu.ut.ee/~lipmaa/papers/lip12b/cl-accum.pdf)