Quantum Fingerprinting

This example protocol allows two parties (two quantum clients) to distinguish their quantum inputs while maintaining the privacy of their own input by comparing their fingerprints alone. The protocol does not permit the two parties to interact directly with each other, hence they send the fingerprints of their respective inputs to a trusted third party (quantum server), where the third party tests that distinguishes two unknown quantum fingerprints with high probability. The quantum fingerprints are exponentially shorter than the original inputs.

Tags: Fingerprinting

Assumptions

• The two quantum clients have no shared key in this protocol.
• The server is trusted
• The fingerprints can consist of quantum information.

Outline

Here, two quantum clients want to check if their quantum inputs are distinct while also keeping their inputs secret. They prepare quantum fingerprints of their individual inputs and send these states to the server. Next stage involves the server performing a SWAP test on the fingerprints to check their equality. The server repeats this several times on the received fingerprints to reduce the error probability.

• Client's preparation:
  • The client prepares the fingerprint of initial input which is sized 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 n} -bits. This fingerprint has a length 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 \log_{}n} bits.
  • This fingerprint is prepared using particular error correcting codes, which converts 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 n} -bit input 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 m} -bits, where 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} is greater than $n$, and the two outputs of any two distinct inputs can be equal at atmost 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 \delta m} positions, where $\delta <0$. The fingerprint has the length to be 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 log_{} m+1}
  • Hence for this purpose Justesen codes are used.
  • The client now sends this fingerprint to the server through a quantum channel. Both the clients do this process simultaneously.

• Server's test: The server receives the two fingerprints from both the clients and performs the SWAP test on these states to check if the states are distinguishable. The server independently repeats this SWAP test on fingerprints several times to reduce the error probability in detecting if the two states are different.

If the initial inputs of the two parties are equal, this would be inferred from the corresponding fingerprints with no error probability and the outcome of the protocol would be correct. However, if the two fingerprints are of different inputs, there exists a non-zero probability that the outcome of the protocol is incorrect. Therefore, there exists a one sided error in the measurement. This one sided error is reduced by repeating the server operations several times with the same fingerprints.

Hardware Requirements

• Authenticated Quantum channel capable of sending a pair of qubits.
• Quantum memory for the server to store the fingerprints.
• Measurement devices for the server.
• A one-time quantum channel from both clients to the server.

Notation

• 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 |h_x\rangle} , Quantum fingerprint for 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 n} -bit input 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} .

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 |h_x\rangle = \frac{1}{\sqrt{m}}\sum_{i=1}^{m} |i\rangle|E_i(x)\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 E(x)} , Fingerprint function associated with input 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\in \{0, 1\}^n}} which maps 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 n} -bit input 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 m} -bit fingerprint.
• 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 \delta} , Fixed constant, 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 \delta<0} .

Properties

• The computational complexity of this protocol is 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 \mathcal{O}(\log{}n)} .
• Given an 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 n} -bit input, the protocol requires a quantum fingerprint of minimum $\log {}n$ bits which contains quantum information.
• The quantum fingerprint is defined as the state 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 |h_x\rangle} , where 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 {E(x)}} is the fingerprint of the input 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} . 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 {E_i(x)}} is 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}}} bit 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 {E(x)}} .
  
• The hamming distance i.e. the number of positions between two strings of same length, at which the corresponding symbols are different, 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 {E(x)}} and 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 {E(y)}} is at least ${(1+\delta )m}$.
• Any two fingerprints, $|h_{x}\rangle$ and 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 |h_y\rangle} have an inner product of at most 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 {\delta}} .
• The one sided error probability is at least 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 (\frac{1+\delta}{2})^k} if the server computation is repeated 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} times.
• Quantum memory would be required to store the fingerprints if the server operations are performed 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} times.
• This protocol requires no quantum memory for the Client

Pseudocode

Input: 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 \in \{0, 1\}^n}} to First Party and 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 {y \in \{0, 1\}^n}} to Second Party.
Output: One bit by server satisfying the equality function with some error probability.
Stage 1: Client's preparation

• First Party prepares the fingerprint 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 |h_x\rangle} from input 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} .
• Second Party prepares the fingerprint $|h_{y}\rangle$ from input 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 y} .
• Both parties transmit their fingerprints to the server.

Stage 2: Server's preparation

• Server prepares an ancilla qubit 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\rangle} for final measurement purpose, and thus starts with the state 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\rangle|h_x\rangle|h_y\rangle} .
• Server creates an entangled state by applying the gate 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 = {(H\otimes I)(c-SWAP)(H\otimes I)}} .
• The server measures the first qubit and transmits the output to both the parties.

Related Papers

*contributed by Rhea Parekh