2
$\begingroup$

Question:

Consider the following commitment scheme:
Public parameters: large primes $q$ and $p$ such that $p = 2\cdot q + 1$, and two generators $g, g'$ of a $q$-order subgroup of $\mathbb Z_p^*$.

  • Alice commits to $t$ in $\mathbb Z_q$ by uniformly picking $r$ from $\mathbb Z_q$, and sending $g^t \cdot g'^r$.
  • She opens the commitment by sending $s$ and $r$.
  • Suppose both parties are poly-time bounded.
  • If Bob gets to pick the public parameters, can he somehow cheat? (Alice verifies the parameters in poly time)

Attempted solution:

If he can cheat, I think Bob needs to choose $q$ and $p$ in a smart way, because even if he picks $g$ and $g'$ to be equal, he is stuck with computing discrete log, which isn't possible in poly-time.

I thought maybe Bob can pick $q$ to be a Carmichael number, then Alice will think it is actually prime (by checking with Miller–Rabin algorithm).

Two problem I ran into with this:

  1. I'm not sure how much it helps him to solve the problem — he can solve it modulo the prime factors of $q$ and use CRT, but if the factors aren't small enough its still exponential.
  2. Maybe there is no prime $p$ such that $p=2q+1$ for a Carmichael number $q$.

I think my solution fails because of the problems above... would appreciate a pointer in the right direction.

Improve this question
$\endgroup$
2
  • $\begingroup$ Note that for Carmichael numbers, all numbers that are relatively prime are Fermat liars, but not necessarily strong liars, so the Miller-Rabin test is still likely to pick them out as composite numbers. $\endgroup$
    – knbk
    Commented Dec 31, 2017 at 14:40
  • $\begingroup$ Yeah Alice can easily cheat if she picks the parameters, but about Bob I'm not sure. I think the point is to let Alice pick 1 generator (maybe q and p as well since it doesn't seem to help her) and have Bob pick the other, but I'm still not sure how Bob can cheat, even if he picks all the parameters. $\endgroup$
    – Bar
    Commented Dec 31, 2017 at 15:24

1 Answer 1

Reset to default
2
$\begingroup$

Assuming that Alice verifies that:

  • $p = 2q + 1$ with $p, q$ prime
  • $g, g'$ are generators of order $q$

then Bob cannot cheat.

First note that $g$ and $g'$ generate the same subgroup, such that $g' = g^\alpha$ for some integer $\alpha$. Given a signature value $s = g^t g'^r = g^{t + \alpha r}$, there are $q$ possible messages $t' \bmod q$, and for every $t'$ there exists a unique value $r' \bmod q$ such that

$$r' \equiv \frac{t - t' + \alpha r}{\alpha} \pmod q$$

and:

$$g^tg'^r \equiv g^{t'}g'^{r'} \pmod p$$

Without further knowledge of $t$ or $r$, every pair $(t', r')$ that satisfies the signature is equally likely. So if Bob only knows $(p, q, g, g', s)$, he cannot deduce any information from the signature.

Note that if Alice knows $\alpha$, she can cheat by calculating $r'$ for any message $t'$ and revealing $(t', r')$ instead of $(t, r)$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Clear, thanks. Is it always true that two generators of the same order generate the same subgroup? $\endgroup$
    – Bar
    Commented Dec 31, 2017 at 16:23
  • $\begingroup$ @Gray Not for groups in general (e.g. $\langle 3 \rangle$ and $\langle 5 \rangle$ in $\mathbb{Z}_8^*$), but in the case that $p = 2q+1$, the only subgroup of order $q$ is the subgroup containing all quadratic residues $\bmod p$. $\endgroup$
    – knbk
    Commented Dec 31, 2017 at 16:37
  • $\begingroup$ To complement this (nice) answer, note that this commitment scheme corresponds to the Pedersen commitment scheme, and stating that Bob cannot cheat is equivalent to the following statement: the parameters of the scheme are publicly verifiable, and the commitment scheme is perfectly hiding. Note that this implies that Bob could not cheat even if he was computationally unbounded. $\endgroup$
    – Geoffroy Couteau
    Commented Dec 31, 2017 at 16:53
  • $\begingroup$ @Gray: "Is it always true that two generators of the same order generate the same subgroup?"; it is always true for $\mathbb{Z}_p^*$ for $p$ prime (but, as Gray mentioned, it is not necessarily true if we consider composite $p$) $\endgroup$
    – poncho
    Commented Dec 31, 2017 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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