brief update for everyone who's paying attention and sarang

I've gotten the proof statement about CLSAG linkable anonymity down to a result that is weird

sarang, you have access to the tex file so you can see the changes i've made

the result is this:

if A is an adversary who plays the linkable anonymity game with k+2 keys given to it, up to k corruption oracle queries, signature oracle access, and advantage phi at linkability, then the script M I build from that algorithm to break DDH has advantage phi/2^k

now, if A is an adversary with non-negligible advantage, then phi/2^k may or may not be negligible, depending on phi

in particular, if the linkable anonymity solver is capable of corrupting *lots and lots and lots* of keys, the probability that they didn't accidentally attempt to corrupt a DDH key gets very small

this is pretty obvious: if A is handed a universe of k keys, all A has to do to force M to terminate and play the DDH game by flipping a coin is to try to corrupt all the keys they are granted access to

so this isn't a security problem, per se, but it does mean that, unless my math is wrong, a *weak* linkable anonymity solver that requires lots and lots of corrupted keys but can still succeed non-negligibly, such a solver will *not* be immediately translatable into a DDH solver

at least, not using my method

but i can prove that a *sufficiently strong* linkable anonymity solver will be able to break the DDH game, which means a sufficiently strong linkability solver that requires very few corruption queries is unlikely to exist in a computational world.

in the above, the only word i'm using that may be weird is "strong" which i'm taking to mean "requiring few corruption oracle queries, not many."

oh wait, no, phi has to be at most 1/2 since it's an advantage... phooey

If I'm understanding you correctly, this boils down to a problem of how likely `A` is to choose challenger keys (versus DDH keys) to corrupt; is that correct?

yes

(this was my initial concern when thinking about this idea)

i havne't played with the ratios of the number of keys available yet

right now it's 50/50

Yeah, I thought this would end up being problematic

Only because of the bounds involved :/

I'm just about finished getting the LRS definitions and security games worked into the single-signer Triptych preprint that's intended for the IACR archive

so, look, this is what today brought: since advantage has to be <= 1/2, my proof actually demonstrates that the DDH game is strictly harder than the linkable anonymity game, and one does not reduce to the other

An interesting but unfortunate result :/

at least, the algorithm M we use cannot even use a linkable anonymity solver ot break DDH, so...

yeah

Presumably an alternate definition of linkability-compatible anonymity could be used too

that would work with DDH

either that algorithm needs to be tweaked, perhaps by ratios of key spaces or something like that, or maybe there's something else we need to consider

After all, nobody says we absolutely need to use the exact Backes model (which, AFAIK, they came up with)

yeah... the real problem here is simulating the corruption oracle

mhmm

I don't really see a DDH-compatible way to do that, though

in other words, just like the musig proof that fell apart, it feels like this is a fundamental limitation of the simulation method of proving security

uhmmmmm

How comfortable are you with using a different LA model?

idea: DDH is random self reducible. so I think we can define a DDH game that allows corruption oracle access, and then either prove that granting corruption oracle access doesn't make DDH easier, or find a proof of that

i'm comfortable with the idea, as long as it captures reasonable security

i think abandoning the corruption oracle entirely is probably a bad idea

i.e. "oh, you think you can solve DDH with n corruption oracle queries? well, if you can, then you can solve DDH with n-1 corruption oracle queries." that sort of thing might do it, because then the corruption oracle doesn't need to be simulated

I only mention alternate models because I've been thinking a lot today about the relationship between having a corruption oracle and allowing the adversary to simply provide its own keys (which could be malicious and not part of a standard keypair)

In particular, what do we wish to capture with a corruption oracle versus adversary-supplied keys?

it's a deep question; adversarially supplied is maybe not helpful because there's a publicly verifiable record of which keys are allowed to be ring members called the blockchain. Although the adversary can try to control them, they are sums of DDH products and hash outputs and all that. on the other hand, corruption in the traditional sense models persuading someone, by carrot or stick, to give you

their key

it feels like that should be the threat model: persuading all except 2 other ring members to reveal their keys shouldn't help you distinguish which of the remaining two are signers

sarang, i'm also sending you an email with a list of questions/comments for the remainder of the paper (i've been focusing on these proofs)

Well, isn't allowing the adversary to supply its own keys/points equivalent (in some sense) to having it generate those outputs (on chain) and then use them?

That seems stronger

Since corruption implies the underlying keys were generated honestly to begin with

^ suraeNoether

is there any more info on triptych available yet?

Like what?

sarang is the key image just another EC point?

I have a crypto::public key I want to convert to a ge_p3

It is a point. In particular, you want it on the main... thing.

curve ?

Yeah key image is a curve point

Was just making sure

Is it possible to use ge_frombytes_vartime to convert a straight up crypto::public_key?

to a ge_p3

sorry convert from crypto::public

to a ge_p3

@sarang: things like performance/design

or how it differs/is superior to omniring/ringct3.0

or trade offs it has

sarang what is the difference between a ge_p3 and a ge_p2

gets my skunkworks repo sublinear branch has some comparison data

peach34: seems this was answered already in dev?

do you have a link to that repo?

Hey everyone. Day of travel turned into a day of chilling in airports, so I am going to be available

"5:39 PM <• sarang> Well, isn't allowing the adversary to supply its own keys/points equivalent (in some sense) to having it generate those outputs (on chain) and then use them?" <--- Sarang, not equivalent, no. Corruption grants the adversary some access to a discrete logarithm Oracle. That's very powerful. And the adversary can already supply any points they like.

The question is really whether corruption is necessary, and I think it is because of our practical security concerns

I think the safe way to go is to prove that a ddh solver with corruption access has no advantage over a ddh solver without corruption access, or finding this proven elsewhere to refer the reader to it...

Certainly solving ddh without corruption oracle access implies the ability to solve ddh with corruption oracle access, of course...

Equivalent was a bad choice of wording

sarang in cryptonote.org/whitepaper.pdf bottom of page 9. closing the loop with r= q-cx mod l, is the mod l applied to cx or the overall result, or both?

peach349: either, since q mod l - cx mod l = (q-cx) mod l. This is because addition in Z/lZ is associative

You misunderstood slightly

I understand addition in Z is associative

But I'm not sure whether the whitepaper is saying: q - ((cx)mod l) or (q-cx) mod l

My guess is (q-cx) mod l

the other way could be negative so it seems a pretty safe bet it's not that

Since q is in Z/lZ, rewrite q = q mod l. Since q mod l - cx mod l = (q-cx) mod l, there is no difference between the two ways of computing it. Negative numbers wrap around. Here is an example from Z/12Z, the clockface. Set q = 4 mod 12 and cx = 7 mod 12. Then q - cx = -3 mod 12 = 9 mod 12.

If q is an arbitrary integer, then they mean q mod l - cx mod l. But iirc q is selected from Z/lZ

So: potato pobobot

*cough* isthmus ^

negative numbers don't wrap if you don't mod l :)

Yeah that makes complete sense.

Thanks

<• luigi1111w> negative numbers don't wrap if you don't mod l :) <--- ehhhhh yeah this is a gap between compsci and math having to do with types. In a computer, if I compute 8675309 mod 7, I get an integer back, not an integer mod 7, so computing q mod l - cx mod l could be between -(l-1) and l-1 instead of being between 0 and l-1.

Nevertheless, (q - (cx mod l) mod l) = (q - cx) mod l = ((q mod l) - (cx mod l) mod l) and so on, which I where my answer came from

it was the only way I could make sense of the question

suraeNoether are you aware of the behaviour of cx_math_subm inside the ledger-sdk in the context of these negative numbers??

?*

I was going to combine cx_math_subm and cx_math_multm to essentially produce what could be named a 'cx_math_mulsubm'

for your reference, these functions are located here github.com/LedgerHQ/nanos-secure-sdk/blob/master/src/syscalls.c

Nope, I have not looked at it closely

I will take a look but definitely rely on other folks too

What is the logic behind combining them? Easier to test two separate functions usually

Cheers. It looks like the result is put into an unsigned char

So I'm guessing you get the +ve result

Well, I could do them separately I suppose

Of course q can never leave the device, otherwise the output private key can be computed (and therefore the wallet seed because of the affine construction)