In the RingCT paper, proof of theorem 5.1 (The Aggregate Schnorr Non-linkable ring signature is unforgeable under the discrete logarithm assumption), it is assumed by contradiction that there exists an adversary A capable of forging such ANSL's. The idea being that being able to produce such a forgery would imply solving the discrete logarithm problem for a certain public key P = xG to which A didn't know the private key x in advance.

However, in the proof it is stated: "Supposing that L11 = aG and L12 = bG, with a and b known to A, then(...)" but I don't think we can assume that from the hypothesis, or from the existence or the forgery alone, even though the L's came from the forgery. Am I reading this wrong, or is there a problem with this proof? Note that there is also already github issue on this question, but no response yet.


Github user divbit responded to the issue on Github here. To quote:

Hi, the paper states that it is a sketch of a proof (mainly it's a sketch because the things are no more efficient than the Borromean ones which are mentioned could be used on a previous page, and possibly less efficient according to the Borromean paper, in some cases (e.g. higher bases than 2 or whatever, and I guess at the time of writing the Borromean paper didn't have a proof written out, but it was sort of publicly in progress on their github, so the author didn't want to sort of steal possibly a big chunk of their paper).

Anyway, I think the point in assuming the 'a', 'b' values is that since various other bits of information are determined by the time-travel stuff (since you have to produce L1, L2 before knowing c1, c2) then at the end you need to find a scalar 's' so would need some way to get a scalar from the other bits of information which are already determined at that point). Moving sG by itself, it is easier to find an 's' when you already know a,b, so presumably if you can't find 's' with that advantage, then you can't find 's' without the advantage. But- this section of the paper hasn't been reviewed much, and it is just a sketch, so let me know if you see an error in that. BTW, the author e-mail is apparently not provided at the paper, so one might assume they are not open to correspondence, however, it's sort of publicly known from their github (shen.noether@gmx.com) which is linked on the first page of the paper, so I would assume they are open to correspondence for this type of question.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.