0
$\begingroup$

I am writing a program using a Pedersen commitment scheme and all I'm missing is an appropriate length for my prime $p$. I have heard that a length of $2^{80}$ is ok, is that correct?

$\endgroup$
3
$\begingroup$

If you mean a prime in the neighborhood of $2^{80}$, well, that is incorrect. A prime that small will allow someone to commit to a value, and then reveal another one.

A Pederson commitment is a value $g^x h^r \bmod p$, where $g$, $h$ and $p$ are public values, $x$ is the value being committed to, and $r$ is a random value. To reveal the commitment, you publish $x$ and $r$.

To reveal a second value $x'$, one way to do this is compute a value $r'$ with $g^x h^r \equiv g^{x'} h^{r'}$, this is equivalent to $h^{r'} \equiv c$, where the attacker can compute $c \equiv g^{x - x'}h^{r}$. If the attacker can solve his discrete logarithm to the base $h$, we can recover $r'$ and reveal his second value $x'$.

Now, for primes of 80 bits in length, this discrete logarithm is easily solved. To make it impractical, you need a prime at least 1024 bits in length, preferably at least 2048 bits.

On the other hand, if you mean a prime that's $2^{80}$ bits in length, that is, around $2^{2^{80}}$, well, you'll find that is an impractically large prime to work with; computing $g^xh^r$ would be infeasible.

$\endgroup$
0
$\begingroup$

One would put a requirement for the group first, rather than one for just prime $p$. That is, require that taking a logarithm (calculate an index) to be hard in this group. For a multiplicative modulo-$p$ group, this would also require choosing a generator of an order $q$ such that $q$ is a prime, is large enough, and divides $p-1$. Alternatively, it would allow for a group of points on an elliptic curve.

$\endgroup$
  • $\begingroup$ One requirement would be that $g$ and $h$ be a part of the same subgroup (otherwise, the commitee can deduce some information on $x$). Given that it's also important that no one know the discrete log $\log_g h$, it would appear wise to select $(p-1)/2$ prime (and select $g$ and $h$ to be random quadratic residues); alternatively, work in an elliptic curve with a prime order. $\endgroup$ – poncho Apr 19 '15 at 20:47
  • $\begingroup$ @poncho Yes, $g$ and $p$ must be in the same subgroup for unconditional indistinguishability of commitment scheme to hold. One could use a subgroup of order $q$ such that $q$ is another large prime and $q | (p-1)$. My point is, there's more to implement than just pick a prime of an appropriate length. $\endgroup$ – Vadym Fedyukovych Apr 21 '15 at 8:28

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.