The sideways view

My phone is protected by a 4-digit PIN. I’d like to make it hard for an attacker to read information from my phone without knowing the PIN. Unfortunately, there are only 10,000 4-digit PINs, so it won’t take long to guess the right one. What to do?

The standard solution involves tamper-resistant hardware. A trusted chip on the phone can store my encryption key, only reveal the key if the PIN is guessed in the first 10 tries, and self-destruct if anyone tries to mess with the chip (e.g. to extract the key).

I don’t know how secure tamper-resistant hardware is. I don’t see much reason that defenders should be able to beat attackers in this game over the very long run. There have been some high-profile failures of phone encryption, which weren’t state of the art but are still a troubling sign. Wikipedia makes the situation sound bleak. (A reader can correct my ignorance here.)

This post presents an alternative proposal, in which security is based on a computational assumption (!). This is impossible classically, but is achievable if (a) we have quantum storage, and (b) there is a gap between the amount of memory available on the phone and the amount of quantum memory available to an attacker.

The assumptions

We require the ability to store stable individual qubits. We don’t require any entanglement. All we need to do is prepare qubits in one of four states (0, 1, +, -) and measure in either the standard or Hadamard basis.

All of the data on your phone will get wiped if too many of the qubits decohere, so they need to be very stable. And we need to store ~200 of them. And of course it’s a phone, so you need to do it at room temperature with basically no power consumption. Yes, it’s a big ask. But again, no coherence or complex preparations, so it doesn’t seem totally out of the question.

We need some function H which behaves like a random function and is easy to compute on the phone, but would be prohibitively difficult for an attacker to compute in quantum superposition. For example, H might require a gigabyte of RAM. A gigabyte of quantum memory is really a huge amount, no one would be able to compute H in superposition for quite a while, but could still be computed very fast on your phone.

(I don’t actually know whether we’ll have ultra-long-lived room-temperature qubits before or after very large quantum computers, it could go either way. But probably the gap in time will be big, one way or the other, so call it a 50% chance there is a period of history where this scheme is applicable.)

The proposal

Let x be my PIN. We use the following scheme to encrypt my drive:

• I generate a random n bit string z, and encrypt my drive with H(z), where H is the complicated function described in the the last section.
• I choose a random map f from possible PINs to n bit keys.
• We can can consider any N bit key f(y) as a measurement on N qubits: measure the ith qubit in the standard basis if f(y)[i] is 0, and in the Hadamard basis if f(y)[i] is 1.
• We prepare the N qubits so that the measurement outcome will be z, if you measure with f(x). That means that if you measure with f(y) for any y != x, you’ll get something that agrees with z in half the bits and is uniformly random on the others.
• To unlock my phone with a proposed PIN y, we measure the N qubits with f(y). We then apply H to the result, and try to use it to decrypt my drive.

The analysis

I claim that in order to access my key, you need to be able to do one of:

• Guess my pin.
• Spend exponentially long to break the symmetric crypto.
• Have a quantum computer which is able to compute H.

The argument is pretty simple:

• Without accessing H on input z, each qubit just looks maximally mixed.
• If you can’t run H on your quantum computer, then we can model it as an oracle that can only be queried classically. The qubits all look maximally mixed until you query this oracle at z.
• But it’s really hard to find z, and hence to query H on z:
  • Without guessing my PIN, you can’t guess any measurement that agrees with f(x) at more than half the positions. (And you can’t make multiple measurements on each qubit.)
  • If you can’t guess any measurement that agrees with f(x) at more than half the positions, then even if I tell you which bits of z you’ve measured correctly, you still need to guess the other half correctly, which would take exponentially long.

It’s not a proof, but it looks pretty solid to me.

Other thoughts

Instead of storing z directly in the qubits, you can use a (classical) error-correcting code, so that you can recover z if some of the qubits break. Obviously this will also reduce your security parameter.

If you can tell when your quantum bits decohere, then you can potentially handle very large number of missing qubits using erasure codes. Obviously you can’t handle >50% undetected errors.

If you want to get 10 guesses instead of 1, then you would need to store 10 copies of this whole setup.

If the quantum bits fail over time, then you could force the user to periodically log in to their phone to “refresh” them.

The security parameter is determined by the symmetric key crypto. I’m not sure how few qubits you could get away with. If H requires 1e10 operations, and an attacker is definitely bounded by 1e35 operations, then you’d need 100 bits for security, which requires 200 qubits (since they can learn the true value of half of them by measuring).