Honestly, I can't really feel exceited about this. It's a fun bit of cryptography, but in the end, it would be yet another tool to lock down devices even more -

Honestly, I can't really feel exceited about this. It's a fun bit of cryptography, but in the end, it would be yet another tool to lock down devices even more - if it worked. However, my impression is that it wouldn't work really well in practice anyway, even if the "delivery problem" for OTMs were solved. My understanding of the whole thing is as follows: The "program" in "one time programs" is a function f(x) -> y that takes a bitstring of some fixed size as input and outputs a value y. (So really f(x1, x2, ..., xn) -> y). The function is also pure, meaning if you input the same bitstring, you'll always get the same output. The task at hand is as follows: There is an untrusted second party "Bob". You want Bob to pick one particular bitstring, calculate the function on it and retrieve the value. But Bob must not be able to pick a second, different bitstring after it and calculate f() on that one too. (So "can run the program only once" really means "can only run the program on one particular input" - but because the function is pure, that's essentially the same) This implies that Bob must not know in detail what f() actually calculates, otherwise he could just reimplement the function and run as many inputs on their version as he likes - yet he is the one who is supposed to do all the calculations. How can this work? Answer: You don't hand Bob the f() itself, but a "garbled" version of it, fg(). I have no idea how this garbling works, but apparently it leads to the following things: - For each bit that f() takes, fg() takes a 128-bit key. So if f() has 10 inputs, fg() will have 1280 inputs. - For each input position and each value, there is a secret key ("label"). I.e. there is one key for x1=0, another key for x1=1, a third one for x2=1, etc etc. - If you input the appropriate labels for your bitstring, fg() will output the same result as f(). If you input anything else, fg() will output a random nonsense value (I think - the article doesn't go into detail here) - The "garbling" operation somehow magically makes it so that you can neither reconstruct f() nor any of the labels from just fg() - or at least not by statically analysing fg(). So before Bob can input his bitstring, he has to convert it to the appropriate set of labels. Bob would like to have a conversation table with all the labels on it, but of course you don't give them that. Instead, you hand Bob a bunch of One Time Memory devices. There is one device for each input position (so one for x1, one for x2, ...). Each device can be queried once for either 1 or 0. It will return the appropriate label and then self-destruct. So if Bob gets to know the label for x1=0, the device ensures he'll never get to know the label for x1=1. So if Bob has a bitstring "11001" and he wants to know f("11001"), he can call $labels := ask_otms("11001") to get the labels, then fg($labels) to get the value. But after that call, ask_otms() will be broken and he cannot obtain the labels for any other input. ---- That's all well and good, but in the end, Bob still knows fg() - and can run all kinds of experiments in the hope to get f() back, or at least learn the missing labels. In particular, as soon as he has a way to distinguish "garbage" results from fg() from "non-garbage" results, he can try to brute-force the labels. So the only way to prevent bruteforcing seems to me is to ensure that Bob can never know if an output from fg() is garbage or not garbage. And that's a constraint that is very easily broken if you use the function in the wrong context. For example, suppose I want to use an OTP for signing: I want to "borrow" my private key to Bob, so he can sign one piece of data with it, but only one. I prepare my function fg() so that it produces a valid signature if the correct labels are input and a random value otherwise. fg() contains my private key, but that's ok as the key is garbled and unretrievable. I also hand Bob a bunch of OTMs which contain the labels. Bob can call fg(ask_otms(data)) to obtain the signature. However, suppose my public key is widely available, as is usually the case for public keys. Then Bob can do the following: - Take the result from ask_otms(data). Say for Bob's data, the value for x1 is 0, so he knows the label for x1=0 but not for x1=1. - Change the label for x1 to some new value and apply the new set of labels to fg(). - Verify the result from fg() using my public key to see if it's a valid signature. - If it is, Bob just found the label for x1=1. - If it isn't, Bob has to try out more keys. In the worst case, Bob has to brute-force 2^128-1 keys for each input. That's a lot, but it's also an "embarrasingly parallel" task: Bob can can try out each key in isolation as well as brute-force each input in parallel. Also, the OP contains this note about the "garbling" operation: > (And it gets worse: if Bob obtains two labels on the same input wire, the entire garbled circuit construction will often unravel like a cheap sweater.) This suggests that it might be enough to brute-force one additional label, then Bob can simply reconstruct f() and obtain my private key! This means that suddenly, both my keys are sensitive: The whole scheme only stays secure if I keep my private key and my public key under wraps! Another scenario: This time, I keep both my keys secret, but I want to allow Bob to sign up to two pieces of data independenly. So I build a function f() which contains my private key, then produce two garbled functions from it, fg() and fh(), each with its own set of labels. I send fg() and fh() to Bob and ship them two sets of OTMs with the labels. However, Bob knows: - If he supplies invalid labels to fg() and fh(), the functions will very likely produce different results. - If he supplies valid labels that correspond to the same bitstring, the functions must produce identical results (as they both must produce the same result as f() would for that bitstring). So Bob can do the following: - run fg(ask_otms_for_g("00000...")); store the result as $yg. - run fh(ask_otms_for_h("10000...")), i.e. use a bitstring which only differs in one bit from the one for fg(). - run fh() again and brute-force all possible labels for x1. - if for some value, fh() produces the same result as $yg, the value is a strong candidate for being the correct label for x1=0 on fh(). Once Bob has both the labels for x1=1 and x1=0 on fh(), he can try to "unravel" fh() and get back f(). So I think even if the problem how to deliver OTMs was solved, there is still an enormous amount of ways how you could shoot yourself in the food by using OTPs.