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
- Cryptographic accumulators: Definitions, constructions and applications
- Universal Accumulators with Efficient Nonmembership Proofs
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
