Given a message $m$, how can I prove that $m$ lies between 0 and 31 without revealing the message using a Sigma protocol?

The message is encrypted as:

$$c = a^{\beta} \cdot g^m ,$$


  • $a$ is the public key of the receiver,
  • $\beta$ is the secret key of the sender, and
  • $g$ is a generator of a cyclic group $G$ of prime order $q$.

I know I need to use "OR" composition and the Diffie-Hellman (DH) triples but I can't figure out how to put them together. I know how to do it for individual bits but not for an entire message. If the message was just 1 bit, the Chaum-Pedersen protocol would help me prove that either $(a, b, \frac{c}{g})$ or $(a, b, c)$ is a DH-triple, where $b = g^{\beta}$ is the prover's public key, $a$ is the receiver's public key and $c = a^{\beta} \cdot g^m$ because $c$ can be either $a^{\beta} \cdot g^0 = a^{\beta}$ or $a^{\beta} \cdot g^1 = a^{\beta} \cdot g$.

Can anyone help or give some hints?