0
$\begingroup$

Is the solution to a discrete logarithm a reasonable commitment scheme?

By my analysis, the following scheme is a reasonable commitment scheme: Let $p$ and $q$ be large primes such that $q∣(p−1)$, let $g$ be a generator of the order-$q$ subgroup of $Z^*_P$. Let $m$ be a value from $Z_q$, and $c=g^m\text{ mod }p$. The commitment is $c$ and to open the commitment, the sender reveals $m$.

I believe this scheme is:

  • (Perfectly?) binding: The discrete logarithm only has one solution and so the sender can't reveal another value, $m'$, such that $c= g^{m'}\text{ mod }p$

  • (Computationally?) hiding: Obviously, this scheme is not perfectly hiding. But assuming the discrete logarithm is hard, receiver or an adversary can't determine the committed message prior to reveal, so I believe this provides computational hiding.

Is my analysis of the binding & hiding properties correct? Are there other flaws not captured by hiding and binding?

$\endgroup$
1
$\begingroup$

Obviously, this scheme is not perfectly hiding. But assuming the discrete logarithm is hard, receiver or an adversary can't determine the committed message prior to reveal, so I believe this provides computational hiding.

If the receiver had no other information about $m$, then you would be correct.

On the other hand, we typically assume that he has some information; the acid test is "if the receiver knew the committed value was either $m_0$ or $m_1$, he still cannot determine which it is from the commitment".

Obviously, your approach (or, for that matter, any deterministic method) cannot fulfill that requirement; you need to include some randomness to meet this criteria.

$\endgroup$
0
$\begingroup$

and, if I'm not wrong, a possible way to add the randomness proposed by @poncho leads you to Pedersen commitments... which, by the way, have reversed properties strengths: theoretically hiding (thanks to introduced randomness) and computationally binding (because finding two couples $(randomness_{0}$,$m_{0})$ and $(randomness_{1}$,$m_{1})$ opening the same commitment implies to be able to solve DLP)

$\endgroup$

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.