Suppose I have two large safe primes $p$ and $q$, and a composite number $N=pq$. I have $G$, a large cyclic subgroup of $\mathbb{Z}^{*}_{N}$; $g$ and $h$ are generators of $G$. I commit to $x$ using a random value $r\in{_{R}\mathbb{Z}_{N}}$ as $(x,r)=g^{x}h^{r}\mod{N}$.

I have a set of valid messages $S=\{p_{1},p_{2},...,p_{m}\}$, and a message $x\in{S}$. The set $S$ is public, while $x$ is private.


I must prove knowledge of two secret integers $\mu$ and $\nu$: $$\mu=(\prod^{m}_{j=1}{p_{j}})/x$$ $$\nu=\mu r$$ using the commitment: $$C=g^{\prod^{m}_{j=1}{p_{j}}}h^{\nu}$$ I know this supposedly can be done using a combination of two Schnorr signatures. I just need a little guidance as to how to utilize those two signatures to prove knowledge of $\mu$ and $\nu$.

What I have so far

Given the definition of $\mu$ I have $C=g^{\mu x}h^{\nu}$. I also know I can express $g^{\mu x}=h^{-\nu}C$ and $h^{\nu}=g^{-(\mu x)}C$, so that gives me $$\mu x=\log_{g}(h^{-\nu}C)=\log_{g}(h^{-1})\log_{g}(\nu)+\log_{g}(C)$$ $$\nu=\log_{h}(g^{-(\mu x)}C)=\log_{h}(g^{-1})(\log_{h}(\mu)+\log_{h}(x))+\log_{h}(C)$$ I'm really not sure where to go from here, because I seem to be making it more complicated instead of less...


$$(x,r) = g^x h^r$$ $$C = (x,r)^ \mu$$

Now you have two standard proofs of knowledge.

  • $\begingroup$ So basically if I've already proven knowledge of $x$ and $r$ in a previous step, I just need to prove $g^{\prime\mu}$ and $h^{\prime\mu}$? $\endgroup$ Oct 23 '15 at 12:32
  • $\begingroup$ No, you can't, because you did not prove that both exponents are equal. But the other way, if you have proven knowledge of the discrete logs to g' and h' , then you have also proven knowledge of the representation of your commitment C, because C = g' h'. $\endgroup$
    – user27950
    Oct 23 '15 at 12:49
  • $\begingroup$ Thanks for your help and I apologize for being a bit thick. So what are the two Schnorr proofs I should use? The paper I'm working from says I only need two, and it's important that I work as close as possible to get proper timings. Just $\log_{g^{\prime}}h^{\prime}$ and $\log_{h^{\prime}}g^{\prime}$? I actually have another commitment from a previous step $C_{0}=g^{x}h^{r}$, this is about $\mu$ and $\nu$. I really wish the paper were more specific about how it applied its proofs... $\endgroup$ Oct 23 '15 at 13:26
  • $\begingroup$ comment deleted $\endgroup$
    – user27950
    Oct 23 '15 at 13:49
  • $\begingroup$ One commitment is $g^{x}h^{r}$ and the other is, for the same $g$, $h$, and $r$, $g^{\prod^{m}_{j=1}{p_{j}}}h^{\nu}$ which is the same as $g^{\mu x}h^{\mu r}$. The two commitments are not necessarily equal to one another. $\endgroup$ Oct 23 '15 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.