Mahadev's result is excellent by any standard and remarkable for a graduate student. It's both impressively creative and technically novel. But quantum verification has not been solved, and the headline is wrong.
In essence, Mahadev developed a quantum verification protocol that relies on a post-quantum secure cryptosystem. She used an encryption scheme based on the the Learning With Errors (LWE) problem, which is one of the foremost intractability assumptions in post-quantum cryptography research. It's a great idea and a novel approach based on the marriage of two related fields of research.
But the jury is still out on whether or not the LWE is actually post-quantum secure (likewise with other intractability assumptions). It probably is, but there are reasonable and credible arguments against lattice-based problems generally and the LWE family of problems in particular (which is one reason proposals based on isogenies, error correcting codes, hash-based signatures and multivariate polynomials are also under active research).
Mahadev's real achievement is not solving quantum verification - but it's possible this will lead to that result. Rather as a direct result of her work we can now conclude one of the following must be true:
1. the LWE problem is not post-quantum secure, or
2. we can verify quantum computation.
That's a win-win for both the quantum computing and theoretical cryptography research communities.
I have suggested elsewhere that a logical next step in this research is to take Mahadev's framework and "port" it to another theorized post-quantum secure intractability assumption. My reading of Mahadev's paper is that her methodology is probably modular enough to support swapping out the LWE with any other family of post-quantum secure assumptions, not just lattice-based ones. She does highlight a few parameter choices taken from one of Gentry's lattice schemes for fully homomorphic encryption (FHE), but I don't think that should pose a significant obstacle to changing the intractability protocol.
This would be very interesting because it might result in nontrivial changes to the speed or efficiency of the quantum verification system. Post-quantum cryptographic systems have different trade-offs depending on their underlying intractability assumptions; I'm interested in whether and how that would surface in quantum verification as well. Another very interesting route for further research is seeing where else cryptographic protocols can be used for creatively solving open problems in verification more generally. But that's already an active area of investigation.
I sincerely believe we should treat quantum computing discoveries as (long term) major 0-days, as in they should sent in confidentiality to sensitive sectors's actors, those that depend heavily on classic encryption.
Or perhaps if it is believed we are close to making a quantum computer that can easily break classic cryptography we simply assume it's broken instead of waiting for the first person who wants to tell us publicly? I don't see why quantum research should be held up more than any other area when it comes to zero days. If we are going to trust people to be forthcoming I think we can trust them to decide if it should be sensitively announced.
If you listen to natsec or intelligence Podcasts you'll hear these people stressing over quantum. We need quantum proof algorithms today, not ten years from now. For symmetric encryption this is easy, unfortunately the vast majority of our encryption protocols bootstrap with PKI.
I've come to the view that because we have a physical safety problem with cyber now (cars, drones, etc) we should be shipping devices with hardware enforced one time pads and the update procedure should incorporate them with a layered approach (ie, encryption + OTP).
Yes physical security is hard and OTPs shouldn't be used most places, but if the factories or update servers for Tesla are physically owned we're fucked anyway so we already have a physical security problem. Why solely trust in cryptographers that have routinely underestimated the risk of algorithmic or side-channel breach? I really want my mind to be changed here, because I don't like having opinions that are way outside the mainstream, but no matter how I dice it I don't see why we shouldn't be employing OTPs.
Presuming you mean One Time Pads, they are an exagerated solution. If I want to send you 1GB of data, we should not require 1GB of shared secret random data.
A setup where you have e.g. 4kb of shared secret data, and use that to communicate fully randomly generated keys. Then those keys are used with symmetric encryption for the full transaction.
The main issue with this is the 'shared secret' part. How would you do 'code signing' with an OTP? You'd need a shared secret with the developer. The developer can't possibly have a different shared secret with each user, and even if they could, it would mean that every user would need a different signature on their binary. So instead, there is one secret shared with everyone.
But if Alice, Bob, and the Dev all have access to the shared secret, then Alice doesn't know whether Bob or the Dev made the signature. This can partially be solved by secure enclaves, but if you have the same secret on a million secure enclaves, it becomes feasible to extract that secret. Besides, it seems quite probably that secure enclaves also have side-channels.
Asymmetric cryptography doesn't have this issue, because you don't rely on a user having only partial access to some data. For many interactive things, a 'chain' of shared secrets could probably be used to set up a secure channel. But for off-line usage such as attestations or proofs of authorization, that isn't possible.
PKI does suck, but the biggest issue is authenticating keys, not the use of weak algorithms.
Yes, I didn't capitalize it, but I did spell out OTPs in my original post.
Here's the part where CompSci people lose me:
> If I want to send you 1GB of data, we should not require 1GB of shared secret random data.
I agree if the data is something trivial like video but it doesn't follow to me that OTPs shouldn't be used for something as critical as code updates for autonomous vehicles control systems.
> How would you do 'code signing' with an OTP?
We don't take anything away. We don't discard our normal cryptographic methods of encryption and code signing. We simply layer them. That way if the cryptographic method is flawed, or the keys compromised, an attacker would also need to compromise the OTP.
Just as structural engineers layer their defences for structural collapse, I fail to see how introducing a OTP presents a serious burden to autonomous device makers compared to the stakes involved. It makes class-attacks far less relevant because the OTPs would need to be breached too.
Even if our OTPs were solely used for the cryptographic signature (as opposed to the whole encrypted code update) we would still be leagues better in the event of a compromise. I know we shouldn't need to, but mistakes keep happening. I know we shouldn't trust physical security over cryptographic security, but if we're layering them how does it hurt?
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.
> it takes a trusted channel between both end points to establish a good OTP. This alone is hard, very hard!
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!
We create the pads. We put one in the car and one in a locked case. We open the case in the server room and plug it into a large bank of pads. When updates are necessary they're run through the pad and broadcast.
If an auto company can't keep pads synced or keep pads physically isolated from malactors I really think we have bigger issues at hand. Syncing a pad could be as easy as requiring them to be read per-megabyte, with unused pad where not required, though I'm sure there are countless better ways.
> OTPs are just not worth the trade-off with respect to symmetric encryption.
I agree that if it were a choice between OTPs and symmetric encryption I'd go symmetric encryption every time, but I fail to see the downside in layering them. Further; I've seen symmetric encryption implemented insecurely in practice even if it is theoretically more secure than OTPs or PKI.
I appreciate you entertaining my questions, and I apologize if I'm inadvertently being obstinate. I really want to understand why I'm wrong here, but I still don't see it.
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.
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.
The lack of inspectability, it seems to me, would make quantum computing flat-out unacceptable in a variety of problem domains, including pretty much any decision support system. Not theoretically, so much as socially. In the way nuclear reactors are unacceptably risky to many who accept a far higher death toll associated with roofers falling to their deaths installing solar. Sure nuclear saves lives, but my aunt doesn't understand it and she finds it scary.
I think it's quite "rational" to find nuclear power far scarier than rooftop solar. The tail risk of nuclear power is Fukushima. I'm not even sure what the tail risk of rooftop solar would be. The average case outcome between these two isn't compelling for me.
I have a B. Eng. in chemical engineering, unlike "your auntie" I understand nuclear plenty, and still think, with most everyone else educated and uneducated alike, it's MUCH more dangerous than solar.
I’m a big proponent of nuclear energy. The benefits far outweigh the risks. But solar power has never rendered an area of the planet uninhabitable, so I understand the concern.
I have a degree in physics, am now a doctor studying cancer, lived on a nuclear aircraft carrier, and was sent to Japan to help with the Fukushima response. I'm not sure I agree about the danger of nuclear, but the lower energy levels involved in solar make it so much more politically attractive, there's not much sense in pursuing new civil nuclear production.
