Issue with proof of unforgeability of ASNL #4

Closed
RandomRun opened this Issue Oct 22, 2016 · 10 comments

Comments

Projects
None yet
3 participants
@RandomRun

In the proof it is assumed, by contradiction, that there exists an adversary A that is able to forge the ASNL, but later on something much stronger is assumed, namely that A somehow knows the discrete logs of L-values to be numbers a and b. I don't see how that could be implied by A's ability to produce a forged signature. Isn't it possible that A has a way to produce L- and s-values that form a valid signature without knowing the discrete log of the L's? If so, the proof shouldn't use the numbers a and b.

@ghost

This comment has been minimized.

Show comment
Hide comment
@ghost

ghost Oct 25, 2016

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 (edit: non-standard terminology from the Borromean paper) one-way nature of the hash (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.

ghost commented Oct 25, 2016

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 (edit: non-standard terminology from the Borromean paper) one-way nature of the hash (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.

@ghost

This comment has been minimized.

Show comment
Hide comment
@ghost

ghost Oct 26, 2016

2p: Since I'm no longer actively working on this stuff- the Monero community could try and get someone to audit- off the top of my head there is NCC crypto services or coinspect. For example, I think Zcash recently did an audit with the first of the two. I can name bugs that have been found in almost every big crypto thing that I can think of off the top of my head, so I wouldn't be too unsurprised if I wasn't immune.

ghost commented Oct 26, 2016

2p: Since I'm no longer actively working on this stuff- the Monero community could try and get someone to audit- off the top of my head there is NCC crypto services or coinspect. For example, I think Zcash recently did an audit with the first of the two. I can name bugs that have been found in almost every big crypto thing that I can think of off the top of my head, so I wouldn't be too unsurprised if I wasn't immune.

@ghost

This comment has been minimized.

Show comment
Hide comment
@ghost

ghost Nov 1, 2016

I previously noted that there was a flaw in my previous comment- and that one needs to commit to the L1 values. After working this change through on paper, I realized that doing this essentially reduces to the Borromean sigs in any case (after replacing the sum with a hash of the L1)

ghost commented Nov 1, 2016

I previously noted that there was a flaw in my previous comment- and that one needs to commit to the L1 values. After working this change through on paper, I realized that doing this essentially reduces to the Borromean sigs in any case (after replacing the sum with a hash of the L1)

@luigi1111 luigi1111 referenced this issue in monero-project/monero Dec 7, 2016

Merged

Borrrrrro #1413

@ghost

This comment has been minimized.

Show comment
Hide comment
@ghost

ghost Jan 2, 2017

It's probably worth noting, that shortly after this thread first appeared, there was a (I think reasonable) offer setup for a crypto audit between one of the organizations in the previous comment, and Riccardo / Othe of the monero project. I'm not sure whether the monero guys followed through, but it would be nice to hear the results of that.

ghost commented Jan 2, 2017

It's probably worth noting, that shortly after this thread first appeared, there was a (I think reasonable) offer setup for a crypto audit between one of the organizations in the previous comment, and Riccardo / Othe of the monero project. I'm not sure whether the monero guys followed through, but it would be nice to hear the results of that.

@ghost

This comment has been minimized.

Show comment
Hide comment
@ghost

ghost Jan 4, 2017

I would like to point out that there is now a thread claiming I completed a 'deep code review' on reddit. I tried to comment there and point out this is untrue (I fixed a small piece of the borromean sigs, and compared the hash to point function with OWS recent implementation), but the comment got shadow-deleted or something.

ghost commented Jan 4, 2017

I would like to point out that there is now a thread claiming I completed a 'deep code review' on reddit. I tried to comment there and point out this is untrue (I fixed a small piece of the borromean sigs, and compared the hash to point function with OWS recent implementation), but the comment got shadow-deleted or something.

@RandomRun

This comment has been minimized.

Show comment
Hide comment
@RandomRun

RandomRun Jan 6, 2017

Hi Shen. Thank you for setting the record straight on this thread. Could you please provide the link to the Reddit thread and your comment, if possible? I couldn't find it there. If something like that was deliberately deleted that is very concerning on its own right...

Hi Shen. Thank you for setting the record straight on this thread. Could you please provide the link to the Reddit thread and your comment, if possible? I couldn't find it there. If something like that was deliberately deleted that is very concerning on its own right...

@fluffypony

This comment has been minimized.

Show comment
Hide comment
@fluffypony

fluffypony Jan 6, 2017

Collaborator

It was censored by Theymos! Quick everyone, let's head to /r/btc!

/s

Collaborator

fluffypony commented Jan 6, 2017

It was censored by Theymos! Quick everyone, let's head to /r/btc!

/s

@taushet

This comment has been minimized.

Show comment
Hide comment
@taushet

taushet Jan 6, 2017

...so why was that comment deleted? @fluffypony

taushet commented Jan 6, 2017

...so why was that comment deleted? @fluffypony

@fluffypony

This comment has been minimized.

Show comment
Hide comment
@fluffypony

fluffypony Jan 6, 2017

Collaborator

@taushet because the comment was so out of bounds, and Shen hadn't contacted myself or othe privately, that it was a safe assumption that his account had been compromised. At this stage I'm still assuming his account has been compromised and am disregarding anything he has said publicly.

Collaborator

fluffypony commented Jan 6, 2017

@taushet because the comment was so out of bounds, and Shen hadn't contacted myself or othe privately, that it was a safe assumption that his account had been compromised. At this stage I'm still assuming his account has been compromised and am disregarding anything he has said publicly.

@fluffypony fluffypony closed this Jan 6, 2017

fluffypony pushed a commit that referenced this issue Sep 16, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment