# Compact RSA inclusion/exclusion proofs

(Prerequisite: RSA Accumulators for Plasma Cash history reduction)

Here is a brief summary of my understandings on how compact RSA inclusion/exclusion proofs work. Correct me if I am wrong somewhere.

## Inclusion proof

To prove some prime number \alpha exists in [g...A] you provide a cofactor x which satisfies the following equation:

g^{\alpha x} \equiv A (mod N)

If A \equiv g^{Q}, then x=\frac Q \alpha

**Proof:** \alpha x=\alpha \frac {Q} \alpha=Q

(I can’t find a cofactor x if \alpha doesn’t exist in the accumulator, because in that case Q is not divisible by \alpha)

The problem is that x can get very large. We can do a trick here.

We know that any positive integer, including x, can be represented as follows:

x = B\lfloor \frac x B \rfloor + x \mod B

where B is an arbitrary positive integer.

Now let’s define:

h=g^\alpha

b=h^{\lfloor \frac x B \rfloor} \mod N

r=x \mod B

Now you can say: b^B.h^r \equiv g^{ax} (mod N)

Because:

b^B.h^r \equiv h^{\lfloor \frac x B \rfloor.B}.h^r \equiv h^{\lfloor \frac x B \rfloor.B + r} \equiv h^x \equiv g^{ax} \equiv A (mod N)

So here we can use the tuple (b, r) instead of x as the proof. The benefit of this approach is that both b < N and r < B are constant-sized.

## Exclusion proof

To prove some prime number \alpha **does not** exist in [g...A] you provide a cofactor x and remainder s (Where 0 < s < \alpha) which satisfy the following equation:

g^{\alpha x + s} \equiv A (mod N)

If A \equiv g^{Q}, then s=(Q \mod \alpha), and x=\frac {Q-s} \alpha

**Proof:** \alpha x+s=\alpha \frac {Q-s} \alpha + s=Q-s+s=Q

(I can’t find a remainder 0<s<\alpha if \alpha **does exist** in the accumulator)

Like the inclusion proofs, x can get very large. We can do the same trick here.

Again we represent cofactor x as follows:

x = B\lfloor \frac x B \rfloor + x \mod B

Now let’s say:

h=g^\alpha

b=h^{\lfloor \frac x B \rfloor} \mod N

r=x \mod B

Now you can say: b^B.h^r.g^s \equiv g^{ax+s} (mod N)

Because:

b^B.h^r.g^s \equiv h^{\lfloor \frac x B \rfloor.B}.h^r.g^s \equiv h^{\lfloor \frac x B \rfloor.B + r}.g^s \equiv h^x.g^s \equiv g^{ax}.g^s \equiv g^{ax+s} \equiv A (mod N)

So here we can use the tuple (b, r, s) instead of (x, s) as the proof. The benefit of this approach is that both b < N and r < B and s < \alpha are constant-sized.

## How to choose B?

It seems that the prover is able to create invalid inclusion/exclusion proofs if B is not set large enough.

As an example, let’s say we have 3 prime numbers \{3,5,11\} in our accumulator.

Therefore: A = g^{3*5*11} \mod N

Let’s say I want to prove that the accumulator includes prime 5.

In the old approach I would provide x=33 as the proof and the user could check the validity of my proof by checking if g^{5*33} \equiv A. I can’t prove the accumulator has prime 7 in it as I can’t find a x such that 7x=165.

**No way for me to cheat the user!**

Now suppose I am using the new approach and I want to cheat the user and say the accumulator has number 7 in it. I should give him the tuple (b, r) such that b^B.h^r \equiv A. I set B=79 on purpose.

Here we have B=79 and h=g^7

Therefore: b^B.h^r \equiv b^{79}.g^{7r}

I pick b = g^{2} and r=1

So: (g^{2})^{79}.g^{7*1} \equiv g^{165} \equiv A

**I successfully proved that 7 exists in A while it is not!**

We can force the prover to use a large, deterministic value for B depending on g and A to make it extremely hard for the prover to find an invalid (b, r) proof. Let’s use a hash function here:

B = hash(g, A)

As @gakonst mentioned, original Wesolowski’s paper states that B should be a prime number. Don’t know why yet.