Gottesman and Chuang Quantum Digital Signature

Functionality Description

Digital Signatures (QDS) allow the exchange of classical messages from sender to multiple recipients, with a guarantee that the signature has come from a genuine sender. Additionally, it comes with the properties of (i) transferability i.e. messages with DS can be forwarded from one recipient to another such that DS is verifiable to have come from the original sender, (ii) non-repudiation i.e at any stage after sending the message to one recipient, sender cannot deny having sent the message and corresponding DS, and (iii) unforgeability i.e. a dishonest recipient cannot alter or fake the sender's DS and forward it to other recipients successfully.
Such protocols require parties to store quantum states for comparison at a later stage. For simplicity, most protocols take into account the case of one sender and two recipients (Seller, buyer and verifier) exchanging single-bit classical messages.

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)

Requirements

• Network Stage: Quantum Memory
• Relevant Network Parameters:
• Benchmark values:

Use Case

Online Transactions, Signing Marksheets

Example:

Outline

---

Quantum Digital Signature (QDS) protocols can be separated 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 phase can be divided into the following steps:

• Key Distribution:

Figure

Similarly, Messaging Phase is divided into the following steps:

• Signing:
• Transfer:

Properties

---

• The protocol-
  • involves three parties (Seller, Buyer, Verifier) exchanging one-bit classical messages.
  • Requires quantum one-way function, quantum memory, authenticated quantum and classical channels
  • assumes maximum number of participating parties are honest. In the present case at least two parties are honest.
  • provides information-theoretic security
  • provides security against repudiation, i.e. the probability that seller succeeds in making buyer and seller disagree on the validity of her sent quantum signature decays exponentially with L, as stated by the formula {equation}
  • provides security against forgery, i.e. any recipient (verifier) with high probability rejects any message which was not originally sent by the seller herself. Forging probability is given by the formula, {equation}

Pseudo Code

---

• Notations Used:
  • L: Length of keys used
  • 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 s_a} : Threshold value for signing
  • 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 s_v} : Threshold value for verification
  • $|\psi ^{k}\rangle$: Quantum Public key for message k
  • $\{\beta _{1}^{k},...,\beta _{L}^{k}\}$: Classical Private key for classical one-bit message k
  • $\beta _{l}^{k}$: Classical description of $l^{th}$ qubit in $|\psi ^{k}\rangle$
  • $B^{m}$: Buyer's Eliminated Signature for message m
  • $V^{m}$: Verifier's Eliminated Signature for message m
  • $b_{l}^{k}$: Buyer’s random bit to determine the measurement basis of $l^{th}$ qubit in $|\psi ^{k}\rangle$
  • 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 v^k_l} : Verifier’s random bit to determine the measurement basis of 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 l^{th}} qubit in $|\psi ^{k}\rangle$
  • $m_{b_{l}^{k}}$: measurement outcome of $b_{l}^{k}$

Stage 1 Distribution

• Input L
• Output Seller: $\{\beta _{1}^{0},...,\beta _{L}^{0}\},\{\beta _{1}^{1},...,\beta _{L}^{1}\}$; Buyer: $B^{0},B^{1}$; Verifier: $V^{0},V^{1}$
  • Key Distribution:

1. For k = 0,1
   1. Seller prepares quantum public key $|\psi ^{k}\rangle =\bigotimes _{l=1}^{L}|\beta _{l}^{k}\rangle$, where $\beta _{l}^{k}\in _{R}\{0,1,+,-\}$
   2. She sends Buyer (k,$|\psi ^{k}\rangle$)
   3. She sends Verifier (k,$|\psi ^{k}\rangle$)

• • State Elimination:

1. For k = 0,1
   1. For l = 1,2,...,L
      1. Buyer chooses $b_{l}^{k}\epsilon _{R}{0,1}$
      2. If $b_{l}^{k}=0$, Buyer measures his qubit in X basis $\{|+\rangle ,|-\rangle \}$
      3. If $b_{l}^{k}=0$, Buyer measures his qubit in Z basis $\{|0\rangle ,|1\rangle \}$
      4. return $m_{b_{l}^{k}}$
      5. $B_{l}^{k}=1-m_{b_{l}^{k}}$

• • Verifier repeats steps 2(a)-2(b) with randomly chosen basis $v_{l}^{k}$ to get his eliminated signature elements 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 V^k_l}

• • Symmetrisation

1. 1. For k = 0,1
      1. Buyer chooses I$\subset _{R}\{1,2,...,L\},|I|=[L/2]$
      2. $\forall i\epsilon I$, Buyer sends Verifier 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 (k,i,b^k_i,B^k_i)}
      3. Verifier chooses JFailed 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 \subset_R\{1,2,...,L\}, |J|=[L/2]}
      4. 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 \forall j\epsilon J} , Verifier sends Buyer 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 (k,j,v^k_j,V^k_j)}
      5. $\forall j\epsilon J$ Buyer replaces $B_{l}^{k}=V_{l}^{k}$
      6. $\forall i\epsilon I$ Verifier replaces $V_{l}^{k}=B_{l}^{k}$

Stage 2 Messaging

• Input Seller: Message m, Private Key for m: $\{\beta _{1}^{m},...,\beta _{L}^{m}\}$
• Output Buyer: accept or abort, Verifier: accept or abort
  • Signing: ’mismatch’ is when Buyer finds an eliminated signature element in Seller’s private key

1. Seller sends Buyer (m,$\{\beta _{1}^{m},...,\beta _{L}^{m}\}$)
2. For l = 1,2,..,L
   1. Buyer counts the number of mismatches ($B_{l}^{m}=V_{l}^{m}$) and returns 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 S_b}
3. If 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 S_b < s_aL/2} , Buyer accepts m else he aborts

• • Transfer

1. Buyer sends Verifier (m,$\{\beta _{1}^{m},...,\beta _{L}^{m}\}$)
2. For l = 1,2,....,L
   1. Verifier counts the number of mismatches (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 V^m_l=B^m_l} ) and returns $S_{v}$
3. If $S_{v}<s_{v}L/2$, Verifier accepts m else he aborts

Discussion

• Theoretical Papers

1. GC-QDS (2001) uses quantum one way function f(); Private keys: classical input x, Public keys: quantum output f(x). Requires quantum memory, quantum one way function, authenticated quantum and classical channels, SWAP Test (universal quantum computer). Unconditionally Secure
2. ACJ (2006) discusses coherent states comparison with a QDS scheme outlined in the last section. 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. Unconditionally Secure
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. Requires random number generator, one-way hash function, quantum memory, key distribution. Computationally Secure

• Experimental Papers