[mc-lovin]

>But one of the other requirements set forth in the paper is that if the slab is stolen, Eve must not be able to send or receive messages. I'm not sure how that is fulfilled here.

If a "full" message involved both sides randomly picking a P, then this could still be satisfied.

But it doesn't seem to live up to my hopes for security: all it really guarantees is that the probability of Eve decrypting an intercepted message (assuming she steals the slab for time t and knows all the P's) is t/T where T is the time Bob and Alice spend generating K(B) + K(A) for different P's.

[ReidZB]

When I woke up this morning (and was in a better state of mind), I realized the supplements may have been on the arXiv page but not included in the paper. I was correct. Here [1] is the supplement paper, which I find more useful than the actual paper itself.

It appears I was correct about the stolen CPUF leading to decryption of previous messages; in supplement G, at the bottom of (2), the authors state:

"Finally, it is worth noting that with a stolen device and access to the public dictionary, an attacker Eve may be able to quickly decrypt any of Alice and Bob’s previous communication that she may have saved(since Alice and Bob publically share which SLM patterns they use each round). For this reason, it is highly beneficial for Alice and Bob to utilize a second layer of encryption to ensure that any eavesdropper cannot determine these previously shared patterns, as discussed next."

They also discuss other security properties of the scheme in supplements G and H, which are both excellent.

[1]: http://arxiv.org/src/1305.3886v1/anc/CPUF_Supplementary_Mate...