Gottesman and Chuang Quantum Digital Signature

The example protocol achieves the functionality of (Quantum) Digital Signatures (QDS) allowing the exchange of classical messages from sender to multiple recipients, with a guarantee that the signature has come from a genuine sender, using quantum memory. It comes with all the Properties of QDS. Such protocols require parties to store quantum states for comparison at a later stage.

Tags: Multi Party (three), Quantum Enhanced Classical Functionality, Specific Task, Quantum Digital Signature, Prepare and Measure Quantum Digital Signature, Measurement Device Independent Quantum Digital Signature (MDI-QDS)

Assumptions

• Perfect devices and channels have been assumed
• It has been assumed that all recipients have received correct and identical copies of Sender's public key (explained later)
• All participants know, the map which takes private keys to public keys, threshold value of acceptance (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_1} ) and threshold value for rejection ($c_{2}$)

Outline

Gottesman and Chuang signature scheme is based on quantum one way functions, which take classical bit string as input and give quantum states as output. Quantum Digital Signature (QDS) protocols can be divided into two stages: the distribution stage, where quantum signals (public keys) are sent to all recipients, and the messaging stage, where classical messages are signed, sent and verified. Here, we take the case of three parties, one sender (referred to as seller) and two receivers (buyer and verifier) sharing a one bit message.

• Distribution: For each message bit (say 0 and 1) sender selects some (say M) classical bit strings. These are chosen to be her private keys for that message bit. Using this private key as input, Sender generates output of the quantum one-way function/map, which she calls her public key and as assumed above, distributes them to each recipient, for each message bit. In the end of this step, each recipient has 2M public keys, M for message bit 0 and M for message bit 1.
  • Quantum One Way Functions:
  • Key Distribution: The author suggests a few methods for key distribution. One of them is the assumption of a trusted third party who receives public keys from Sender, checks all the keys using SWAP Test and then if test is passed by each key sent, the trusted party distributes it to the recipients. A second method eliminates the requirement of a trusted third party and instead requires Sender to send two copies of each public key to each recipient, such that, in the end each recipient has 4M keys (2M public keys for each message bit). Both Buyer and Verifier perform Swap test on their supposedly identical copies of public keys. Then, if passed, Buyer sends one copy of his public key to the Verifier, who then performs the SWAP test between the received copy and his copy of public key.
• Messaging: Sender sends her message bit with the associated private keys to the Buyer. Buyer performs the map on the private key (quantum one way function takes the sent private key as input) and then compares the output thus generated with the public key received in the distribution stage. If the number of unmatched bits are below rejection threshold, the message is declared valid, else invalid. If the number of unmatched bits is below acceptance threshold, it is declared transferable, else not transferable.

A generalized scheme for more than three parties is given in the article. Also, for multi-bit messages, a scheme using error correcting codes has been suggested in brief.

Properties

• Sending m bits message uses O(m) quantum bits for each recipient.
• The public keys can be used only once.
• Only limited (T) distribution of public keys should be allowed, such that $T<L/n$, where quantum public key is an 'n' qubit state and L is the length of classical bit string.
• Unlike some classical information-theoretic (unconditional security) schemes which require secure anonymous broadcast channel or noisy channel, which are hard to achieve resources, the quantum scheme provides information-theoretic security by only demanding plausible quantum channels and modest interaction between parties involved.
• The scheme is secure against forgery if $(1-\delta ^{2})(M-G)>c_{2}M$, where $\delta$ depends on public keys and hence, on quantum one way functions; M is the number of private keys chosen for each message bit; Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G=2^{-(L-Tn)}2M} , and c_2 is the threshold for rejection.
• The Sender can successfully repudiate by probability, $p_{cheat}\sim O(d^{-M})$, for some $d>1$.

Requirements

• Network Stage:Quantum Memory
• Required parameters: Size of public key (n), private key (L), signed message (1, in above case)
• Scalability:
  • Size of public key increases as logarithm of number of recipients.
  • Size of private key, $L\geq T$ where T must be linear or quadratic in the number of recipients.
  • Size of signed message scales linearly with L.
• Benchmark values: No experimental implementation using qubits. See Experimental Papers (1) for implementation using coherent states.

Further Information

This protocol was the first ever scheme designed for Quantum Digital Signatures. Due to unavailability of quantum memory at the current stage, this scheme has not seen enough experimental implementations, yet variations of the same without the need of quantum memory has some progress such as Prepare and Measure Quantum Digital Signature, Measurement Device Independent Quantum Digital Signature (MDI-QDS), etc.. Following is the list of a few more protocols with similar requirement (quantum memory) but small variations. Theoretical Papers

1. GC-QDS (2001) uses quantum one way function f(); Private keys: classical input x, Public keys: quantum output f(x).
   1. Requires quantum memory, quantum one way function, authenticated quantum and classical channels, SWAP Test (universal quantum computer).
   2. Security: Information-theoretic
2. ACJ (2006) discusses coherent states comparison with a QDS scheme outlined in the last section.
   1. Protocol uses the same protocol as (2) but replaces qubits with coherent states, thus replacing SWAP-Test with Coherent State Comparison. Additionally, it also requires quantum memory, authenticated quantum and classical channels, multiports.
   2. Security: Information-theoretic
3. SWZY (2017) Discusses an attack and suggests corrections on existing QDS scheme using single qubit rotations. Protocol uses rotation, qubits, one-way hash function; Private keys: angle of rotation, Public keys: string of rotated quantum states.
   1. Requires random number generator, one-way hash function, quantum memory, key distribution.
   2. Security: Computational

Experimental Papers

1. CCDAJB (2012) uses phase encoded coherent states, coherent state comparison
   1. Loss from multiport=7.5 dB, Length of the key= $10^{6}$

*contributed by Shraddha Singh