0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ r is directly sent without entering any equation. I suppose this is wrong. $\endgroup$
    – user27950
    Jul 12 '18 at 3:59
  • 1
    $\begingroup$ 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$. $\endgroup$ Jul 12 '18 at 5:57
2
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$ Jul 12 '18 at 13:58
  • $\begingroup$ 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? $\endgroup$ Jul 12 '18 at 14:08
  • $\begingroup$ @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. $\endgroup$ Jul 12 '18 at 14:17
  • $\begingroup$ thanks a lot for the correction and for answered my questions. $\endgroup$ Jul 12 '18 at 15:12

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.