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