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
Collision-free accumulators and fail-stop signature schemes without trees: bhttps://dl.acm.org/citation.cfm?id=1754587
Cryptographic accumulators: Definitions, constructions and applications: bhttp://www-cs.ccny.cuny.edu/~fazio/pubs/FaNi03.pdf
Universal Accumulators with Efficient Nonmembership
Proofs: bhttps://www.cs.purdue.edu/homes/ninghui/papers/accumulator_acns07.pdf
The following paper proposes using a certain kind of groups called class groups to construct a strong accumulator. I am not sure how it constructs (non)membership proofs though.
Secure Accumulators from Euclidean Rings without Trusted Setup