# How to design a Zero-Knowledge Proof of a message in a certain range? [duplicate]

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

where:

• $$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?