1
$\begingroup$

Hi I am currently developing a research project, but it seems that my implementation of Pedersen commitment is not efficient.
I wonder if there are any efficient implementation of Pedersen commitment in c++?
Or if using things like ECC would boost the efficiency(seems number of bits could be smaller), or does anyone try the NTL(number theory library)?
TIA

EDIT: What I am using now is based on the mpz_powm() in gnu-gmp gmplib.org/manual/Integer-Exponentiation But it seems not very efficient, so I am looking to change the implementation

$\endgroup$
4
  • 2
    $\begingroup$ What implementation have you looked at that isn't efficient enough? If I told you about a different implementation, how would you judge whether that would be efficient enough for you? It's very simple to use a standard ECC library to create Pedersen commitments $\endgroup$
    – knaccc
    Commented Apr 12, 2023 at 14:51
  • 2
    $\begingroup$ Alternatively, do you need all the functionality that Pedersen commitments give you? If all you need is the basic 'commit' and 'open' functionality, well, hash based commitments give you that (and are a lot more efficient). On the other hand, if you need more (e.g. efficient zero knowledge proofs of the relationship between different commitments), well, never mind... $\endgroup$
    – poncho
    Commented Apr 12, 2023 at 15:22
  • $\begingroup$ Thanks for the reply, yes I do need the homomorphic property. And what I am using for exponentiation is the bigint powerMod in MP-SPDZ github.com/data61/MP-SPDZ/blob/master/Math/bigint.cpp to do the exponentiation g^x*h^r $\endgroup$
    – js wang
    Commented Apr 12, 2023 at 19:30
  • 1
    $\begingroup$ It is based on the mpz_powm() in gnu-gmp gmplib.org/manual/Integer-Exponentiation But it seems not very efficient, so I looking to change the implementation $\endgroup$
    – js wang
    Commented Apr 13, 2023 at 0:56

1 Answer 1

3
$\begingroup$

On efficiency, mpz_powm() of a correctly compiled GMP is next to the state of the art to compute $g^x\,h^r\bmod p$ for given values of $(p,g,h,x,r)$ of cryptographic interest. One of few possible optimizations for that same computation is using Shamir's trick aka Simultaneous Exponentiation, which AFAIK is not prepackaged in GMP. That combines the modular squarings involved in computing $g^x$ and $h^r$. Beware that mpz_powm() and the primitives it uses internally are not intended to resist side-channel attacks, which apply in some cryptographic contexts.

For further speedup, one needs to use a different cyclic group.

If that's not already done, a large speedup is possible at equal (conjectured) cryptographic strength using a Schnorr group. That selects primes $p$ of the form $p=q\,r+1$ to make $g$ and $h$ of order a prime $q$ just as big as necessary for security, e.g. 256-bit $q$, while keeping $p$ large, e.g. 2560±512 bit $p$. Compared to $p$ a safe prime, a speedup of a factor like $\log p/\log q\approx10$ is possible.

Instead of a multiplicative group modulo $p$ as above, we can use an Elliptic Curve Group over a finite field. At equal (conjectured) cryptographic strength that can involve much smaller values (256 bit vs 2560±512 bits), and thus despite added complexity a further large speedup is possible. One popular option is Curve25519. There are plenty of libraries around for that, including many that are carefully optimized for speed, and resist timing attack.

$\endgroup$
2
  • $\begingroup$ Thanks for the help, truly appreciate it. Do you mean that I could shrink the size of Pedersen commitment using ecc? e.g: I am using mod 256 bits now, is it possible to change it to mod 128 bits? $\endgroup$
    – js wang
    Commented Apr 14, 2023 at 0:53
  • 1
    $\begingroup$ @js wang: if you are computing a 256-bit commitment as $g^x\,h^r\bmod p$ (thus with 256-bit $p$), then that's horribly unsafe. 795 bit is practically breakable. ECC will give you high security with 256-bit commitment, some security with 160-bit commitment. It will be much faster at equal security. $\endgroup$
    – fgrieu
    Commented Apr 14, 2023 at 5:44

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.