00:46:12_ingsoc_:_ingsoc_ is now known as _ingsoc
10:42:47adam3us: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:13adam3us:petertodd: maybe subliminal channel free signatures would be a starting point
12:11:49he1kki:he1kki has left #bitcoin-wizards
12:12:31adam3us: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:59petertodd:adam3us: I mean to prove that some random junk *doesn't* contain data using the appropriate timelock-iterations algorithm
12:29:37petertodd: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:56petertodd:adam3us: hellman's idea doesn't work in this case - proves the wrong thing
12:31:09adam3us: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:24petertodd:adam3us: but that's the thing, there may be no key
12:31:49adam3us:petertodd: ok so you want to prove that its not a DoS msg, ie the person who encrypted actually knew the plaintext
12:32:16adam3us:petertodd: and have that be verifiable before the brute-force decryption happens
12:32:17petertodd: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:48petertodd:adam3us: proving that there is a hidden message is the easy part
12:33:42adam3us: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:09adam3us:petertodd: kind of analogous the p2sh^2 argument frustrating data publication
12:34:32petertodd:adam3us: that still doesn't work
12:35:08petertodd: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:11adam3us: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:56petertodd: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:35adam3us:petertodd: i suppose you dont want to connect the msgs to the same author or they could be blockable
12:36:47adam3us:petertodd: (provable rng seed)
12:37:48petertodd: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:49adam3us: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:43adam3us: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:12petertodd: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:23petertodd:adam3us: you can only use a key to prove data was hidden, not the other way around
12:40:04adam3us:petertodd: oh wait you want to efficiently prove this is the ground key, without attaching it to the useful decryption
12:40:14petertodd: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:27adam3us:petertodd: because the decryption maybe garbage, and so have no inherent verifiability
12:40:37petertodd:yes
12:43:04adam3us: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:33petertodd:adam3us: yeah, something with just hashes is probably best - easier to be sure you have an efficient implementation
12:44:49adam3us: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:25adam3us: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:51adam3us: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:19petertodd:adam3us: yeah, but starting from random data I still can't prove I did that procedure honestly and came up with nothing
12:46:20adam3us: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:03petertodd:oh I see, you're saying that there's only going to be one solution in the space... bit risky there
12:47:26petertodd:you don't want it to be possible at all for people to create false proofs to consensus will break down
12:47:52adam3us: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:42adam3us:petertodd: if its bits 128-255=0 there is no way they're going to be able to collide that.
12:50:03petertodd: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:17adam3us:petertodd: well the bruteforce space is fromthe delete bits 0-31 so that can be tuned
12:52:11adam3us: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:27adam3us:petertodd: so you can chose those strengths independently
12:53:45petertodd: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:35adam3us: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:13adam3us:petertodd: if someone sends random junk there is very likely no solution yes.
12:55:15petertodd: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:31petertodd:adam3us: what you're doing has a zillion easy ways to do it - it's not the hard part
12:55:32adam3us:petertodd: got it you want to prove this actually is random junk
12:55:37petertodd:adam3us: yes!
12:55:54petertodd:adam3us: I need to honestly prove that, so other people don't have to re-do that work!
12:56:20adam3us: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:17petertodd:ight, I'm assuming this needs moon-math
12:57:20adam3us: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:57petertodd:well it's not about luck in this case: the work required is well-defined
12:58:10adam3us:petertodd: i left it as an open problem for research in the conclusion section in the amortitzable hashcash paper
12:58:27adam3us:petertodd: different use case. but if we had that building block i think it could've been a solution
12:59:19petertodd:anyway bbl
13:01:48adam3us: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:49adam3us: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:09adam3us: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:00adam3us: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:12wallet421:wallet421 is now known as wallet42
15:38:39wallet42:wallet42 is now known as Guest17024
15:38:39wallet421:wallet421 is now known as wallet42
16:01:37amiller: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:42amiller:you get a sort-of RSA without any setup trapdoor
16:02:16amiller:would be really thrilling to get this for snarks somehow...
17:23:38maaku:1A9Px42draCmgcYLC3xcsVZVmQV8YuGxuD
17:23:43maaku:sorry wrong channel
17:35:15execut3:execut3 is now known as shesek
18:09:19adam3us: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:09petertodd:sigh, I'm going to miss playing the exciting game "Is that dewer full of liquid helium, or liquid oxygen?"
21:21:47petertodd:maybe I can convince mastercoin to fund some QC miner research?
21:22:04petertodd:I technically it'd be ASIC hard...
21:22:09petertodd:*I guess
21:24:17michagogo|cloud:petertodd: Do you mean Dewar?
21:24:56petertodd:michagogo|cloud: lol, yeah
21:25:09sipa:to dewar, that means to make peace?
21:25:26petertodd:sipa: I think you should stick to your day job... :p
21:25:59maaku:* maaku groans
21:26:25petertodd: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:21michagogo|cloud:sipa: ...
21:31:19michagogo|cloud:I'm assuming that was a joke, but if not, http://en.wikipedia.org/wiki/Cryogenic_storage_dewar
21:32:49sipa:yeah, it was a joke :)
21:33:08petertodd: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:13petertodd:I suggest you sell all your Bitcoins right now.
21:54:22phantomcircuit:petertodd, why?
21:55:09phantomcircuit:just have to mine the transactions spending my pubkeyhash bitcoins to my lamport sig bitcoins
21:57:32petertodd: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:09petertodd: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:25nsh:petertodd, at least one quantum computer exists.
22:07:31nsh:(unfortunately we're inside it)
22:08:44petertodd:heh
22:10:13maaku:QC works just fine for God, I don't see why you've got a problem with it :P
22:10:14helo:i was happy to read about the revelation that our brains/consciousness relies on quantum tricks
22:10:35maaku:helo: very off topic, but I wouldn't put much credence in that
22:10:48helo:yeah :/
22:11:23maaku:helo: mysterious answer for a mysterious question
22:21:03sipa: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:09helo:heh nice
22:23:28petertodd:sipa: that's an excellent description - my coworkers echo that sentiment