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