12 ms·

Time-lock encryption

• pacofvf 13y ago
  Maybe it's just because is Monday but, besides of the Julian Assange's example and the time capsule, I can't think of another use case of a Time-lock crypto puzzle, anyone?
  • simias 13y ago
    If you want to leave something that you are sure won't be accessed before your death (and you don't want to have to trust some third party). Although I guess it might fit the definition of "time capsule".
  • ColinDabritz 13y ago
    Court proceedings that would be sealed for 100 years. Secret material, say military records, that need to be secure in the present, but are important historically at some point. You could provide a declassification schedule this way. You could do a delayed form of historical whistleblowing or confession, so that it doesn't cause you problems today, but history can know what really happened. Perhaps providing the equivalent of a 'sealed envelope' to prove that something was known or happened on a given date, without having to be present or active to prove it. It's fun to think of a puzzle, but presuming it was truly delivering on the safety promise, I can see quite a few uses. The real schemes though depend on a lot of varying factors, so in cases where the secrecy was critical, you can see why people wouldn't use it.
  • betterunix 13y ago
    Even Assange's example is suspect. The goal is not to release the documents eventually but to release the documents if he dies under suspicious circumstances. That is not really something that can be done with cryptography. Here is one possible use case: imagine an offline digital cash system, so i.e. the bank will not accept the same token twice. To protect against an unscrupulous seller, the buyer pays by giving the seller a time-lock puzzle with the tokens; if the goods are not delivered by some deadline, the buyer will deposit the tokens at the bank, thus preventing the seller from doing so. Otherwise the seller solves the puzzle and makes the deposit. This is basically an anonymity-preserving escrow service, though in practice there are probably simpler approaches.
  • jiffyjeff 13y ago
    According to FutureCrypt.com, time-release encryption can be used for Sealed Bids, Competitive Proposals, and Press Releases. So things like sealed bids for government RFPs could be transmitted electronically rather than "sealed" in a FedEx envelope. Full disclosure: I own FutureCrypt.
  • simbolit 13y ago
    I am sure you read about the early-access scandal at Reuters [0], which the quants found especially spooky as they (by definition) weren't first. So releasing high-value financial information this way is my first idea for a use case. Clarification: it seems Reuters intentionally sold the info to high value customers early. But this is an even better reason for the information source to release their info this way. [0] http://qz.com/92786/more-evidence-that-data-thomson-reuters-gives-its-clients-may-be-leaking-out-even-earlier-than-its-meant-to/ http://qz.com/92786/more-evidence-that-data-thomson-reuters-...
  • pavel_lishin 13y ago
    A trust for your children that you don't want them to be able to access until they reach a certain age.
• earlz 13y ago
  Possible variant on this scheme to make it harder to estimate the amount of time required: Don't use a fixed number of hash iterations. Instead, use a bitcoin-ish scheme like: "the key to this file is given by hashing 'xxxx' until the hash's bottom 8 bits are 0"
  • simias 13y ago
    The problem here is that the amount of work needed to generate the key is not known beforehand either. I think a better approach (that would also not leak bits of the key) would be to say "hash until the hash of the hash is xxx". So basically you hash until you get xxx and then take the previous iteration's result as a key.
    • zeckalpha 13y ago
      Given a sequence of N hashes, you could select any hash A as the initial hash, any hash B as the key, and the successor of B (C) as the key to the key. After choosing B and C, choose an A whose distance to B and C is proportional to the amount of work you wish to require.
      • simias 13y ago
        Your "given a sequence of N hashes" is a bit of a deus ex machina here :)
        • zeckalpha 13y ago
          Create it using 50% of your lifetime. Or create one for your children.
  • tlrobinson 13y ago
    I don't see how this would work. What key is the encryptor supposed to use to encrypt?
  • tetha 13y ago
    This should still be fairly parallelizeable, shouldn't it? You go ahead and take a number of crackers. Each cracker starts with a random hash and randomizes it for a fixed number of times, or until the bottom 8 bits of the hash are 0. Once it is done hashing, it goes to a central database and stores it's hash sequence. After that, it picks another hash which is not contained in a hash sequence and repeats the process. Finally, you'd probably have one node just doing the boring hash iteration while checking if it can skip according to the generated hash sequences from the database. I haven't done any math how much of an improvement this would be, but I would suspect a pretty decent improvement given enough nodes.
• pbaehr 13y ago
  This is interesting in its own right, but the Assange use case doesn't really make sense to me. Wikileaks doesn't want the encryption to be broken after a certain amount of time, they want it broken based on the condition of assassination.
  • arielweisberg 13y ago
    The primitive for this is a dead man's switch. I wonder what the cryptographic equivalent would be. Some sort of computational network that will always make progress towards decrypting the data unless the soon to be dead man injects something using his private key that sets the network back preventing completion? The network can't identify that the soon to be dead man is preventing progress? Sounds like a fun research project. Maybe tie it to some coin mining network.
    • betterunix 13y ago
      The problem with using a secure protocol is that you need to trust the parties to not just instantiate a second version of the protocol without you. If you can trust them to do that, you can just give them shares of the secret and trust them not to recombine the shares unless you die.
      • arielweisberg 13y ago
        I think what you would do is make it computationally infeasible for them to create a separate network. The network exists independent of your individual secret and may be working towards the release of many soon to be dead men's secrets in a peer to peer fashion. Sure they could avoid the dead man injecting something, but then they would get hit with the full workload. If you coupled this with an economic incentive like bitcoin mining you could get the miners to allow you to drastically increase the amount of work required and make it keep up with the state of the art in technology. I couldn't say whether you can string enough primitives together to build something like this but it would be really cool if you could. Maybe I should go file a patent or something :-P
• im3w1l 13y ago
  I think I have a better scheme. Say you have a 10 bit keyspace or something, and then encrypt a very large number of times with random keys. You don't have to perform as much computation as your adversary. By the law of large numbers the probability to solve all of the puzzles in a much shorter then expected time is low. And it is much less parallellizable then just one encryption with a random key.
  • Strilanc 13y ago
    That sounds risky. You're using a cryptographic primitive in a non-standard way, and in danger of having created a weakness. For example, are you sure that your cipher doesn't have the property that for any text.Encrypt(key1).Encrypt(key2) there's an equivalent text.Encrypt(key3)? Some ciphers have that property (e.g. the one time pad). That would reduce your security from 10^N to... 10.
    • im3w1l 13y ago
      The article is about research on time lock systems, not about someone actually building one. Thus I think a speculative, "risky", novel idea is appropriate.
  • deleted 13y ago
    [deleted]
  • ColinDabritz 13y ago
    Interesting idea, I like the "as much certainty as you want" with the probability. Why can't this be parallelized? Sure you have to work on one key at a time because they are sequential, but 1000 machines can be cracking that one key. Every key cracked would be distributed and the cluster would start in on the next. It's a little more complicated, but I'm not seeing how it's really any less parallelizeable.
    • im3w1l 13y ago
      I think, but am not certain, that with such a small keyspace the IO cost would dominate if you tried to parallelize it. (Assuming each decryption attempt is rather quick).
• deleted 13y ago
  [deleted]
• bteitelb 13y ago
  If only there were a series of mirrors, each N light-years away, you could blast a one-time pad out to the mirror of your choice and then announce the date the reflection is expected to arrive.
  • 3pt14159 13y ago
    The use of black holes here could work, if you had an accurate enough representation and or a large enough receiver dish. Fire your one time pat just in front of a moving black hole and have it circle back through the gravity well before the black hole moved on.
  • batbomb 13y ago
    It'd probably be easier to design an ultra-long delay line ASIC that internally maintains a state for a certain count of clock cycles, and spits it out after a while. It might still be possible to do a cryogenic attack, but that wouldn't be very easy to do. Or maybe some sort of superconductor/magnetic state device.
  • simbolit 13y ago
    Nice idea IF we had such mirrors. Afaik the farthest away is on the moon.[0] Also a one-time pad needs to be as large or larger than the data used to encrypt it.[1] So your plan cannot be used for the several gigabytes wikileaks insurance file. But perhaps you can "pad" the key used to encrypt it? Probably. [0] http://en.wikipedia.org/wiki/Lunar_Laser_Ranging_experiment http://en.wikipedia.org/wiki/Lunar_Laser_Ranging_experiment [1] http://en.wikipedia.org/wiki/One-time_pad http://en.wikipedia.org/wiki/One-time_pad
  • croikle 13y ago
    It's a cute idea, but you have 1/r^4 intensity scaling, which is prohibitive even at lunar distance. The lunar ranging experiments receive "one photon every few seconds" [1]. You could probably do better with bigger equipment, higher power, and perhaps an orbiting base station to skip the atmosphere, but the numbers are going to win before too long. An active repeater would give you 1/r^2, though. For example, you could ping Voyager I for a 36-hour delay. However, that's likely not feasible at light-year distances, let alone the problem of getting the devices there. :) [1] http://www.jpl.nasa.gov/news/news.php?feature=605 http://www.jpl.nasa.gov/news/news.php?feature=605
• karl_gluck 13y ago
  I like the parallelized hash chain construction idea; I've never seen that before. One could improve a chunk of the chain by having checkpoints along the way. As the author mentioned, it would suck to be 2 years into mining a 35-year computation, only to make a mistake that you can't detect until the very end. To add checkpoints, one could release both the original seed of the chain A, and a number of pairs of hashes (x0,y0) (x1,y1) ... Let's say you wanted to do 1-month chains. Hash the seed A for a week, then take the current value x0 such that H(B)=x0. You know the value of B, since you've been computing the chain. Pick another random value y0, and continue the chain with H(B^y0). Write (x0,y0) in the output, and hash for another week. Do the same for (x1,y1) (x2,y2) and (x3,y3). Each chain then has a seed value and 4 pairs of 'checkpoints'. When unlocking the crypto puzzle, these checkpoints can't be used to jump ahead in the computation, but they can tell you that you're on the right track. I think that you could even use a secondary hash chain for the y_n values, so y_n+1=H(y_n). If you also derived y0 from A (e.g. y0=H(A^const) ), you would just need to publish the seed value A and each checkpoint hash x_n in order to have a fully checkpointed crypto puzzle.
  • deleted 13y ago
    [deleted]
  • cbhl 13y ago
    One problem I can see with that is you have to be very careful that your hashes (x_i, y_i) don't make it more attractive to, say, solve the n-1th computation (similar to brute-forcing a password hash) than to do the first 1..n-1 computations properly.
    • karl_gluck 13y ago
      Good point! Still, I think the best hash inversion I've seen is slightly under 1/2 the hash space (2/5ths?). Using a 512-bit hash like SHA3, even at an ungodly hash rate (1 TH/s), you still get approximately 2^141 seconds = 2^133 years maximum chain length before it becomes more efficient to invert the hash.
    • dsl 13y ago
      This is a pretty well understood construct, called hash stretching. The correct implementation is in each (or every 5h, etc) iteration you test if the key is valid by trying to decrypt, then continuing if unsuccessful. That way the attacker has no idea what n is.
• geedy 13y ago
  Correct me if I am wrong, but this assumes that processor speed will not increase dramatically over the lock period, no? Seems to me that if one was to be storing information over an extended period of time, say 20 years, as time goes on, it becomes more and more likely that the encryption can still be broken sooner than desired.
  • DanBC 13y ago
    Rivest's puzzle (1999) http://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt http://people.csail.mit.edu/rivest/lcs35-puzzle-description.... assumes that we're all using 10 GHz processors in 2012. > The value of t was chosen to take into consideration the growth in computational power due to "Moore's Law". Based on the SEMATECH National Technology Roadmap for Semiconductors (1997 edition), we can expect internal chip speeds to increase by a factor of approximately 13 overall up to 2012, when the clock rates reach about 10GHz. After that improvements seem more difficult, but we estimate that another factor of five might be achievable by 2034. Thus, the overall rate of computation should go through approximately six doublings by 2034. I asked about progress on this puzzle at stack exchange here http://crypto.stackexchange.com/questions/5831/what-is-the-progress-on-the-mit-lcs35-time-capsule-crypto-puzzle http://crypto.stackexchange.com/questions/5831/what-is-the-p... and got some nice answers.
    • simbolit 13y ago
      Disclaimer: I have no idea what factors are relevant for cryptographic functions. In 1999 they had coppermine 1133 single-core @ 1.1ghz (~ 2 gflops), in 2012 we now had sandy bridge 3970 quad-core @ 3.4ghz (> 100 Gflops). So at least according to one measure the factor of increase is more like 50 than 13.
• romaniv 13y ago
  1. Generate a random number. 2. s- or bcrypt it. 3. Encrypt the data with the result of step 2. 4. Give people most of the random number, minus N bits at the end. (And tell them how many bits they are missing.) They will have to run s/bcrypt (N^2)/2 time to get your date. Am I missing anything?
  • karl_gluck 13y ago
    The issue is that you can parallelize the "unlocking" operation. So, if one person is attempting to unlock, they solve in 10 years. If two people attempt, it's solved in 5 years. If the NSA puts all their computers on it, it takes 1 second. The author is proposing methods that are forcibly sequential.
• 3pt14159 13y ago
  In reality the easiest solution for this would be to build yourself a time release cellphone or something. A simple time release power switch pulls, then the phone tweets the key to a strong encryption scheme. Build the phone into the walls of a cafe or something, maybe a bit of redundancy (multiple cafes) / and photosensors to detect discovery and disable/destruct the phone. If you split the key redundantly between the phones, you should be fine.
  • walrus 13y ago
    That doesn't sound very easy.
  • simbolit 13y ago
    And now you don't have to trust the math, but all kinds of things in the physical world. A photo sensor for example is disabled by darkness. Digging up the phone by night, anyone? Bad idea, IMHO.
    • jlgreco 13y ago
      IR LED for illumination, use the camera to detect movement where there should be none. It would burn a ton of power though.
• currymesurprise 13y ago
  gwern, if you're reading, this section is misleading if not wrong ...: "But that doesn’t seem very true any more. Devices can differ dramatically now even in the same computers; to take the example of Bitcoin mining, my laptop’s CPU can search for hashes at 4k/sec, or its GPU can search at 54m/second." This is an example of parallelism and parallelism only.
  • gwern 13y ago
    Are you implying that GPUs execute each hash as slowly as a CPU and are better at hashing simply because they have more processing elements? I knew GPUs had a lot of small cores, but I was unaware that mine had 54000000 / 4000 = 13500 cores.
    • Dylan16807 13y ago
      I think you were using a bad algorithm on your CPU. Assuming any half-recent x86 processor you should be looking at a number like 4 Mhash/second, not 4K.
    • currymesurprise 13y ago
      More or less, yes, that is my implication. Luckily, my sibling comment provides some extra information. For the example of SHA-1 computation, you mention using FPGAs that finish in 400 clock cycles, which is at most an order of magnitude away from a naive CPU implementation of around 4000 clock cycles. I'm not as familiar with SHA-256.
• logicallee 13y ago
  Under the third section "hashing" it says: >For example, one could take a hash like bcrypt, give it a random input, and hash it for a month. Each hash depends on the previous hash, and there’s no way to skip from the first hash to the trillionth hash. After a month, you use the final hash as the encryption key, and then release the encrypted file and the random input to all the world. The first person who wants to decrypt the file has no choice but to redo the trillion hashes in order to get the same encryption key you used. Then it lists this downside: >"This is pretty clever. If one has a thousand CPUs handy, one can store up 3 years’ of computation-resistance in just a day. This satisfies a number of needs. But what about people who only have a normal computer? Fundamentally, this repeated hashing requires you to put in as much computation as you want your public to expend reproducing the computation, which is not enough. We want to force the public to expend more computation - potentially much more - than we put in. How can we do this? >It’s hard to see. At least, I haven’t thought of anything clever" I have! Rather than hash n as your seed, after finding n (which you will still release) hash (n+m) instead, where m is a random number in the range (for example) 0,100. Discard m, do not retain it after you've started the hashes. Release only n. Now, rather than starting at n, they still have to start at n, then when they find that m wasn't 0, they have to try all over again hashing n+1 a trillion times, then when they find it's not a good key, they have to try hashing n+2 a trillion times, and so on until they've bruteforced n+m as the correct initial seed for the start of the hash process. i.e. you make them bruteforce what m must have been. if m is ten, someone would have to repeat your process up to ten times (an average of 5 times) before they found the seed. Likewise if m is large, like 1,000,000 the force multiplier is 1,000,000x as much work as you had to do, in the worse case and 500,000 times as much work on average. I've emailed the offer this suggestion.
  • josephg 13y ago
    This has the same drawbacks as using a small random key, which the article discusses later on: - They might find the key earlier or later in their search (it adds volatility to the amount of time required). - Searching for the right value of m is highly parallelizable.
    • logicallee 13y ago
• deleted 13y ago
  [deleted]
  • dmd 13y ago
    Isn't that exactly what the article said? or did I misunderstand?
    • oconnore 13y ago
      (oops, yes, I didn't read it very carefully)
• atlbeer 13y ago
  How secure is http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing ?
  • chrislipa 13y ago
    It's a really beautiful and easy to understand and genius algorithm, and it perfectly meets its design goals. It works very analogously to the following: Pretend your secret is an integer. You want to distribute clues as to your secret integer to N of your friends such that any K of them can collude to figure it out, but K-1 of them can't figure out anything about it at all. So you construct a (K-1)-degree polynomial of one variable, f(x). All of the coefficients of the terms of f(x) are random, except choose the y-intercept (i.e. the constant co-efficient) to be your secret. Then calculate and distribute the numbers f(1), f(2), ..., f(N) to your N friends. K points on the 2D co-ordinate plane uniquely identify your single (K-1)-degree polynomial, which will have your specific secret y-intercept. However (K-1) points will pick out an entire family of potential (K-1)-degree polynomials. And, in fact, for every single possible secret you could have chosen, there's a (K-1)-degree polynomial that goes through (K-1) points and the possible secret value. So, (K-1) of your friends colluding really don't have any additional information at all about your secret. Shamir's secret sharing works just like that, but done with integers modulo a prime. (And the prime has to be larger than your secret.)
• ye 13y ago
  Schedule a google calendar event in the future. Set up an email alert so it sends the key to an email. This assumes google isn't going to discontinue its calendar service.
  • nwh 13y ago
    Might be an unfortunate assumption.
  • r00fus 13y ago
    You're also trusting Google here, as your key must be accessible by google calendar's event in order to send.
    • ye 13y ago
      So? To google it looks like a random character sequence. They don't know what it is. It can even be encrypted, if you're that paranoid.
• zellyn 13y ago
  There are also real-world solutions. I spent some time brainstorming this a while back. 1) The safest solution, albeit somewhat expensive: launch a Voyager-like probe. It constantly generates private and public key pairs, broadcasting the public keys immediately and the private ones on a schedule. That way, you can pick a known timeframe for decryption. Launching more than one probe, for redundancy, is probably a good idea: you can encrypt with multiple keys. 2) Cheaper but less reliable solutions involve balloon-dropping transmitters that wake up and divulge decryption keys across a huge geographic area where it would be infeasible to find them. A variation is sinking modules very deep in the ocean that wake up and float to the surface.
  • tlrobinson 13y ago
    That would be a cool use of a CubeSat (as long as it never becomes worthwhile for a wealthy entity to go snatch it out of orbit...)
  • sirsar 13y ago
    What about launching a probe that echoes any signals it gets? If it were sufficiently far away, one could send it the private key and destroy the local copy. Nobody's going to leave from Earth (or wherever) and catch up to your private key!
    • TeMPOraL 13y ago
      And even if they did, barring FTL, they couldn't really get it down here faster than the probe itself.
    • pavel_lishin 13y ago
      Since you're launching the probe well in advance of sending out the key, a sufficiently well-funded and a paranoid party could send a probe that just trails yours, intercepting your signal and beaming it back to the party in question (encrypted with their private key, of course.)
      • xlayn 13y ago
• chrislipa 13y ago
  Maybe there's still a way to use homomorphic encryption. gwern rightly suggests that it causes a big problem if the recipient must decrypt the result of an encrypted computation. However, what if the decrypted result of the computation is never known to the recipient and instead the recipient must use the still-encrypted result of the encrypted homomorphic computation? It would work like this: The secret sharer creates some random string called 'a' and some computable function 'f'. The secret sharer also creates an encryption function 'e', and a homomorphic equivalent to 'f', called 'F' so that the following commutes: e(f(x)) = F(e(x)). F acts on encrypted data and gives encrypted results, but is much slower than f. The secret sharer can comparatively quickly compute e(f(x)), which he or she uses as a key to encrypt a message. However the recipient is only given the values e(x) and F and must use exponentially more computational time to go the more laborious route, computing F(e(x)).
  • dsl 13y ago
    That is effectively a proof of work scheme, which is what most time lock systems are based on. The fundamental problem is that people with more resources can decrypt faster than people with less resources, and you're generally wanting to share with someone who has less not more.
    • chrislipa 13y ago
      You make a good point, but that's also a shortcoming of all of the purely computational techniques. I think the most you can hope for is 'democratizing' the computational methods, i.e. making them non-parallelizable. Taking gwern's idea, what if the homomorphic computation is just incrementing your input repeatedly inside of a loop? It seems like that might be hard to parallelize. Or at least, I don't know enough to assume otherwise.
• dangayle 13y ago
  This sounds like the ideal opportunity to have a map tattooed to our scalps like old fashioned pirates. Or to the back of some kid (like on Waterworld).
• emiliobumachar 13y ago
  Prepare ordered sterile Petri dishes with nutritious solution. Expose some to bacteria, forming bacterial cultures, but not others. Ones and zeroes. At first, they will be almost impossible to distinguish (you cannot hurry much your culture medical exams even if willing to spend a lot, right?) After a while, the cultures become obvious. The timing is heavily dependant of the bacteria's life cycle, but I guess if you stricly control the number of individuals initially put into the dishes, and keep temperature and lighting optimal, you can predict the time-to-observability to around 40%?
• Cyranix 13y ago
  Not directly related to this article, but gwern.net seems to be coming up on the front page quite often. Is there an RSS feed for the site? I was unable to find one.
  • malcolmmcc 13y ago
    Gwern posts articles, but not in blog format. If you look on the sidebar for this page, for example, you'll see it was originally published in 2011, and just recently modified. This is the closest thing to what you're looking for: http://www.gwern.net/Changelog http://www.gwern.net/Changelog
    • Cyranix 13y ago
      Ha, close enough I suppose. Thank you!
  • gwern 13y ago
    There is an RSS feed, although your browser may not be displaying it to you.