Grad Student Solved a Fundamental Quantum Computing Problem

OTPs come with a lot of overhead. In order to get value out of them, it takes a trusted channel between both end points to establish a good OTP. This alone is hard, very hard!

There are significant size issues, but those are solved by replacing an OTP with a fixed size key K that is expanded somehow. eg a stream like

    [ sha(K, 1); sha(K, 2) ... ] 

Though to be honest I am just reinventing AES-CTR here. However, besides this the biggest issue is keeping state. You don't just need to keep all of the shared keys, but you need to remember and be synchronized on where in the stream you are.

In the end, essentially all you want to achieve can be done using AES-CTR or really any kind of symmetric encryption. In general, symmetric encryption has been pretty reliable. OTPs are just not worth the trade-off with respect to symmetric encryption.

One time pads are theoretically more secure than any other form of encryption. If implemented correctly they offer information theoretic security, whereas modern encryption schemes can only provide computational security.

Information theoretic security essentially means that we cannot learn anything whatsoever about a plaintext from a ciphertext. There exists no information leakage.

In order to achieve this we need to 1) use an encryption key at least as long as the plaintext, 2) generate that key secure and (truly) randomly, and 3) never reuse that key for the duration of the session. Computational security was invented (in part) because this is a completely unrealistic ideal to strive for in approximately all communication. If I want to securely send you an plaintext with a size of 1GB, I need to first securely generate a truly random 1GB string and exchange that with you. Since that secure exchange would obviate the encryption in the first place, it's more likely I'd generate a significantly larger key and exchange that with you first, then only use as much of the key as necessary for each exchanged message in the session.

This makes one time pads extremely inefficient - in order to achieve the information theoretic advantages of one time pads all messages must be doubled in size and no part of the key can ever encrypt the same part of the text. It's effectively a stream cipher. If you and I encrypt recurring metadata, or we reuse common idioms or greetings under the same key, we immediately lose information theoretic security. Then we're downgraded to a ridiculously inefficient stream cipher with computational security. At that point we might as well use AES, or ChaCha-Poly.

One time pads are used (typically by the government), but it's very uncommon and reserved for areas where literally no expense is spared. The purpose of computational security is to make cryptography more efficient and practical via a simple tradeoff. We get disproportionately more efficiency back by accepting infeasibility instead of impossibility.

Does that help clarify things for you?

Ok, I think I'm getting closer to understanding your point.

> Right, and this is why we don't use them for arbitrary communication between networked computers, but for manufactured cars (or other cyber-physical devices) we have a trusted channel already! The factory that builds the car!

So what exactly do you want to use the OTP for? Just for updates to the cars, or are there other forms of communication you'd want to see extra protected. Next, what exactly do you wan to ensure about a message? There are 3 properties we commonly seek to ensure (also referred to as C I A):

* Confidentiality, i.e. the public can't read the messages * Integrity, i.e. the message that arrived is the message that was sent. * Authenticity, i.e. the message came from a trusted source

A very simple OTP with xor-ing only gives Confidentiality. I suppose you could append some HMAC of the message, using part of the OTP for the key to ensure Authenticity and Integrity. Note that without this, I can flip any bits I want in your OTP encrypted message just by flipping random bits in the ciphertext. For something like a firmware update, that would be a problem.

There is also the question of the order of the layering. Do you OTP-then-Encrypt or Encrypt-then-OTP? To be honest, it seems like the layering is useless. As using a full OTP with HMAC is already enough to give CIA.

In the end, I'm still not sure of the significant advantages of an OTP over something like AES-GCM with a key shared between the device and the manufacturer. Especially because you need to include the HMAC, which introduces some of the complexity you seem to want to avoid. Really, the biggest downside of AES-GCM is that you need decent randomness for the nonce (though I believe you can deterministically derive the nonce from the message).

The reason your choice for an OTP over symmetric encryption like AES-GCM really confuses me is because I don't see the benefit of the guaranteed Confidentiality of an OTP in this case. Really, Authenticity and Integrity are what matters here.

I would also note that something like AES-GCM with a unique key per vehicle is already far from reality. In any case, you still need a way to keep bad guys from getting the secret key from your car. Moreover, it seems to me like any kind of engineering to create a decent 'secure enclave' could also be spent on verifying your symmetric encryption is actually 'done right'.

Note that in this case, any push of data to a vehicle needs to a fully on-line connection between the factory and the car. No possibility for an intermediate CDN. With something like AES-GCM you could at least prepare a message for every car and deliver it asynchronously. This would ensure it is still possible for a mechanic to do a physical update in the case an internet connection has been fried. But for a true OTP, to ensure the pads remain sync, that cannot happen.

I could see going for the AES-GCM route to protect against quantum decryption, but beyond that, I don't see the issue with using normal assymetric crypto.