00:02:55 <suraeNoether> brief update for everyone who's paying attention and sarang
00:03:42 <suraeNoether> I've gotten the proof statement about CLSAG linkable anonymity down to a result that is weird
00:03:51 <suraeNoether> sarang, you have access to the tex file so you can see the changes i've made
00:04:12 <suraeNoether> the result is this:
00:06:44 <suraeNoether> 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
00:07:41 <suraeNoether> now, if A is an adversary with non-negligible advantage, then phi/2^k may or may not be negligible, depending on phi
00:08:34 <suraeNoether> 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
00:10:16 <suraeNoether> 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
00:11:46 <suraeNoether> 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
00:11:54 <suraeNoether> at least, not using my method
00:13:27 <suraeNoether> 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.
00:13:52 <suraeNoether> 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."
00:14:40 <suraeNoether> oh wait, no, phi has to be at most 1/2 since it's an advantage... phooey
00:14:41 <sarang> 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?
00:14:48 <suraeNoether> yes
00:14:54 <sarang> (this was my initial concern when thinking about this idea)
00:14:55 <suraeNoether> i havne't played with the ratios of the number of keys available yet
00:15:02 <suraeNoether> right now it's 50/50
00:15:10 <sarang> Yeah, I thought this would end up being problematic
00:15:30 <sarang> Only because of the bounds involved :/
00:16:50 <sarang> 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
00:16:54 <suraeNoether> 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
00:17:14 <sarang> An interesting but unfortunate result :/
00:17:27 <suraeNoether> at least, the algorithm M we use cannot even use a linkable anonymity solver ot break DDH, so...
00:17:28 <suraeNoether> yeah
00:17:39 <sarang> Presumably an alternate definition of linkability-compatible anonymity could be used too
00:17:49 <sarang> that would work with DDH
00:17:55 <suraeNoether> 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
00:18:06 <sarang> After all, nobody says we absolutely need to use the exact Backes model (which, AFAIK, they came up with)
00:18:38 <suraeNoether> yeah... the real problem here is simulating the corruption oracle
00:18:44 <sarang> mhmm
00:18:50 <sarang> I don't really see a DDH-compatible way to do that, though
00:19:11 <suraeNoether> 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
00:19:35 <suraeNoether> uhmmmmm
00:19:35 <sarang> How comfortable are you with using a different LA model?
00:21:23 <suraeNoether> 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
00:21:37 <suraeNoether> i'm comfortable with the idea, as long as it captures reasonable security
00:21:48 <suraeNoether> i think abandoning the corruption oracle entirely is probably a bad idea
00:22:25 <suraeNoether> 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
00:22:37 <sarang> 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)
00:31:05 <sarang> In particular, what do we wish to capture with a corruption oracle versus adversary-supplied keys?
00:35:26 <suraeNoether> 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
00:35:27 <suraeNoether> their key
00:36:40 <suraeNoether> 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
00:37:44 <suraeNoether> 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)
00:39:28 <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?
00:39:36 <sarang> That seems stronger
00:39:54 <sarang> Since corruption implies the underlying keys were generated honestly to begin with
00:42:09 <sarang> ^ suraeNoether
15:49:39 <gets> is there any more info on triptych available yet?
16:23:08 <sarang> Like what?
16:31:36 <peach34> sarang is the key image just another EC point?
16:31:56 <peach34> I have a crypto::public key I want to convert to a ge_p3
16:32:13 <moneromooo> It is a point. In particular, you want it on the main... thing.
16:32:17 <moneromooo> curve ?
16:32:18 <sarang> Yeah key image is a curve point
16:35:38 <peach34> Was just making sure
16:36:15 <peach34> Is it possible to use ge_frombytes_vartime to convert a straight up crypto::public_key?
16:36:20 <peach34> to a ge_p3
16:36:34 <peach34> sorry convert from crypto::public
16:36:38 <peach34> to a ge_p3
16:45:32 <gets> @sarang: things like performance/design
16:46:29 <gets> or how it differs/is superior to omniring/ringct3.0
16:46:39 <gets> or trade offs it has
17:10:53 <peach34> sarang what is the difference between a ge_p3 and a ge_p2
18:24:48 <sarang> gets my skunkworks repo sublinear branch has some comparison data
18:29:28 <sarang> peach34: seems this was answered already in dev?
18:31:26 <gets> do you have a link to that repo?
18:39:41 <sarang> https://github.com/SarangNoether/skunkworks/tree/sublinear
18:43:08 <suraeNoether> Hey everyone. Day of travel turned into a day of chilling in airports, so I am going to be available
18:45:22 <suraeNoether> "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.
18:46:42 <suraeNoether> The question is really whether corruption is necessary, and I think it is because of our practical security concerns
18:47:39 <suraeNoether> 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...
18:48:46 <suraeNoether> Certainly solving ddh without corruption oracle access implies the ability to solve ddh with corruption oracle access, of course...
18:55:43 <sarang> Equivalent was a bad choice of wording
21:19:30 <peach349> sarang in https://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?
21:24:08 <suraeNoether> peach349: either, since q mod l - cx mod l = (q-cx) mod l. This is because addition in Z/lZ is associative
21:30:11 <peach349> You misunderstood slightly
21:30:25 <peach349> I understand addition in Z is associative
21:31:05 <peach349> But I'm not sure whether the whitepaper is saying:       q - ((cx)mod l) or (q-cx) mod l
21:33:23 <peach349> My guess is (q-cx) mod l
21:54:13 <luigi1111w> the other way could be negative so it seems a pretty safe bet it's not that
21:56:58 <suraeNoether> 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.
21:57:30 <suraeNoether> If q is an arbitrary integer, then they mean q mod l - cx mod l. But iirc q is selected from Z/lZ
21:58:02 <suraeNoether> So: potato pobobot
21:58:13 <suraeNoether> *cough* isthmus ^
22:00:12 <luigi1111w> negative numbers don't wrap if you don't mod l :)
22:03:26 <peach349> Yeah that makes complete sense.
22:04:05 <peach349> Thanks
22:31:16 <suraeNoether> <• 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.
22:32:30 <suraeNoether> 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
22:38:11 <luigi1111w> it was the only way I could make sense of the question
22:49:20 <peach349> suraeNoether are you aware of the behaviour of cx_math_subm inside the ledger-sdk in the context of these negative numbers??
22:49:27 <peach349> ?*
22:50:46 <peach349> I was going to combine cx_math_subm and cx_math_multm  to essentially produce what could be named a 'cx_math_mulsubm'
22:51:21 <peach349> for your reference, these functions are located here https://github.com/LedgerHQ/nanos-secure-sdk/blob/master/src/syscalls.c
22:54:06 <suraeNoether> Nope, I have not looked at it closely
22:54:38 <suraeNoether> I will take a look but definitely rely on other folks too
22:55:14 <suraeNoether> What is the logic behind combining them? Easier to test two separate functions usually
22:55:20 <peach349> Cheers. It looks like the result is put into an unsigned char
22:55:37 <peach349> So I'm guessing you get the +ve result
22:56:50 <peach349> Well, I could do them separately I suppose
22:57:24 <peach349> 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)