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?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Apr 19 '15 at 12:25
-
$\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
