Quantum digital signature
Like a handwritten signature, a digital signature is used to protect a document, such as a digital contract, against forgery by another party or by one of the participating parties.
As e-commerce has become more important in society, the need to certify the origin of exchanged information has arisen.
Modern digital signatures enhance security based on the difficulty of solving a mathematical problem, such as finding the factors of large numbers (as used in the RSA algorithm).
Unfortunately, the task of solving these problems becomes feasible when a quantum computer is available (see Shor's algorithm).
To allow this, the public key is made broadly available to all potential recipients.
To make sure only the legal author of the message can validly sign the message, the public key is created from a random, private sign key, using a one-way function.
A classic example is the multiplication of two very large primes: The multiplication is easy, but factoring the product without knowing the primes is normally considered infeasible.
In general we can divide quantum digital signature schemes into two groups: In both cases f is a one-way quantum function that has the same properties as a classical one-way function.
That is, the result is easy to compute, but, in contrast to the classical scheme, the function is impossible to invert, even if one uses powerful quantum cheating strategies.
In detail [1][2] A classical one-way function as said above is based on a classical infeasible mathematical task, whereas a quantum one-way function exploits the uncertainty principle which makes it impossible even for a quantum computer to compute the inverse.
This is done by providing a quantum output state, with whom one cannot learn enough about the input string to reproduce it.
In case of the first group of schemes this is shown by Holevo's theorem, which says, that from a given n-qubit quantum state one cannot extract more than n classical bits of information.
[3] One possibility to ensure that the scheme uses less qubits for a bit string of a certain length is by using nearly orthogonal states That gives us the possibility to induce a basis with more than two states.
becomes very large, which makes it impossible for a dishonest person to guess the sign key.
This becomes more difficult in the quantum case, because copying a quantum state is forbidden by the no cloning theorem, as long as the state itself is unknown.
[4] So public keys can only be created and distributed by a person who knows the exact quantum state he wants to create, thus who knows the sign key (This can be the sender or in more general a trustful institution).
has to be big) To make sure that every recipient gets identical results when testing the authenticity of a message, public keys distributed have to be the same.
To test, if two public quantum states are the same one has to compare the following This is done with the following quantum circuit which uses one Fredkin gate F, one Hadamard gate H and an ancilla qubit a.
[1] The calculation of the swap test in more detail: The overall state After the Fredkin gate is applied
Hash algorithms won't be considered, so Alice has to sign every single bit of her message.
Alice chooses M pairs of private keys
She can make as many copies as she needs, but has to take care, not to endanger the security
Her level of security limits the number of identical public keys she can create If Remember: In this example Alice picks only one bit b and signs it.
After he has done so he makes use of the swap test to compare the calculated states with the received public keys.
Since the swap test has some probability to give the wrong answer he has to do it for all the M keys and counts how many incorrect keys he gets r. It is obvious, that M is some kind of a security parameter.
It is more unlikely to validate a bit wrong for bigger M. One problem which arises especially for small M is, that the number of incorrect keys different recipients measure differ with probability.
Because the number of errors increase proportional with M, the thresholds are defined like [1] If we assume perfect channels without noise, so the bit can't be changed due to the transfer, then the threshold
can be set to zero, because the swap test passes always, when the compared states are the same Message authentication codes (MACs) mainly aim at data origin authentication, but they can also provide non-repudiation in certain realistic scenarios when a trusted third party is involved.
In principle, the same idea can be exploited in the framework of quantum MACs.
However, a broad class of quantum MACs does not seem to offer any advantage over their classical counterparts.
