00:46:12 | _ingsoc_: | _ingsoc_ is now known as _ingsoc |

10:42:47 | adam3us: | petertodd: "Can you prove to a third party that a given transaction does *not* contain a stego-encoded data packet? With SCIP it's easy to see how that could be possible in principle, but I dunno if it can be made efficient enough to be practical." <-- other than the assertion that stego wins |

10:47:13 | adam3us: | petertodd: maybe subliminal channel free signatures would be a starting point |

12:11:49 | he1kki: | he1kki has left #bitcoin-wizards |

12:12:31 | adam3us: | petertodd: "can you prove the execution of a timelock crypto sequence, which is something as simple as 10,000 SHA256 invocations, such that you can prove the end result cheaply to a third party that can evaluate that proof cheaply" <-- well just Hellman's idea to delete 16-key bits with symmetric crypto is efficiently provable after someone has found the key. or do you mean prove it is decryptable before it has been decrypted? |

12:27:59 | petertodd: | adam3us: I mean to prove that some random junk *doesn't* contain data using the appropriate timelock-iterations algorithm |

12:29:37 | petertodd: | adam3us: remember that the timelock algorithm in this case is just a fixed number of H() invocations or similar - the question is can you prove the end-result of that algorithm to someone else cheaply? |

12:29:56 | petertodd: | adam3us: hellman's idea doesn't work in this case - proves the wrong thing |

12:31:09 | adam3us: | petertodd: well hellman's thing shows after you know the key, its certainly easy /cheap for anyone else to verify its the right key, and decrypt it and see what the plaintext was |

12:31:24 | petertodd: | adam3us: but that's the thing, there may be no key |

12:31:49 | adam3us: | petertodd: ok so you want to prove that its not a DoS msg, ie the person who encrypted actually knew the plaintext |

12:32:16 | adam3us: | petertodd: and have that be verifiable before the brute-force decryption happens |

12:32:17 | petertodd: | adam3us: no, I have random data, I want to prove that after you apply the timelock stego algorithm, you still have random data |

12:32:48 | petertodd: | adam3us: proving that there is a hidden message is the easy part |

12:33:42 | adam3us: | petertodd: ok so maybe like if you could prevent proof of publication, eg by proving with SCIP that the contents are the hash of an undisclosed value then you restrict the stego-encoding rate to ground bits of the hash |

12:34:09 | adam3us: | petertodd: kind of analogous the p2sh^2 argument frustrating data publication |

12:34:32 | petertodd: | adam3us: that still doesn't work |

12:35:08 | petertodd: | adam3us: I was referring to using SCIP to prove that you *did* the 10,000 iterations of H() honestly, and thus the result is the honest candidate decryption key, so if that key doesn't work, you know there isn't hidden data |

12:35:11 | adam3us: | petertodd: or if there is a static public key, the private key of which is used as the seed of a rng, you could prove that this hidden/encrypted value is with the next rng output, without revealing what the rng output is |

12:35:56 | petertodd: | adam3us: remember this is about my timelock crypto for embedded consensus systems thing - you don't get any control over the data other users add to the blockchain |

12:36:35 | adam3us: | petertodd: i suppose you dont want to connect the msgs to the same author or they could be blockable |

12:36:47 | adam3us: | petertodd: (provable rng seed) |

12:37:48 | petertodd: | adam3us: that's irrelevant, it's timelocked so the fact that you can decrypt the stego message in 1hour frustrates the miner who only wants to spend a few seconds at most figuring out if they can put the transaction in their block |

12:37:49 | adam3us: | petertodd: btw why scip prove you did the work, you can just reveal the key, if the msg is garbage, people can see that for themselves |

12:38:43 | adam3us: | petertodd: yes time-lock works for analogous reasons to committed-tx, there is some similarity in forcing miners to make decisions on encrypted data |

12:39:12 | petertodd: | adam3us: it's impossible to prove you revealed the *correct* key if decrypting the candidate stego data with that key results in random junk |

12:39:23 | petertodd: | adam3us: you can only use a key to prove data was hidden, not the other way around |

12:40:04 | adam3us: | petertodd: oh wait you want to efficiently prove this is the ground key, without attaching it to the useful decryption |

12:40:14 | petertodd: | adam3us: remember that there's far more candidate data without steggo data in it, so you save resources if everyone can work together in a trust-free way to decrypt it all |

12:40:27 | adam3us: | petertodd: because the decryption maybe garbage, and so have no inherent verifiability |

12:40:37 | petertodd: | yes |

12:43:04 | adam3us: | petertodd: i was thinking about like rivests rsa-timelock might be tweaked to be efficiently veriable maybe, (i managed to find a blindable version of it so you could securely offload KDF calculation to untrused nodes) but maybe more simply if you make the key to grind have structure (an indirection) |

12:44:33 | petertodd: | adam3us: yeah, something with just hashes is probably best - easier to be sure you have an efficient implementation |

12:44:49 | adam3us: | petertodd: so c= E_k( msg ), e = E_b( k ) publicsh c, e, bits b[32-255] and bits b[192-255]=0 |

12:45:25 | adam3us: | petertodd: now you have to brute force decrypt e to find k by finding the missing 32-bit of b, hwen you find it its obvious its the right key |

12:45:51 | adam3us: | because its much harder to find a collision in the 64-bits of b set to 0 (adust to 80 or 128 even) |

12:46:19 | petertodd: | adam3us: yeah, but starting from random data I still can't prove I did that procedure honestly and came up with nothing |

12:46:20 | adam3us: | and so that allows fast verification, and then people can decrypt c and see what the msg looks like, even if its garbage they're pretty sure its the right key and proves work |

12:47:03 | petertodd: | oh I see, you're saying that there's only going to be one solution in the space... bit risky there |

12:47:26 | petertodd: | you don't want it to be possible at all for people to create false proofs to consensus will break down |

12:47:52 | adam3us: | petertodd: well it would be almost impossible to find b!=b' such that D_b(c)=mod 2^192==0 and D_b'(c) mod 2^192==0 |

12:48:42 | adam3us: | petertodd: if its bits 128-255=0 there is no way they're going to be able to collide that. |

12:50:03 | petertodd: | adam3us: but that's not very adjustable re: difficulty - I either make it basically impossible to ever find that distinguished key in the space, or I make it possible to find one such key, and therefor possible to find a second |

12:51:17 | adam3us: | petertodd: well the bruteforce space is fromthe delete bits 0-31 so that can be tuned |

12:52:11 | adam3us: | petertodd: and the strength of the assurance that they didnt cheat and make two solutions is separately tunable as the trailing 0 bits (80 or 128 of those) |

12:52:27 | adam3us: | petertodd: so you can chose those strengths independently |

12:53:45 | petertodd: | adam3us: ok, but this is the issue: from random data you won't be able to find a distinguished solution at all, therefore have no way of proving you did the work |

12:54:35 | adam3us: | petertodd: well it is true that its a known solution proof of work... the person who did the encryption knows the solution so has a work advantage |

12:55:13 | adam3us: | petertodd: if someone sends random junk there is very likely no solution yes. |

12:55:15 | petertodd: | adam3us: but that's not the point! the point is to prove the case where no-one did any encryption and no solution exists |

12:55:31 | petertodd: | adam3us: what you're doing has a zillion easy ways to do it - it's not the hard part |

12:55:32 | adam3us: | petertodd: got it you want to prove this actually is random junk |

12:55:37 | petertodd: | adam3us: yes! |

12:55:54 | petertodd: | adam3us: I need to honestly prove that, so other people don't have to re-do that work! |

12:56:20 | adam3us: | petertodd: yeah i was never able to find a symmetric encryption PoW with no trapdoor that was efficiently verifiable... i tried back in 1997 |

12:57:17 | petertodd: | ight, I'm assuming this needs moon-math |

12:57:20 | adam3us: | petertodd: and symmetric encryption search space was interesting because it has a maximum work.. ie we know it takes no more than 2^n work so you can not get more unlucky than that |

12:57:57 | petertodd: | well it's not about luck in this case: the work required is well-defined |

12:58:10 | adam3us: | petertodd: i left it as an open problem for research in the conclusion section in the amortitzable hashcash paper |

12:58:27 | adam3us: | petertodd: different use case. but if we had that building block i think it could've been a solution |

12:59:19 | petertodd: | anyway bbl |

13:01:48 | adam3us: | petertodd: maybe u can get closer it by defining a verifiable problem instance defined by the ciphertext. so like coelho merkle hash using he ciphertext a deterministic seed. then the fiat shamir gives you possibility to only spot check the work. still fairly expensive though |

13:08:49 | adam3us: | petertodd: you can probably do it reasonably efficiently with the asymmetric PoWs like dwork & naor's eg use the ciphertext as a seed to define a big num, compute the squareroot of it mod p a large fixed prime. now people can veryify the root PoW by squaring, and then try to say hash the number and use it a sym key to decrypt. there is only one solution. it resonably efficiently verifiable. p has to be quite big to create much work they |

13:11:09 | adam3us: | petertodd: the down side of their approach is the asymmetry of work to verification is less extreme than with hashcash. bigger work tends to require somewhat bigger verification cost. you are basically using a signature algorithm with weak parameters and breaking them in their other scheme sothat maybe is a bit faster verification for reasonable work than square root |

13:14:00 | adam3us: | petertodd: unfortunately their non square root scheme has a setup time trapdoor like zerocoin (n=pq with p&q must be deleted and forgotten). its the fiat shamir signature scheme (that introduced the fiat-shamir transform.) |

14:07:12 | wallet421: | wallet421 is now known as wallet42 |

15:38:39 | wallet42: | wallet42 is now known as Guest17024 |

15:38:39 | wallet421: | wallet421 is now known as wallet42 |

16:01:37 | amiller: | i was pretty interseted to see this RSA UFO paper mentioned in zerocoin http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.4015&rep=rep1&type=pdf |

16:01:42 | amiller: | you get a sort-of RSA without any setup trapdoor |

16:02:16 | amiller: | would be really thrilling to get this for snarks somehow... |

17:23:38 | maaku: | 1A9Px42draCmgcYLC3xcsVZVmQV8YuGxuD |

17:23:43 | maaku: | sorry wrong channel |

17:35:15 | execut3: | execut3 is now known as shesek |

18:09:19 | adam3us: | amiller: yeah but its huge eh 40kbit key or something? i was thinking you maybe able to shave some bits on it with a big online factorizing effort to see if you can find any feasible ones like any < 512-bit factors with some effort. its a composite n=p1*..*pk for variable sized and unknown p, with a statistical argument that at least two fo them should be > 512-bit (or whatever the security margin is) |

21:21:09 | petertodd: | sigh, I'm going to miss playing the exciting game "Is that dewer full of liquid helium, or liquid oxygen?" |

21:21:47 | petertodd: | maybe I can convince mastercoin to fund some QC miner research? |

21:22:04 | petertodd: | I technically it'd be ASIC hard... |

21:22:09 | petertodd: | *I guess |

21:24:17 | michagogo|cloud: | petertodd: Do you mean Dewar? |

21:24:56 | petertodd: | michagogo|cloud: lol, yeah |

21:25:09 | sipa: | to dewar, that means to make peace? |

21:25:26 | petertodd: | sipa: I think you should stick to your day job... :p |

21:25:59 | maaku: | * maaku groans |

21:26:25 | petertodd: | Trying to wrap things up at work... First time I've had to do that with non-trivial projects, and it's not proving to be very easy. |

21:30:21 | michagogo|cloud: | sipa: ... |

21:31:19 | michagogo|cloud: | I'm assuming that was a joke, but if not, http://en.wikipedia.org/wiki/Cryogenic_storage_dewar |

21:32:49 | sipa: | yeah, it was a joke :) |

21:33:08 | petertodd: | For the peanut gallery full of investors, the dewar I'm talking about is related to the quantum stuff I do for the mining company I was working at. |

21:33:13 | petertodd: | I suggest you sell all your Bitcoins right now. |

21:54:22 | phantomcircuit: | petertodd, why? |

21:55:09 | phantomcircuit: | just have to mine the transactions spending my pubkeyhash bitcoins to my lamport sig bitcoins |

21:57:32 | petertodd: | phantomcircuit: well actually in theory a QC computer can do a sqrt(bits) (or was it bits/2?) speedup compared to a conventional computer for even hash functions |

21:58:09 | petertodd: | phantomcircuit: though I suspect QC computers will never be developed - they're basically infinite precision analog computers and that doesn't sound very physical to me |

22:07:25 | nsh: | petertodd, at least one quantum computer exists. |

22:07:31 | nsh: | (unfortunately we're inside it) |

22:08:44 | petertodd: | heh |

22:10:13 | maaku: | QC works just fine for God, I don't see why you've got a problem with it :P |

22:10:14 | helo: | i was happy to read about the revelation that our brains/consciousness relies on quantum tricks |

22:10:35 | maaku: | helo: very off topic, but I wouldn't put much credence in that |

22:10:48 | helo: | yeah :/ |

22:11:23 | maaku: | helo: mysterious answer for a mysterious question |

22:21:03 | sipa: | petertodd: not sure where i read this quote, but it says that QC is essentially trading NP-hard runtime for NP-hard engineering |

22:22:09 | helo: | heh nice |

22:23:28 | petertodd: | sipa: that's an excellent description - my coworkers echo that sentiment |