4 ms·
I’m a coauthor of Ristretto. There is a much more concise explanation than in the linked post: in Ristretto, the encoding of group elements was constructed so
by hdevalence 4y ago
I’m a coauthor of Ristretto.
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.
- bondarchuk 4y agoPractical solution: just use all ones instead.
- patrakov 4y agoJust 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?
- thaumasiotes 4y agoThat 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.
- deleted 4y ago[deleted]
- 3np 4y agoThis reasoning doesn't hold if we're still operating within the base assumptions of RSA (and if we're not, no private key is secure)
- jagged-chisel 4y agoLet’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.
- hgsgm 4y ago"someone might guess a key by luck" has always been an accepted risk of RSA or any key-based encryption system. It's an "act of God".
- doomrobo 4y agoThis 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.
- etna_ramequin 4y agoThanks 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?
- hdevalence 4y agoOne 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 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 4y agoWhich, 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!
- nailer 4y ago> So it’s not surprising that the all-zero byte string has a known private key: it’s the all-zero secret key. Is this sentence a mistake? A private key is a secret key.
- hgsgm 4y agoIt's a use of a synonym to make the writing more pleasant to read.
- nailer 4y agoOk. It’s better to use consistent terminology rather than move between two different technical terms.
- hdevalence 4y agoI wrote it while waiting to board in the airport, sorry
- nailer 4y agoIts 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!
- anothernewdude 4y agoWhy is an image viewer using PKI?