Quantum Coin

This example protocol implements Quantum Money which is a unique object generated by a Trusted Third Party (TTP). It is then circulated among untrusted clients (Transferability). Each client should be able to prove the authenticity of his owned quantum money to a verifier. On the other hand, an adversary must fail in counterfeiting the quantum money with overwhelmingly high probability (Unforgeability).

Tags: Multiparty, Quantum Enhanced Classical functionality, prepare (bank) and measure (client)

Outline

In this scheme, a Trusted Third Party (TTP) and a coin holder run the following procedure for generating and verifying a quantum coin:

• Quantum coin Generation - The TTP chooses k random 4-bit strings, keeps them in secret and produce k quantum states. A newly issued quantum coin consists of a piece of paper glued to k quantum registers that hold k quantum states. The piece of paper contains a unique identification tag and k initially unmarked positions, where the i-th position has to be marked in k-bit classical register P when the corresponding quantum state is used in the verification protocol.
• Quantum coin Verification - To verify a quantum coin through classical communication with the TTP, its holder sends the identification number of the quantum coin to the TTP. Then, the TTP and the coin holder exchange some classical information for choosing some quantum registers. The coin holder measures the chosen registers and sends their corresponding classical information to the TTP. The TTP verifies the authenticity of the coin by the secret information he possesses.

Notations

• 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 HMP_4} -states: $|\alpha (x)\rangle ={\dfrac {1}{2}}\sum _{1\leq i\leq 4}(-1)^{x_{i}}|i\rangle$, $x\in \{0,1\}$

Requirements

• Network stage: quantum memory network.

Properties

• General Features:
  • No need to quantum communication for quantum coin verification.
  • The classical communication channel used for verification can be unencrypted.
  • The database of the bank is static, and therefore many de-centralized “verification branches” can exist that do not have to communicate with one another.
  • The number of verifications that a quantum coin can go through is limited.

• Security Claims:
  • The coins are exponentially hard to counterfeit.
  • Secure against an adversary who uses adaptive “attempted verifications” in order to collect information about a coin.

Pseudocode

Stage 1: Quantum coin generation
Input: A secret record consists of $k$ entries $x_{1},...,x_{k}$,$x_{i}\in \{0,1\}^{4}$
Output: A “fresh” quantum coin
The Trusted Third Party (TTP) chooses $x_{1},...,x_{k}\in \{{0,1}\}^{4}$ at random, keeps them in secret and produces quantum states $|\alpha (x_{1})\rangle ,...,|\alpha (x_{k})\rangle$. A “fresh” quantum coin corresponding to this record consists 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 k} quantum registers consisting of 2 qubits each, where the 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 i} -th register contains 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 |\alpha(x_i)\rangle} ;
• a 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} -bit classical register 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 P} , that is initially set to 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 0^k} ;
• a unique identification number.

Stage 2: Quantum coin verification
Input: the identification number of the quantum coin
Output: Accept or Reject

This stage is run as follows:

• The holder sends the identification number of the quantum coin to the TTP.
• The TTP chooses uniformly at random a set 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_{bn}\subset[k]} of size 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 t} , and sends it to the coin holder.
• The holder consults with P and chooses uniformly at random a set $L_{hl}\subset L_{bn}$ consisting 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 2t/3} yet unmarked positions. He sends 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_{hl}} to the bank and marks in 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 P} all the elements 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_{hl}} as used.
• The TTP chooses at random 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 2t/3} values 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 m_i \in\{{0, 1}\}} , one for each 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 i \in L_{hl}} , and sends them to the coin holder.
• The holder measures the quantum registers corresponding to the elements 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_{hl}} in order to produce 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 2t/3} pairs $(a_{i},b_{i})$, such that 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 (x_i,m_i, a_i, b_i)\in HMP_4} for all 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 i \in L_{hl}} . He sends the list 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 (a_i, b_i)} s to the TTP.
• The TTP checks whether 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 (x_i,m_i, a_i, b_i)\in HMP_4} for all 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 i \in L_{hl}} , in which case it confirms validity of the quantum coin. Otherwise, the coin is declared to be a counterfeit.

*contributed by Mashid Delavar

Further Information

Gavinsky, Dmitry. "Quantum money with classical verification." 2012 IEEE 27th Conference on Computational Complexity. IEEE, 2012, Available at: http://users.math.cas.cz/~gavinsky/papers/QuMoClaV.pdf