There is a much more concise explanation than in the linked post: in Ristretto, the encoding of group elements was constructed so that the encoding of the identity (zero) element of the group is the all-zero byte string. So it’s not surprising that the all-zero byte string has a known private key: it’s the all-zero secret key.
This aspect of the encoding makes it very easy to check whether a provided group element is the identity element, because “zero means zero”.
What the questioner seems to be looking for is a way to generate “burn addresses”, public keys with the property that everyone can be sure that no one else knows the secret key to. This is actually kind of hard: if I just give you a public key, how do you know I didn’t generate it from a secret key I know?
The correct answer to this “nothing-up-my-sleeve” problem is to have a group-valued hash function, which Ristretto provides. Then public keys can be specified as the outputs of the hash function.
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
Its OK it was just like reading ‘car’ and ‘automobile’ in the same sentence and not being quite sure if that was what was actually meant. Otherwise it was a very clear explanation!
Just out of curiosity: is a similar problem (generate a valid public key that surely nobody including myself can know the private key of) solvable for RSA?
This is a great question. To rephrase: is it possible to come up with an RSA modulus that even you don't know the factorization of?
The answer, I believe, is we have no way of doing that so far. The closest thing that exists is "multiparty" or "distributed" generation of an RSA modulus. Roughly, in the two party case of Alice and Bob, this means Alice picks some pair of numbers (P1, Q1) and Bob similarly picks some (P2, Q2). Then, Alice and Bob engage in some secure multiparty computation protocol whereby they obliviously a) check P1+P2 and Q1+Q2 are prime, and b) if so, output N=(P1+P2)(Q1+Q2) to both Alice and Bob.
At the end of the protocol (after repeating enough times that it succeeds), both parties have derived an N whose factorization they don't know.
I don't know much about this area of study, but searching multiparty RSA modulus generation should bring up relevant papers.
That problem can't be solvable in any context. There's no way to rule out the possibility that someone else in the world knows your mathematical secret.
Let’s try it this way: what if two people, unlikely as it may be, generate the same key pair? Two people know the private key, and factoring is still hard.
There is a much more concise explanation than in the linked post: in Ristretto, the encoding of group elements was constructed so that the encoding of the identity (zero) element of the group is the all-zero byte string. So it’s not surprising that the all-zero byte string has a known private key: it’s the all-zero secret key.
This aspect of the encoding makes it very easy to check whether a provided group element is the identity element, because “zero means zero”.
What the questioner seems to be looking for is a way to generate “burn addresses”, public keys with the property that everyone can be sure that no one else knows the secret key to. This is actually kind of hard: if I just give you a public key, how do you know I didn’t generate it from a secret key I know?
The correct answer to this “nothing-up-my-sleeve” problem is to have a group-valued hash function, which Ristretto provides. Then public keys can be specified as the outputs of the hash function.