# How to prove knowledge of discrete logarithm in a product?

## Definitions

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.

## Problem

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.

• 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}$? Oct 23 '15 at 12:32
• 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'.
– user27950
Oct 23 '15 at 12:49
• 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... Oct 23 '15 at 13:26
• comment deleted
– user27950
Oct 23 '15 at 13:49
• 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. Oct 23 '15 at 13:55