Can You Sign A Quantum State?

Spoiler: no, you can’t, unless you also encrypt the quantum state.

In this post we are going to look at recent scientific results about the potential and limitations of cryptography on a quantum computer. We are looking at the possibility of creating quantum digital signatures, that is, cryptographic signatures on quantum states. This is not to be confused with quantum-resistant digital signatures, which is a different topic.

Digital signatures are a crucial component of today’s electronic society. Such a very fundamental cryptographic primitive is found everywhere, from credit cards to mobile communication. A cryptographic signature on a piece of digital information (the message) is a binary certificate, attached to the message, that guarantees that the message was prepared by a specific user, whose identity is bound to a pair of public/private verification and signing keys. Security for a digital signature scheme is given in terms of unforgeability and non-repudiation, which are properties that requires that nobody without the signing key can generate a valid signature for an arbitrary message.

A typical example of a digital signature scheme is the well known RSA cryptosystem. This was initially born as a public-key encryption scheme, but it can also be used as a signature scheme: it has the property that the private decryption key can also be used as a signing key, and the public encryption key can also be used as a verification key.

(Notice that this is a very special property of the RSA cryptosystem: such a strong “functional symmetry”, i.e. the fact that the same encryption trapdoor can also be used as a signature trapdoor, is not found in most other public-cryptosystems. For example, one cannot straightforwardly use ElGamal to generate signatures, and many signature schemes cannot be used for public-key encryption.)

RSA, like many other modern cryptosystems, will be broken when quantum computers arrive. This has led to the recent development of other, more secure, quantum-resistant digital signature schemes, that are supposed to stay secure even in the post-quantum future. However, as we previously explained in another blog post, it is also interesting to look at the following scenario: what will happen when the information we exchange in the network will also be quantum? In other words, what happens if we want to digitally sign a quantum state?

Quantum Signatures

First of all, we have to decide what it means to “digitally sign a quantum state”. Ideally, we want a functionality that mimics as closely as possible the traditional digital signatures we are used to, but where the message to be signed is an arbitrary (possibly entangled) quantum state. In this scenario, user A prepares a quantum state and sends it over the “quantum Internet” to user B, and user B wants to make sure that the state received is actually the one sent by A and not something else. We still want signing and verification keys to be classical, because that’s a useful property, but what about the signature itself?

The intuitive solution would be to require that a quantum signature on a state $\left| \varphi \right\rangle$ is another state $\left| \psi \right\rangle$ such that:

the authenticity of $\left| \psi \right\rangle$ can be verified by using A’s verification key $\mathsf{vk}$ ; and
only by using A’s signing key $\mathsf{sk}$ one can generate a valid signature.

But quantum mechanics is tricky. The idea above cannot work, for the following reason:

if $\left| \psi \right\rangle$ is generated by acting on $\left| \varphi \right\rangle$ directly, it will “consume” $\left| \varphi \right\rangle$ in the process. Given that in quantum mechanics one cannot create a copy of an arbitrary state, this means that there would not be a way to recover the message $\left| \varphi \right\rangle$ , even if the signature itself might be valid;
on the other hand, if $\left| \psi \right\rangle$ is generated without consuming $\left| \varphi \right\rangle$ , then it will not carry any information about $\left| \varphi \right\rangle$ itself. This means that the signature will be completely unrelated to $\left| \varphi \right\rangle$ , and will still work with a different quantum message, therefore invalidating security.

It turns out that the only reasonable way to go forward is to “package” signature and message into a single quantum state $\left| \sigma \right\rangle$ , with the following properties:

if $\left| \sigma \right\rangle$ was generated correctly through $\mathsf{sk}$ , then by using $\mathsf{vk}$ it is possible to both check this correctness and to recover the original $\left| \varphi \right\rangle$ at the same time; and
if $\left| \sigma \right\rangle$ was not generated correctly, then by using $\mathsf{vk}$ it is possible to check this fact (but not necessarily to recover $\left| \varphi \right\rangle$ ).

This model sounds appealing, but how to realize it? It doesn’t look so easy. In fact, consider the “straightforward” idea of signing a message in superposition: let $\mathsf{\left(KGen,Sign,Verify\right)}$ a (classical, but quantum-resistant) digital signature scheme, and let $\left| \varphi \right\rangle = \sum_m \alpha_m \left| m \right\rangle$ our message. We could generate the signed packaged state as:

$\left| \sigma \right\rangle = \sum_m \alpha_m \left| m , \mathsf{Sign}_\mathsf{sk}(m) \right\rangle$

However, by doing some math, it is easy to convince yourself that this system doesn’t work, because it doesn’t usually allow to recover the original $\left| \varphi \right\rangle$ (hint: it introduces entanglement that it is difficult to undo without the signing key $\mathsf{sk}$ ). Moreover, if we modify the scheme in such a way that recovering $\left| \varphi \right\rangle$ becomes easier, then it also becomes easier for an adversary to use $\left| \sigma \right\rangle$ to create a valid forgery for a different $\left| \varphi' \right\rangle$ .

It sounds like the more we strive to recover the message, the less secure the signature schemes becomes because an adversary can “undo” the signature. How is this possible?

Impossibility of Quantum Signatures

It turns out that there is indeed a very fundamental problem in realizing quantum signatures, and to understand what the problem is we have to recall that in quantum computing every transformation that preserves the “quantumness” of a system must be reversible. And this makes the problem of digitally signing and publicly verifying a quantum state impossible.

The intuition is the following: a quantum signature generates a packaged state $\left| \sigma \right\rangle$ by acting on a message $\left| \varphi \right\rangle$ and a secret piece of information ( $\mathsf{sk}$ ). However, given that the verification process must allow, starting from $\left| \sigma \right\rangle$ , to recover $\left| \varphi \right\rangle$ by using only public information ( $\mathsf{vk}$ ), then the same process must allow to recover $\mathsf{sk}$ as well, because of the reversibility of the quantum process!

This intuition is admittedly very vague, and leaves the door open to many loopholes. However, in a recent scientific work, it was proven unambiguously that the intuition is correct! More precisely:

if you define a very weak form of security for quantum digital signatures (in fact, so weak that it would be the very minimal reasonable property), then even that form of security cannot be achieved if you also require that the message $\left| \varphi \right\rangle$ can be recovered;
moreover, even if you do not require that the full message $\left| \varphi \right\rangle$ can be recovered, still no security is possible – unless you only recover classical information about $\left| \varphi \right\rangle$ ;
finally, even if you weaken the definition of quantum signature itself in various ways (by using quantum keys, by using a either-verify-or-recover-but-not-both approach, etc.) you still cannot circumvent the two points above.

To put it differently: only classical digital signatures are possible! This is a very strong and devastating impossibility result: it basically tells us that digital signatures are only possible on classical data, and that there is something, after all, that classical computers can do better than quantum computers!

In fact, this results shows that digital signatures are the first known example of a “simple” cryptographic primitive that can be realized classically but not quantumly.

Quantum Signcryption

So, is all hope lost?

Well, a way to authenticate a quantum state between two parties exists after all: the solution is to use a shared secret key instead of a public/private key pair. This is done in quantum authenticated encryption, but has the disadvantage that a different shared key is necessary for every pair of users. As the number of users in a given system grows, this becomes quickly unmanageable.

However that is an interesting initial observation. A very fundamental result in quantum cryptography tells us something about the problem of encrypting VS authenticating a quantum state through the use of a shared classical secret key between two parties. In 2002, researchers showed that, since in quantum computing every process must be reversible, it is not possible to authenticate a quantum state without also encrypting it. Their result actually only applies to symmetric-key authenticated quantum encryption, but it also sounds quite similar to the issue we have with the impossibility of quantum signatures, that is, the problem that public verifiability implies loss of security. Is there a way we can exploit such observation to circumvent our impossibility result?

It turns out that, yes, we can!

Remember that the problem with quantum signatures is that they are not secure because anybody can verify them. What if we make sure that only the recipient of the message $\left| \varphi \right\rangle$ can verify the signature, and nobody else? In order to do that we have clearly to encrypt the message for the recipient. However, we do not have necessarily to resort to a shared secret key between parties, because in fact quantum public-key encryption exists!

The resulting system, which consists in signing and encrypting a message at the same time, is called “signcryption”. Classically, it is just a layered combination of signature and encryption, and it is only considered an interesting joint operation when it provides a performance boost over separately signing and encrypting. However, quantumly, it is far more interesting: it is the only way of digitally signing a message with a public/private keypair!

A practical way to realize quantum signcryption is as follows:

start with a quantum message $\left| \varphi \right\rangle$
generate a classical, random message $m$
generate a classical signature $\sigma$ for $m$ , using your private signing key $\mathsf{sk}$ and a quantum-secure classical digital signature scheme
encode $(m,\sigma)$ into a quantum state $\left| m | \sigma \right\rangle$
use a public-key quantum encryption scheme to encrypt the joint state $\left| \varphi \right\rangle \otimes \left| m | \sigma \right\rangle$ using the recipient’s public encryption key.

Upon receiving the signcrypted quantum state, the recipient will first decrypt it using his own private decryption key, and then he will verify the signature using our public verification key, and at the same time will recover the original $\left| \varphi \right\rangle$ .

You have probably noticed a potential vulnerability: a malicious receiver could unwrap $(m,\sigma)$ from the signcrypted state and use it to generate arbitrarily many forged signcrypted messages on behalf of the sender. This doesn’t sound very secure. Is there a way to avoid it? Unfortunately not: if it were possible, then we could obtain quantum digital signatures (by ignoring the encryption step) and we already know that this impossible. Therefore, quantum signcryption can be used to authenticate messages between users, but still has a limitation: it cannot provide non-repudiation.

Conclusion

The intersection between cryptography and quantum computing is terribly fascinating, and many things we give for granted in the classical world have to be reconsidered entirely. We know that, by exploiting the power of quantum, we can perform cryptographic tasks that are impossible with classical computers (information-theoretically secure key-exchange, quantum money, etc). But it turns out that the opposite is also true: there are certain tasks that are possible on classical data but not on quantum data. Digital signatures are certainly a prominent example. It is very important to know this limitation because it tells us important guidelines to keep in mind when designing future quantum networks. For many applications, quantum signcryption is going to be secure enough and will replace digital signatures. But non-repudiation cannot be achieved anyway.

Quantum Signatures

Impossibility of Quantum Signatures

Quantum Signcryption

Conclusion

Share:

Related

Leave a Reply