Return to Answer

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

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

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

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

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

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