You mean if you know all the nonces? Sure, you could identify which nonces correspond to signature elements and recover the private key, akin to a Schnorr nonce leak

At that point, I suppose you either have a terrible RNG or the signing device is compromised

yeah this is normal schnorr stuff

get the nonce get the key same as it ever was

does monero use ed25519 for everything or are there other curves/etc used in various places?

everything crypto related in the blockchain. can't speak to any communication stuff

yes, that is what I meant. thanks

sarang did you see my question? I can't see the chat history

To anyone else just joining: bottom of page 9 on cryptonote.org/whitepaper.pdf, If output private key x used to close the ring (r=q-cx mod l) was never exposed, but someone could access all of the other variables at the bottom of page 9, could they reverse engineer x

Could they just move the equation r =q-cx mod l around , given that they know all of r,q,c

suraeNoether

peach34: i am pretty sure that both suraeNoether and sarang are not in GMT/Europe timezone, so may not be online for a few hours yet.

I thought so. Thanks

peach34: out of curiosity, why can you not disclose what cryptocurrency you work for? seems slightly at odds with the open source nature of the sector/field.

Just company rules.

so its a company rule that you can't tell anybody who you work for?

The field is not really that open source as you'd think either. Most of the best blockchain projects aren't on coinmarketcap.

Not in an informal setting, on a chatroom

i understand that there are deployments of the technology that do not have a market traded token

i am not sure how a research related cryptography IRC channel is informal.

its not like the discussion is jokes and memes, is it?

<peach34> The field is not really that open source as you'd think either. Most of the best blockchain projects aren't on coinmarketcap. ---- I guess it depends how you define best. best to whom? if it's a super blockchain project being worked on in secrecy, by some company, my spidey sense somehow tells me that the financial privacy of the masses is probably not a design goal

The ones actually delivering value

How many on CMC have delivered anything that benefits anyone in any substantial way?

bitcoin, ethereum, monero

at the very least

There are some that have

99% of the rest is meaningless

I agree with monero and Eth but not really BTC

What is BTC doing for anyone?

well, it started this whole thing, and for many of us early birds it allowed us to transact outside the mainstream system until viable alternatives (monero) were ready

I appreciate it in that sense Kay

Of course I do

even today, since it has (sadly) wider impact than monero, it can be used for many things.. flights, hotels, servers, hosting, vpns, domains.. even pizzas, yes

xmr.to comes to mind

and then there's the whole ongoing research on lightning network, and then the fact that for most non-blockchain/crypto people, when they hear about the industry, it's usually bitcoin, so that attracts more people, some of which hopefully in due time realize the perilous lack of privacy there

not to say that there isn't interesting tech that could come from a corporate environment, don't get me wrong, but in my mind no matter how cool the tech might be, these will inevitable be used as tools for more control, not less, and therefore seem to run counter to the ideals of this whole thing

I'd rather pay for those things with fiat or XMR

i bet it's very nice for banks to use ripple or stellar or whatever they're planning to use these days, but then the bank is completely in control still, there is zero privacy, accounts can be shut down with the click of a very regulated button .. that's great, for the banker

not for me

Yeah, BTC is a lighthouse for the newcomers

<peach34> I'd rather pay for those things with fiat or XMR --> impossible to disagree there

xmr.to is a (great) hack to more or less hide the fact that if bitcoin adoption is nearly nonexistent, then monero adoption is a tiny speck of dust

it works, for now, but it would be unwise to exclusively rely on it forever ..

Different projects have their place. Blockchain is being used in supply chain management, medicine, national security etc

so I hear, but none of these alternative use cases inspire any confidence (to me).. that could also be because I'm mostly interested in digital cash though

happy to see research into such things though, don't get me wrong.. more power to everyone if it works as people seem to want it to

blocks without work i presume

peach34: if you knew all the nonces for that construction, you could trivially recover the key (just like you could in a Schnorr signature)

sarang I thought as much. But if say the attacker got everything apart from q_s, and x at the bottom of p9 on cryptonote.org/whitepaper.pdf

We could write r = q-cx as r = q' - c' (where we've 'divided' by c for the primed values)

sorry I meant r' = q' -x

I don't really under what circumstances that could happen

If an attacked never gets hold of q, x, there are l solutions for x that satisfy the equation

FWIW knowing all nonces except the signing-index nonce leaks the signing index (if such a weird leak could happen)

Correct, but here I'm interested in x only

I don't think I'm fully following you

Lets say I don't care if an attacker knows the signing index

Sure, they only want the signing key

correct

If they were to get everything except q_s and x, could they derive x from the other variables/values

I think not, because we're closing the loop with r = q -cx, if they only know r,c, but not q_s and x, we can rewrite r = q -cx as r' = q'-x

by dividing through by the known quantity c

beings as q' and x are unknown, this equation has L solutions where L is the size of the finite field

Yes, this reduces to the same nonce-based problem underlying Schnorr

That is what I thought

And provided your scalars are chosen well, guessing the nonce is just as hard as guessing the private key

So as long as q_s and x are kept secret ( and therefore the calculation of r = q - cx), an attacker cannot recover x?

In fact, you're computationally better off just guess-and-checking the private key

This assumes no external information, uniformly random selection of nonces and private key, etc.

I also don't recall what signer ambiguity model that construction uses

So you may or may not have to consider whether non-signing ring members are corrupted

Yep exactly that

'guessing the nonce is just as hard as guessing the private key'

exactly, as I said r' = q' - x has L solutions

^ provided they were both chosen uniformly at random

The method for generating nonces should be just as good as that for generating private keys, which may not be the case in practice

^ just using the random32_unbiased function in Monero

random scalar{random32_unbiased()}

Also, the inability to determine x without q_s, this applies to all ringsizes (including =1) right

Parenthetically, if it matters here, ring size 1 is impossible with ringct. It can only be done with original ring signatures.

I'm just considering original sigs

For the originals, presumably x still can't be computed without q_s for ringsize =1

correct

Thanks a lot

`n=1` is effectively a reduction to a Schnorr signature with the added linear combination for key image construction

Research meeting today at 17:00 UTC (about an hour from now)

howdy everyone

Hey

good morning, monerians

okay well let's get going I guess

Meeting agenda here:

to begin with the obvious: GREETINGS!

This is our weekly MRL research meeting, where we discuss the progress (or lack thereof) from the previous week, papers we are interested in reading, projects we are intersted in working on, and we hear from whichever MRL contributors happen to be online at the moment

A lot of thought has been going into the CLSAG security model lately, with a few different ideas floating around to define linkable anonymity in a way that makes sense, or is common to other work

suraeNoether: you had been looking into corruption oracles that would be compatible with the Backes definition

and I had been looking at modifications to Backes that would not require such an oracle

woops, internet hiccup

okay, so since no one else appears to be here, let's chat CLSAG

so, the reviewers got back to us with some comments on CLSAG: we used a novel definition of anonymity/ambiguity because previous definitions lacked some of what we were looking for, and one of the reveiwers pointed us to a paper we weren't aware of at the time when we wrote the paper

this paper has a banging definition of linkable anonymity, and so we began adapting the proof

unfortunately, the way that security proofs in crypto often go is something like this: "If a solver of this problem X here exists, I am going to put that algorithm into a blackbox and turn it into Y, some solver of a cryptographically hard problem."

that way, any problem we assume to be cryptographically hard can be relied upon as a foundation of hardness: if i can show that an algorithm that can break linkable anonymity exists and that implies that algorithm can also break the discrete logarithm problem, then i'm good to go because the DL problem is thought to be hard

unfortunately, the bangin definition of linkability in Backes (here: eprint.iacr.org/2019/196.pdf page 25)

this definition appeared to have a contradiction with our proof method: the black box algorithm X needs to be able to corrupt keys, and so the algorihtm Y has to be able to simulate key corruption, and the specific order in which things were occurring in the proof was causing some problems

i spent the weekend thinking about the problem, and I solved the issue: the linkability definition in Backes' has corruption oracle access and target key selection occurring simultaneously in step 3

this allows us to restrict oracle access to the adversary only before they select their target keys

this resolves the issue entirely: the solver Y can simulate key corruption, I think, since things are happening in this order

sarang's initial idea was to split the key spaces up inside the algorithm Y so that X can only corrupt keys from the challenge set, but I wasn't convinced such a method could work, but because of this ordering of events, I think it can work

In what way? It presents the key universe first

so, the order in which things happen is this:

Y receives a bunch of DDH triple challenges. Y then simulates a bunch more Y-generated DDH triples, to which Y knows the ground truth. Y then sends X the union of these two sets of keys. X outputs a corruption set and two target keys; Y can cleanly abort if X outputs any keys it doesn't know the secret keys to (the proper DDH challenge triples), and respond to the DDH game by flipping coins.

otherwise, X outputs two proper challenge keys and a set of corruption keys known by Y

the sizes of these two sets indicate the probability of these two events, but if Y gains a non-negligible advantage this way, it'll translate through the probabilities; it just requires that we track the probabilities of success of this game very carefully and be very careful with our conditional probabilities to avoid Monty Hall-style spurious results

OK, so you're relying on aborting unless both (a) the corruption set is all challenger-created; and (b) the target pair are both true DDH

yes, and we can bound the probabilities at which these occur

Seems that `Y` will abort very frequently

*shrug* unless it aborts with probability greater than 1-negl(), the proof will still work

consider it this way: if i give you a non-negligible advantage to solving the DLP for 1 in every 10 keys, or 1 in every 10,000 keys, DLP is essentially broken

so, that's my "big result" from last week, but over the weekend I was thinking about hte CLSAG proof while working on my matching code, and i'm expecting a push with a script that produces a small sample exploration of parameter space later today

Would this be parameterized by the size of the corruption and DDH sets separately?

i think you can just parameterize it by the ratio of the sizes of those two sets

(I would assume so, to be able to get the bounds)

but yes

now that i've taken up 20 minutes explaining "yes, your idea from last week works, sarang, and here is why, although the bounds will be super weak..."

heh

Well, I've been working on security models for CLSAG but also on getting a form of key aggregation formalized into Triptych code, analysis numbers, and its preprint

Now that we've settled on Backes being a good definition for linkable anonymity, I want to add that to the ring signature definitions that Groth used, so as to extend it to the linkable case

What I liked about how Groth did it was that it took advantage of the underlying proving system being a sigma protocol (SHVZK, etc.)

oh that's interesting

also i'm considering going back to thring signatures to write a better linkable anonymity proof; if i do, it'll probably be a blog post

Unforgeability in the Groth case isn't quite as clean, but it's not bad

(uses special soundness)

okay, well I have no questions

and it appears to be quiet

holiday times

Ya

i'll be traveling next monday, so i will likely miss our meeting

OK, no problem

if we can reschedule for tuesday next week or wednesday, that'd be better for me

and probably half of the lurkers

Worth noting that the conference submission deadline is coming very soon

Would be nice to get CLSAG submitted there if the proof revisions (and other much smaller edits) are good to go

Deadline is November 30; next rolling deadline is February 29

okay, thanks. i'm pretty sure clsag will be gtg for Nov30

I'm on the fence about reducing the details for LSAG/MLSAG as examples

but I'm not opposed to it

I like having the details as background, and for comparison to the construction of CLSAG

What we _could_ do is reduce the amount of material that covers the specific constructions, and instead note the differences in security model

which also would highlight the improvements

(we should also include a note thanking the anonymous reviewers)

Thoughts on that suraeNoether ?

suraeNoether must have stepped away

Well, I shall continue work on papers and proofs then

woops, sorry, I thought we wrapped it. :P i'm still around, though. re: reduced details, sarang, I'm thinking of just throwing the deets into an appendix

appendices are such a helpful trick, and it's something you never need to exploit until you start writing 20+ page papers :P

Advantage to doing that over just a citation?

i'm trying to put myself in the position of the reviewer who interpreted some of the applications of CLSAG as "made up," who maybe is skeptical of other protocols, doesn't want to go find the other citation and try to figure it out by context. it makes the paper more self-contained without making the body itself bigger... but this is, itself, just an illusion from publishing papers on literal paper

we can consider it more deeply if we get rejected again :P

I do think that more clearly discussing the changes to security model would be useful

It shows that the improvements are also to the underlying proofs

If you like, I can include the edits prior to the appendixes

and we can get that definition/proof updated, since you already have some edits there

What say you, suraeNoether ?

I want to avoid conflicting edits, which would be a pain

Yes that's my game plan today

I mean, should I continue the non-appendix edits presently?

(would that avoid edit conflicts)

Oh I misunderstood. No, I am in the midst

I'd rather you work on triptych for now tbh

no problem