# Public-key generation - primes reuse

Given the following Trap-door Commitment scheme

• Secret key receiver: $x_B \in_u Z_q$
• Public key receiver: $y_B = g^{x_B} \mod p$

Here, $p=q*k+1$ for two primes $p,q$ and $k \in Z$. And $g$ is the generator of subgrup $G_q$ of $Z_p^{*}$, of order $q$.

To the sender commit $w \in Z_q$, he selects $r \in_u Z_q$, the commitment is $c=g^wy_B^r \mod p$. To open a commitment, he sends $(w,r)$.

My question is: if I want create milions of theses public-secret keys for milions of different senders, could I reuse $p,q$?

• r is directly sent without entering any equation. I suppose this is wrong. – user27950 Jul 12 '18 at 3:59
• Is this meant to be Pedersen commitment, where the commitment to $w$ is $c=g^w y_B^r\bmod p$ for random $r$, and $(w,r)$ is what the sender must show to reveal? If so, yes: you can reuse the group as long as each recipient $B$ has their own key pair $(x_B,y_B=g^{x_B}\bmod p)$. Whoever can find $w\ne w'$, $r\ne r'$ with $g^w y_B^r\equiv g^{w'}y_B^{r'}\pmod p$ can find $x_B\equiv(w'-w)(r-r')^{-1}\pmod{p-1}$, so breaking this is at least as hard as computing discrete logs. Of course, you need $p\approx2^{2048}$ for security against index calculus and $q\approx2^{256}$ for security against $\rho$. – Squeamish Ossifrage Jul 12 '18 at 5:57

Fix a group $G$ of large prime order $q$. Fix a generator $g \in G$. For a public key $h \in G$ other than the identity, a message $m \in \mathbb Z/q\mathbb Z$, and randomization $r \in \mathbb Z/q\mathbb Z$, define the commitment $c = g^m h^r$.

Fix $h$. Suppose $r$ is uniformly distributed in $\mathbb Z/q\mathbb Z$. Then $h^r$ is uniformly distributed in $G$, since $G$ has prime order so $h$ is a generator, and so as long as $x$ is independent of $r$, $c = g^m h^r$ is also uniformly distributed. Hence an adversary given the commitment $c$ learns nothing about the message $m$, no matter what the distribution on $m$ is—the commitment is information-theoretically hiding.

Suppose you have a random algorithm $A\colon G \to (\mathbb Z/q\mathbb Z)^4$ that, given $h$, computes $(m, r, m', r') = A(h)$ with $m \ne m'$ such that $g^m h^r = g^{m'} h^{r'}$ with high probability. Then necessarily $r \ne r'$, and $g^{(m - m')(r' - r)^{-1}} = h$, i.e. $(m - m')(r' - r)^{-1}$ is the discrete log of $h$ in base $g$, so that we can solve the discrete log problem in $G$ with high probability and negligible additional cost by the random algorithm $A'(h) = (m - m')(r' - r)^{-1} \bmod q$ where $(m, r, m', r') = A(h)$. Thus, an algorithm that can break the commitment can be used as a subroutine in an algorithm to compute discrete logs with high probability at negligible additional cost—the commitment is computationally binding.

Of course, whoever knows $x$ such that $h = g^x$ can break commitments by computing $r' = (m - m') x^{-1} + r$ for any messages $m$ and $m'$ of their choice. So the group should be chosen to make it nigh impossible for anyone to compute $x = \log_g h$, but just like in finite-field Diffie–Hellman or Schnorr signatures or DSA, the same group can be used by many key pairs $(x, g^x)$.

What group should we use as $G$? To thwart generic discrete log algorithms like Pollard's $\rho$, $q$ must be at least $2^{256}$ or so. The two obvious choices are a Schnorr group, i.e. an order-$q$ subgroup of $(\mathbb Z/p\mathbb Z)^\times$ where $p$ must be at least $2^{2048}$ or so to thwart index calculus, or a group on some elliptic curve $E/k$ over some field $k$ of at least $2^{256}$ elements or so. Although the adversary's powers are somewhat more limited than in the Diffie–Hellman setting where they learn $\gamma^x$ for any $\gamma$ of their choice, there are many more criteria than these: for a finite field, $p$ must be chosen to resist the SNFS; for an elliptic curve, there is a host of things to worry about.

Yes you can reuse $p$ and $q$, i.e. you can have multiple key pairs using the same group, as long as the secrect keys $x_B$'s are chosen independently at random.

Essentially, what you are asking is this, given $y_B=g^{x_B} \in G$ where $G$ is the order-$q$ subgroup of $Z_p^*$ and $x_B \in Z_q$, and additional $y_i =g^{x_i} \in G$ for polynomial many $y_i$'s, is the trapdoor commitment is still secure?

Some more details:

The security of commitment requires two things: hiding and binding.

For the hiding property, note that your commitment scheme is perfectly (information theoretically) hiding, thus a commitment $g^w{y_B}^r$ is uniformly random and the uniformity comes from the fact $r$ is uniformly random. This also means the distribution of $g^w{y_B}^r$ is independent of all $y_i$'s the adversary can get, and those $y_i$'s provide no advantage for the adversary to learn $w$. So the hiding property holds.

For the binding property, you can reduce it to the DL problem such that if an adversary $A$ can break the binding property of your scheme, then we can use it to break the DL problem. Suppose a DL adversary who has $y=g^x \in G$ and needs to find $x$, he can choose random $x_i,x_2,\ldots,x_n \in Z_q$ and compute $y_1=g^{x_1},y_2=g^{x_2},\ldots,y_n=g^{x_n}$ and invoke $A$ with $y$ and the additional $y_i$'s. The adversary $A$ can break the binding property means with a non-negligible probability, $A$ can find two different pairs $(m,r)$ and $(m',r')$ such that $g^my^r=g^{m'}y^{r'}$. If $A$ returns such a pair, it must hold that $m+xr=m'+xr'$, and $B$ can compute $x=\frac{m'-m}{r-r'}$, thus solve the DL problem. Since we assume the DL problem is hard, such $A$ does not exist. Therefore the binding property also holds (as Squeamish Ossifrage also said in the comment).

• the authors here link, pg. 147, say the commitment scheme is due G. Brassard, D. Chaum. Crepeau, Minimum Disclosure Proofs of Knowledge,Jourrial of Computer and System Sciences, Vol. 37, No. 2 , Oct. 1988, pp. 156-189. Anyway, you answered my question. Thanks you very much! – McFly Jul 12 '18 at 13:58
• BTW, if we can reuse $p,q$, it could be hard to generate 1, 10 or 100 millions of public-secret pairs keys in a shot: few minutes... less then 5 minuttes... Is the calc $y_B = g^{x_B} \mod p$ a concern? – McFly Jul 12 '18 at 14:08
• @McFly I've edited your question to correct the commitment formula (from $c=g^wy_B \mod p$ to $c=g^wy_B^r \mod p$). For public key generation, depends on your security parameter, e.g. if it 1024 bit $p$, you can generates $10^3$ - $10^5$ $g^{x_B}$ per second, depending on the speed of your computer. You might need to parallelize the process if you want to generate many in a short period of time. – Changyu Dong Jul 12 '18 at 14:17
• thanks a lot for the correction and for answered my questions. – McFly Jul 12 '18 at 15:12