Quantum Fingerprinting

This example protocol allows two quantum clients to distinguish between their quantum inputs while maintaining the privacy of their own input just by comparing the fingerprints of their inputs. 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). This server performs a test to distinguish between two unknown quantum fingerprints with a 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 test 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 $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 O(\log{}n)} bits.
  • This fingerprint is prepared using particular error correcting codes, which converts the $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 $m$ is greater than $n$, and the two outputs of any two distinct inputs can be equal at atmost $\delta m$ positions, 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 \delta < 0} . The fingerprint has the 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{}m+1} bits.
  • Here for error correcting code, 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 quantum 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.

Hardware Requirements

• Authenticated Quantum channel capable of sending a pair of qubits.
• 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 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 y} : inputs of both the clients
• 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} : length of inputs
• 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} : Length of output of error correcting codes, using x and y as 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 E(x)} : Error correcting code 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}} , where $E:\{0,1\}^{n}{\xrightarrow {}}{}\{0,1\}^{m}$.
• 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} : 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)} qubit state 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 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 c} : Parameter for error correcting code. 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=cn, c>1}
• 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} : Parameter for error correcting code. 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<1} .

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 $n$-bit input, the protocol requires a quantum fingerprint of minimum 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 which contains quantum information.
• 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 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 {(1+\delta)m}} .
• For Justesen codes, 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 < 9/10 + 1/(15c)} for any chosen 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>2}
• Any two fingerprints, 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} 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 ${\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.

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}, {y \in \{0, 1\}^n}} for first client and second client respectively.
Output: 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} , 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} sent to server
Stage 1: Client's preparation

• First client prepares 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 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} .
• Second client prepares 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_y\rangle} from $y$, 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 = \frac{1}{\sqrt{m}}\sum_{i=1}^{m} |i\rangle|E_i(y)\rangle} .
• Both clients send 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} , 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} to the server.

Stage 2: Server's test

• 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