Quantum Protocol Zoo

Editing Quantum Fingerprinting

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.

Latest revision Your text
Line 1: Line 1:
This [https://arxiv.org/abs/quant-ph/0102001 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.
Quantum fingerprinting allows two parties (two quantum clients) to collaboratively compute the value of a function using both of their inputs while maintaining the privacy of their own input. The protocol does not permit the two parties to interact directly with each other, hence they send their respective inputs to a trusted third party (quantum server) who computes the correct value of the function corresponding to both inputs while minimizing the amount of information sent by the two parties.  
 
</br></br>
'''Tags:''' [[Fingerprinting]]
Minimization of information is done by fingerprinting, which is a technique that associates a string to an exponentially smaller string (fingerprints) such that any two strings can by distinguished solely based on their fingerprints.
</br></br>
'''Tags:''' Fingerprinting


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


==Outline==
==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.
The two quantum clients want to compute a function using the input of both parties. In this protocol, we focus on a specific function, which is the equality function. This function provides boolean output 1 if the input of both the parties is the same, otherwise, the output is 0.
</br>
 
Preparation stage involves two parties (two quantum clients) preparing the fingerprints of their individual inputs and sending their quantum states to the server (trusted third party). The two clients do not possess any shared quantum key.  
</br>
 
Next stage involves the server performing several operations on the fingerprints to check their equality. These operations are repeated several times on the same fingerprints to reduce the error probability.
</br>
* '''Client's preparation''': The client prepares the fingerprint of initial input sized <math>n</math>-bits. This fingerprint has a length  of <math>\log_{}n</math> bits. The client now sends this fingerprint to the server through a quantum channel. Both the clients do this process simultaneously.
 
* '''Server's preparation''': The server receives the two fingerprints from both the clients and prepares the operations to distinguish them. The server independently repeats the computation process with the fingerprints several times to reduce the error probability in detecting whether the equality of the two states.


* '''Client's preparation''':  
* '''Measurement''': The server measures the final states and announces the result.
** The client prepares the fingerprint of initial input which is sized <math>n</math>-bits. This fingerprint has a length of <math>O(\log{}n)</math> bits.
** This fingerprint is prepared using particular error correcting codes, which converts the <math>n</math>-bit input to <math>m</math>-bits, where <math>m</math> is greater than <math>n</math>, and the two outputs of any two distinct inputs can be equal at atmost <math>\delta m</math> positions, where <math>\delta < 0</math>. The fingerprint has the length of <math>log{}m+1</math> bits.
** Here for error correcting code, [https://ieeexplore.ieee.org/document/1054893 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 [[Glossary#Quantum SWAP test|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.
If the initial input 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==
==Requirements==
* Authenticated Quantum channel capable of sending a pair of qubits.
* Authenticated Quantum channel capable of sending a pair of qubits.
* Quantum memory for server to store the fingerprints.
* Measurement devices for the server.
* Measurement devices for the server.
* A one-time quantum channel from both clients to the server.
==Knowledge Graph==
{{graph}}


==Notation==
==Notation==
* <math>x</math>, <math>y</math>: inputs of both the clients
* <math>|h_x\rangle</math>, Quantum fingerprint for <math>n</math>-bit input <math>x</math>.
* <math>n</math>: length of inputs
* <math>E(x)</math>, Fingerprint function associated with input <math>{x\in \{0, 1\}^n}</math> which maps <math>n</math>-bit input to <math>m</math>-bit fingerprint.
* <math>m</math>: Length of output of error correcting codes, using x and y as input.
* <math>\delta</math>, Fixed constant, such that <math>\delta<0</math>.
* <math>E(x)</math>: Error correcting code associated with input <math>{x\in \{0, 1\}^n}</math>, where <math>E: \{0, 1\}^n \xrightarrow{}{} \{0, 1\}^m </math>.
* <math>|h_x\rangle</math>: <math>(log{}m+1)</math> qubit state quantum fingerprint for <math>x</math>.
<math>|h_x\rangle = \frac{1}{\sqrt{m}}\sum_{i=1}^{m} |i\rangle|E_i(x)\rangle</math>
* <math>c</math>: Parameter for error correcting code. <math>m=cn, c>1</math>
* <math>\delta</math>: Parameter for error correcting code. <math>\delta<1</math>.
* <math>\epsilon</math>: Error probability
* <math>k</math>: Number of times a fingerprint is repeated, <math>k \in O(log{}{\frac{1}{\epsilon}})</math>


==Properties==
==Properties==
* The computational complexity of this protocol is <math>\mathcal{O}(\log{}n)</math>.
* The computational complexity of this protocol is <math>\mathcal{O}(\log{}n)</math>.
* The two quantum clients have no shared key in this protocol.
* Given an <math>n</math>-bit input, the protocol requires a quantum fingerprint of minimum <math>\log{}n</math> bits which contains quantum information.
* Given an <math>n</math>-bit input, the protocol requires a quantum fingerprint of minimum <math>\log{}n</math> 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 <math>{E(x)}</math> and <math>{E(y)}</math> is at least <math>{(1+\delta)m}</math>.
* The quantum fingerprint is defined as the state <math>|h_x\rangle</math>, where <math>{E(x)}</math> is the fingerprint of the input <math>x</math>. <math>{E_i(x)}</math> is the <math>{i^{th}}</math> bit of <math>{E(x)}</math>. </br>
* For Justesen codes, <math>\delta < 9/10 + 1/(15c)</math> for any chosen <math>c>2</math>
<math>|h_x\rangle = \frac{1}{\sqrt{m}}\sum_{n=1}^{m} |i\rangle|E_i(x)\rangle</math>
* The hamming distance i.e. the number of positions between two strings of same length, at which the corresponding symbols are different, of <math>{E(x)}</math> and <math>{E(y)}</math> is at least <math>{(1+\delta)m}</math>.
* Any two fingerprints, <math>|h_x\rangle</math> and <math>|h_y\rangle</math> have an inner product of at most <math>{\delta}</math>.
* Any two fingerprints, <math>|h_x\rangle</math> and <math>|h_y\rangle</math> have an inner product of at most <math>{\delta}</math>.
* The one sided error probability of the SWAP test is <math>(\frac{1+\delta}{2})</math>.
* The one sided error probability is at least <math>(\frac{1+\delta}{2})^k</math> if the server computation is repeated <math>k</math> times.
* Quantum memory would be required to store the fingerprints if the server operations are performed <math>k</math> times.
* This protocol requires no quantum memory for the Client


==Protocol Description==
==Pseudocode==
'''Stage 1''': Client's preparation</br>
'''Input''': <math>{x \in \{0, 1\}^n}</math> to First Party and <math>{y \in \{0, 1\}^n}</math> to Second Party. </br>
'''Input''': <math>{x \in \{0, 1\}^n}, {y \in \{0, 1\}^n}</math> for first client and second client respectively. </br>
'''Output''': One bit by server satisfying the equality function with some error probability. </br>
'''Output''': <math>|h_x\rangle</math>, <math>|h_y\rangle</math> sent to server
'''Stage 1''': Client's preparation
* First client prepares <math>|h_x\rangle</math> from <math>x</math>, <math>|h_x\rangle = \frac{1}{\sqrt{m}}\sum_{i=1}^{m} |i\rangle|E_i(x)\rangle</math>
* First Party prepares the fingerprint <math>|h_x\rangle</math> from input <math>x</math>.
* Second client prepares <math>|h_y\rangle</math> from <math>y</math>, <math>|h_y\rangle = \frac{1}{\sqrt{m}}\sum_{i=1}^{m} |i\rangle|E_i(y)\rangle</math>
* Second Party prepares the fingerprint <math>|h_y\rangle</math> from input <math>y</math>.
* Both clients send <math>|h_x\rangle</math>, <math>|h_y\rangle</math> to server
* Both parties transmit their fingerprints to the server.


 
'''Stage 2''': Server's preparation
'''Stage 2''': Server's test
* Server prepares an ancilla qubit <math>|0\rangle</math> for final measurement purpose, and thus starts with the state <math>|0\rangle|h_x\rangle|h_y\rangle</math>.
'''Input''': <math>|h_x\rangle</math>, <math>|h_y\rangle</math> </br>
* Server creates an entangled state by applying the gate <math>G</math>.
'''Output''':  SWAP test result
<math>G = {(H\otimes I)(c-SWAP)(H\otimes I)}</math>
* Server prepares an ancilla qubit <math>|0\rangle</math> for SWAP test and starts with state <math>|0\rangle|h_x\rangle|h_y\rangle</math>
* The server measures the first qubit and transmits the output to both the parties.
* Server applies gate <math>G = {(H\otimes I)(c-SWAP)(H\otimes I)}</math>, resulting in final state <math>\frac{1}{2}|0\rangle(|h_x\rangle|h_y\rangle + |h_y\rangle|h_x\rangle) + \frac{1}{2}|1\rangle(|h_x\rangle|h_y\rangle - |h_y\rangle|h_x\rangle)</math>
* The server measures the first qubit and transmits the result to both the clients.


==Further Information==
==Further Information==
* To reduce the error probability to any <math>\epsilon</math>, the fingerprint of <math>x</math> should be set to <math>|h_x\rangle^{\otimes k}</math>, for a suitable <math>k \in O(log{}{\frac{1}{\epsilon}})</math>
==Related Papers==
==Related Papers==


<div style='text-align: right;'>''*contributed by Rhea Parekh''</div>
<div style='text-align: right;'>''*contributed by Rhea Parekh''</div>
Please note that all contributions to Quantum Protocol Zoo may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see Quantum Protocol Zoo:Copyrights for details). Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel Editing help (opens in new window)

Template used on this page:

Retrieved from "https://wiki.veriqloud.fr/index.php?title=Quantum_Fingerprinting"