Should Monero use ElGamal commitments instead of Pedersen commitments?

Question

Following on from the Q/A regarding "perfectly hiding and computationally binding" commitments, it is mentioned ElGamal commitments can be used to flip the commitment properties to become "perfectly binding and computationally hiding". How does this work and why doesn't Monero prefer this?

Answer 1

Let's first recap the concept of input and output spaces. In our Pedersen commitments, we are perfectly hidden because the input space is larger than the output space - we have a many-to-one relationship. For our binding, the spaces are the same size, the relationship is one-to-one, so can only be computationally bound. The inverse of these relationships flips the properties of the scheme. The way ElGamal commitments flip these properties is by publishing an extra point in the commitment (so the commitment now consists of 2 points). As an example:

C1 = xG + aH
C2 = xH
C = (C1, C2)

Here, our input space is the tuple x,a (two 253 bit scalars) and our output space is the same size, a tuple of two points C1,C2 (two 253 bit points). This is guaranteed distinct because of the mapping of x to xH and the fact there can only be one input tuple that maps to a single output tuple. It is only computationally hidden because x can theoretically be extracted from C2 and then xG can be subtracted from C1 leaving aH, from which a can be theoretically extracted. Thus a is computationally hidden.

Importantly, it is perfectly bound because an adversary cannot open a commitment to a different amount a to that which was originally committed. Or in layman terms, change a, x will have to change, verification of the original commitment fails. Or to put another way, changing a or x, one cannot construct a matching commitment to that of the original commitment. It's perfectly bound and computationally hidden.

So there is nothing stopping us switch to using perfectly bound and computationally hidden commitments. However, these come with a serious drawback, size. In a Monero transaction, there are a lot of commitments (they are used in both the ring signatures and range-proofs), and ElGamal commitments require an extra 32 bytes each (the extra point). So given that both properties are important to not be broken (the hiding of amounts and the binding of the commitments), and that the computationally strength is considered sufficiently strong for the foreseeable future (we are some way off being able to solve the discrete logarithm problem), and that even when the DLP can be effectively solved, there would be far more pressing problems to face. Therefore deciding on whether to use computationally/perfectly hidden/bound commitments right now, boils down to other factors, and in our case this is predominantly the size factor.

Therefore, it's fine for now to use either scheme, though preferable to use the smaller of the two. By the time the DLP is solvable, and we have implemented a replacement, all past Pedersen committed amounts will still remain hidden, but there will have to be a new binding & hiding scheme to protect against hidden inflation. Which brings us to another subtle reason why the Pedersen commitments (perfectly hiding and computationally binding) are preferable. Assuming a replacement is found before the DLP is easily solvable, a migration to a new hiding and binding scheme could be done such that the older, weakened, bound commitments could be phased out (e.g. marked as untrusted from a certain point in time) and only the newer scheme trusted for subsequent transactions. Flipping the scenario, if we used computationally hidden and perfectly bound commitments now, and the DLP assumption becomes broken, all past amounts would become known with no migration plan possible that could be used to avert this. And of course in the worst case scenario, of not having a replacement to the broken DLP assumption (regardless of perfectly/computationally hidden/bound commitments), there are far more problems than just Monero commitments! Everyone's coins for any cryptocurrency could be stolen for one thing (e.g. it would be possible to obtain the private wallet key for a given public wallet key). SSH/PGP/SSL, all breakable. Thus, one can tend to assume we will have alternative cryptographic schemes before the DLP is easily solvable - it's more than just our silly [tic] cryptocurrencies that would be affected.

Hopefully these two posts have helped educate that the phrase "perfectly hiding and computationally binding" is not some weakness in Monero, but rather refers to specific properties of commitment schemes. No scheme can be both perfectly binding and hiding and the computational strength is as strong as we rely on for all other modern day cryptography applications.

Answer 2

even if the topic is two years old and @jtgrassie's answer is very complete, I think it's worth adding a subtle point in "Pedersen VS ElGamal commitments in Monero".

No doubt Monero uses Pedersen which we can say it's theoretically/perfectly hiding and computationally/imperfectly binding. However in the broader context of RingCT (where Pedersen Commitments are used), given a destination-amount commitment defined as:

    C = yG + bH

(where y is the blinding factor and b the amount) the protocol mandates that:

(1) y = H("commitment_mask" | H(rV,t)) = H("commitment_mask" | H(vR,t))

(where t is the output number, (r,R) is the transaction keys couple and (v,V) is the view keys couple)

and the trasaction contains the field:

(2) amount = b XOR H("amount" | H(rV,t)) = b XOR H("amount" | H(vR,t))

Both (1) and (2) could be calculated if DLP was broken, the only weak-supplemental-protection being that V isn't on-chain (nevertheless it's public, being part of payee address); R instead is written in extra field of transaction. In that case, it easy to see that it enough to invert (2) (no need to use (1)) to get:

    b = amount XOR H("amount" | H(rV,t)) = amount XOR H("amount" | H(vR,t))

so we could say, IMHO, that RingCT as a whole is computationally hiding even if Pedersen is theoretically hiding.

And, funny enough, imposing (1) for the blinding factor y means constraining it to:

    H("commitment_mask" | H(rV,t)) = H("commitment_mask" | H(vR,t))

...and adding a specific commit to constrain the blinding factor is the way by which Pedersen commitments are transformed in ElGamal ones

My2cents ;)