Thanks for the layman’s explanation, I didn’t realise something like that was even possible!
What are some use cases for using it? Are they all crypto-currency related?
One use case for generating group elements with verifiably unknown discrete logs is for a commitment scheme, like a Pedersen commitment.
In a Pedersen commitment, you have two generators, let’s call them G_value and G_blinding. To commit to a value v, you choose a random blinding factor v_blinding and form the commitment C_v as
C_v = v * G_value + v_blinding * G_blinding
Later, you can publish (v, v_blinding) to open the commitment.
Pedersen commitments are really useful because they’re homomorphic: adding commitments produces a commitment to the sum of the values. So you can use them to do a limited form of computation on hidden data.
Where does the verifiable generation come in? Since G_value and G_blinding are both in the same prime-order group, there exists _some_ value r so that G_value = r * G_blinding. If someone knew this relation r, they could forge commitments, for instance
and claim that C_v is a commitment to the value v+1 instead, because knowledge of the relation r lets them “slide value” between the “basis vectors”.
So Pedersen commitments are only _computationally_ binding: finding r requires solving the discrete logarithm problem, which we assume is hard, as long as the generators G_value and G_blinding were generated through some verifiable procedure.
On the other hand, though, they’re perfectly hiding, since knowing r lets you find a valid blinding factor for _any_ value, so even an infinitely computationally powerful adversary can’t determine which value was used after the fact.
Which, for a particular real-world use case; I built a PoC for the four biggest insurance companies in my country that allowed them to query each others claims data to see if a claim has been made with another insurance company for the same car/accident/etc (apparently it’s pretty common, with a dodgy repairer involved to do this), without ever revealing the actual data and who was answering it. This would allow the companies to reduce fraud without falling afoul of data sharing prohibitions (which rightfully exist) or needing to necessarily trust one another.
We used a partial homomorphic encryption system for it, but I’m sure we could’ve used a Pederson commitment if we tweaked how we approached it.
One factor though that the PoC never truly got rid of was a semi-trusted central system. We didn’t need to though, at the time. Would’ve been neat however!
Another use is for password authenticated key exchange. The CPace protocol picks its generator using a hash to group operation. See page 13 of https://eprint.iacr.org/2018/286
hdevalence|3 years ago
In a Pedersen commitment, you have two generators, let’s call them G_value and G_blinding. To commit to a value v, you choose a random blinding factor v_blinding and form the commitment C_v as
C_v = v * G_value + v_blinding * G_blinding
Later, you can publish (v, v_blinding) to open the commitment.
Pedersen commitments are really useful because they’re homomorphic: adding commitments produces a commitment to the sum of the values. So you can use them to do a limited form of computation on hidden data.
Where does the verifiable generation come in? Since G_value and G_blinding are both in the same prime-order group, there exists _some_ value r so that G_value = r * G_blinding. If someone knew this relation r, they could forge commitments, for instance
C_v = (v+1) * G_value + (v_blinding - r) * G_blinding
and claim that C_v is a commitment to the value v+1 instead, because knowledge of the relation r lets them “slide value” between the “basis vectors”.
So Pedersen commitments are only _computationally_ binding: finding r requires solving the discrete logarithm problem, which we assume is hard, as long as the generators G_value and G_blinding were generated through some verifiable procedure.
On the other hand, though, they’re perfectly hiding, since knowing r lets you find a valid blinding factor for _any_ value, so even an infinitely computationally powerful adversary can’t determine which value was used after the fact.
girvo|3 years ago
We used a partial homomorphic encryption system for it, but I’m sure we could’ve used a Pederson commitment if we tweaked how we approached it.
One factor though that the PoC never truly got rid of was a semi-trusted central system. We didn’t need to though, at the time. Would’ve been neat however!
unknown|3 years ago
[deleted]
doomrobo|3 years ago