If QQ is back, the current code is in github.com/moneromooo-monero/bitmonero/tree/clsag

sarang: this will be what should be reviewed, it's just the CLSAG changes.

Hello all

hi

good morning; sarang, i'm finishing up some notes on LRS security definitions to pass along to you. this is indept of the CLSAG notes, which i have *some* of but i'm going through the paper line by line before sending it along

Sounds goods; thanks suraeNoether

sarang some previous papers have called what you call unframeability a few different things but I think non-slanderable is possibly one of the more accurate terms

I'm cleaning up and testing some simplifications suggested for the CLSAG code, and chasing some performance numbers in the meantime

Yeah that term has been used as well

was there a logic in using "unframeability"? or is there a subtle difference between non-slanderability from Tsang's 2004 separable paper and our def that i'm missing?

The security games are all different for them anyway

that's my question... hold on let me pull this up

Based on what signatures you can obtain, etc.

tsang's paper is annoying because it's for event-oriented threshold ring sigs, not signing-key-oriented usual ring sigs

I'm happy with any definition that prohibits an adversary from choosing an honest key and linking with it, subject to suitable oracle access

but the security model i think is similar to what you are going for

^ * gotcha

but let me continue probing the differences with you briefly

okay so in that paper on page 9 we have their game-theoretic definition of non-slander

The Liu version doesn't really work IMO since it assumes both the target key signature and the adversarial signature are honestly generated

and doesn't make clear what other information (e.g. oracles) the adversary can see

agreed

now: here's my version of that definition for our purposes; i don't specify the orientation of key images and it's just a usual LRS, not threshold

enjoy the latex

now let me dig up your definition of unframeability

p 12 of the reorg overleaf version

here is your definition of non-frameability irccloud.com/pastebin/zL8X3cmW

(in my draft i'm neglecting things like number of oracle queries and time constraints on solvers until i have the majority of the definitions down correctly)

Sure

btw TWCALW non-slanderability is that tsang paper from iacr i just linked

hmm so immediate thing pops out at me

corruption in your definition of non-frameability

How so?

it looks to me like corruption oracle access isn't a success condition for yours; an adversary can corrupt the target key after asking for the oracle'd signature \sigma

but that appears to be the only practical difference between your definition of non-frameability and my attempt at describing the twcalw non-slanderability game (which admittedly does involve translating from the tsang paper's setting to our setting, but that's not a challenge here imo)

which is a good thing

Ah, there should be a condition on that key corruption

Otherwise the adversary could just sign, of course

similar thing happened to me about unforgeability recently :P

good catch

i was allowing the adversary to win by rolling their own keys and constructing a fair signature with them

i was up at 4am today thinking about whether we can eliminate the need for all the keys in both rings in non-slander to be challenge keys, so as to allow adversarially selected ring members...

(I'll likely need to update Triptych for that as well, but it shouldn't affect its proof or validity)

but we would need some way of ensuring the signatures *were* computed from some challenge ring members, even if some other ring members are adversarially computed

Well, as a related example, I can't think of any solid unforgeability definitions (not counting linkability at all) that don't fully restrict the ring for this reason

Otherwise the challenger can't detect if the adversary rolled a keypair and used it honestly

so, actually, i think i have that problem solved

Using linkability in particular?

due to our linkability

yep

it actually is something like this

(I'm referring to linkability-free signatures, just as an example of restricting malicious keys)

"weaken your definition of unforgeability, but then tack on linkability and non-slanderability, and you get a definition of unforgeability stronger than all previous definitions."

so i started thinking about extractors that could rewind a signer... if the signer outputs two linked signatures with two rings with some adversarially selected members, i think an extractor exists that can: place the signer in a black box, manage and record it's oracle queries, and then rewind the signer as many times as necessary to extract a proof that the adversarially selected ring members aren't

being used to compute the signature

that *would* relax the requirements of non-slanderability, but formalizing it and proving it may be... an unnecessary rabbit hole for right now

okay, sarang: thanks for chatting with me about this, I think I have enough of what I need right now to provide notes to you on CLSAG real soon, and now I can de-prioritize my tech note on LRS security until that's done

:D

I shall continue with CLSAG code performance testing then

sarang, a thought occurred to me

k

this is for the general LRS security paper, but it's relevant to CLSAG

for one thing, d-CLSAG is still a linkable ring signature scheme that satisfies some definition of linkability when linking occurs by matching *all* of the key images instead of just the first one

Yep

our scheme can be described as using the full linkability version as a sub-scheme, and merely discarding some of the linkability criteria

so i think that formally we should prove first the linkability using all key images, and then show that we don't lose linkability with respect to some model by discarding some of the linkability criteria

the reason i think this is important is the following

Yeah, it's still a bit asymmetric by using a single base across all linking tags (from the linking component)

that is true, but is also pretty specific to our implementation and the LRS paper i'm writing is very implementation agnostic at this point.

but... all of my concerns about making sure that the key image being published actually corresponds to the amounts being opened go away if 1) the LRS scheme is linkable when looking at all key images, and 2) we merely discard some of the linkability criteria. i *think*

moreover, there seems to be a new security definition here that is bugging me

which is this: in all of our real-life applications with confidential transactions, some of the keys being used are adversarially selected. That is to say, modeling everything by taking (sk, pk) <- KEYGEN doesn't capture the fact that *most* of the secret key is adversarially generated.

Would that discount the possibility of an adversary unable to link using all tags, but able to link using the single tag that really matters?

i'm not sure yet

the security model here gets really delicate

this would have to be a lemma to be proven in the course of proving that discarding linking tags is harmless

i feel like our definitions of unforgeability, for example, should allow the adversary to select the non-linking keys!

that is, instead of generating a big space of private and public keys and sending just the public keys to A, just generate the *linking coordinates* of these keys and let A fill in the amount coordinates

and i feel like a lot of our definitions need to take this into account

but i also know that no paper has done that before

and that it may be unnecessary? i'm not sure

but it feels like our security models should assume that, other than the linking key coord, the rest of the keys could be adversarially selected

anwyay, back to notes

If linkability accounts specifically for the single-component tag, what's wrong with just assuming that auxiliary tags are structurally no different than other signature components?

They exist only for the algebra, like other signature elements

The Monero Konferenco CFP is now open. Please submit your ideas and encourage others to submit theirs! monerokon.com/cfp

sgp_: "preference may be given too lower-cost travel" typo

good spot

sarang: thanks, fixed :)

sarang: our unforgeability definition implies non-frameability, and our definition of non-frameability is *really really close* to our definition of unforgeability; if unforgeability is restricted to lose the "adversarially selected keys" property, they are equivalent.

sarang: If linkability accounts specifically for the single-component tag, what's wrong with just assuming that auxiliary tags are structurally no different than other signature components? <--- i'm not sure if there's anything wrong with it. but i haven't seen a proof either way, and it's not immediately obvious

excuse me, i'm being sloppy with my language

let me be a lot more precise because "our" definition of unforgeability needs to be updated

okay, so define unforgeability almost exactly as in reorg.tex except change the linking tag requirement to the following statement

there exists a challenge key \textbf{pk}_i in \textbf{\underline{pk}}^\prime such that \textbf{pk}_i has not been corrupted and for any message m^*, any ring \textbf{\underline{pk}}^*, if this challenge key \textbf{pk}_i is in ring \textbf{\underline{pk}}^* at index l^*, then Link((m, \textbf{\underline{pk}}^\prime, \sigma), (m^*, \textbf{\underline{pk}}^*, l^*)) = 1

and modifying this definition so that the ring of public keys need not be a subset of the challenge keys (only the linked key needs to be a challenge key)

for *this* definition of unforgeability, the definition of non-slanderability follows

non-slanderability/non-frameability, however, does not imply unforgeability but *only because* our definition of non-frameability requires all ring members be challenge keys, but unforgeability relaxed this

this is of course exactly what we wanted unforgeability to capture: the inability to construct a valid non-oracle signature that links to someone else's honestly generated key

by the way, i didn't really believe that non-slanderability implied so much of unforgeability until i saw the proof, so if you want me to elaborate on that, it was a bit of a surprise to me.

sarang, i'm going to make a new rereorg.text and then share it with you.

OK, or edit directly if that's cleaner

meh.

also, gotta dip out in an hour but i'll be back after

OK, let me know when you're done

thinking about the gamma distribution for decoy selection; in my simple brain it's a fixed distribution over [0,1], a number is selected randomly from that distribution and gets multiplied by the total number of outputs; this implies as more outputs accumulate (e.g. doubles), the age spread of chosen decoys changes (e.g. widens by ~2x); is my story accurate? I reached a dead end trying to read the code

Here is some sample code showing different selection mechanisms that were under consideration: github.com/SarangNoether/skunkworks/tree/outputs/outputs

`lineup` is the idea that was deployed

It was found to be reasonably robust against different possible chain conditions, while doing a good job with weighting within blocks

The tricky part is that outputs don't have a timestamp beyond the block timestamp

and for extreme chain conditions that, coupled with the fact that empty blocks exist, can throw off the selection

ok I think I understand that part; an example for a thousand words; say the blockchain is 1yr old, and the gamma distribution will pick ~90% of decoys from the past 10 days; 1yr from now, when the chain is 2yr old, will the gamma distribution now pick ~90% from the past _20_ days?

The timing parameters for the distribution are fixed

A fixed time window is used to derive an "average output time" from the output/block density and the block target times

This is the time used for the exp-gamma selection

after which a shuffle is performed within the block of the chosen output (to account for the fact that all outputs in the block have the same time, and could have been adversarially packed by the miner)

The distribution timing from Miller et al. was found to change very little over time

So the answer to your question is "the distribution doesn't change purely based on the length of the chain"

what affects it is the average output timing, which is taken over a reasonably long period to avoid short-term "feast or famine" conditions, which can throw off the selection

well take a friendly assumption like constant output emission

(but not as much as some other possible selection methods)

The windowed average output timing is intended to smooth out the effects of non-constant output density

You can model different chain conditions using that simulator, or write your own, or supply your own chain data

yeah that part is clear

Ok

so (assuming constant output emission) decoys will have nearly the same average age no matter how long the chain gets (within human lifetime)? or more precisely, the same median age?

This was found to be in line with Miller et al.'s analysis

Which examined spend snapshots of chain data

and compared with true-spend Monero data where available

If your conclusion is "this selection method is suboptimal" then yes, it is

Ideally we'd account for as many aspects of spend behavior as possible

Made more challenging by the fact that true spend behavior is in general not known for the Monero chain

Im more worried it wont age well

All we can reasonably do is compare to known chain data, which is what Miller et al. did

Revisiting the analysis at some point (I'm not saying right now) would be a good idea

A user spending a very, very, very old output who is concerned about the distribution (should it never change) can always perform a self-spend to return the output to the "recent pool" first

ok

That's one spot where binning, if done right, could help

Since even if you identify the bin containing the likely spend (due to age), you still have ambiguity (barring other information like cross-ring comparisons, etc.)

sarang: backe's linkability and tsang's linkability are not directly comparable. in the sense that an algo that can solve one can't always be turned into an algo that can solve the other. however, tsang's linkability, with certain ring size constraints imposed, *does* imply backe's linkability via induction. without those ring size constraints, the two notions are actually distinct, although the proofs

of each will be very similar.

so i think we'll need to prove both (not a big deal)

brb