Write, autoreview, editor, reviewer
3,129
edits
Quantum Fingerprinting: Difference between revisions
Jump to navigation
Jump to search
no edit summary
No edit summary |
|||
| Line 1: | Line 1: | ||
This [https://arxiv.org/abs/quant-ph/0102001 example protocol] allows | 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. | ||
'''Tags:''' [[Fingerprinting]] | '''Tags:''' [[Fingerprinting]] | ||
| Line 5: | Line 5: | ||
==Assumptions== | ==Assumptions== | ||
* The two quantum clients have no shared key in this protocol. | * The two quantum clients have no shared key in this protocol. | ||
* The server is trusted | * The server is trusted. | ||
* The fingerprints can consist of quantum information. | * 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 several times on the received fingerprints to reduce the error probability. | 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''': | * '''Client's preparation''': | ||
** The client prepares the fingerprint of initial input which is sized <math>n</math>-bits. This fingerprint has a length of <math>\ | ** 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 | ** 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. | ** The client now sends this fingerprint to the server through a quantum channel. Both the clients do this process simultaneously. | ||
| Line 21: | Line 21: | ||
==Hardware Requirements== | ==Hardware Requirements== | ||
* Authenticated Quantum channel capable of sending a pair of qubits. | * Authenticated Quantum channel capable of sending a pair of qubits. | ||
* Measurement devices for the server. | * Measurement devices for the server. | ||
* A one-time quantum channel from both clients to the server. | * A one-time quantum channel from both clients to the server. | ||
==Notation== | ==Notation== | ||
* <math>|h_x\rangle</math> | * <math>x</math>, <math>y</math>: inputs of both the clients | ||
* <math>n</math>: length of inputs | |||
* <math>m</math>: Length of output of error correcting codes, using x and y as input. | |||
* <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>|h_x\rangle = \frac{1}{\sqrt{m}}\sum_{i=1}^{m} |i\rangle|E_i(x)\rangle</math> | ||
* <math> | * <math>c</math>: Parameter for error correcting code. <math>m=cn, c>1</math> | ||
* <math>\delta</math> | * <math>\delta</math>: Parameter for error correcting code. <math>\delta<1</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>. | ||
* 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 | * 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>. | ||
* For Justesen codes, <math>\delta < 9/10 + 1/(15c)</math> for any chosen <math>c>2</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 is at least <math>(\frac{1+\delta}{2})^k</math> if the server computation is repeated <math>k</math> times. | * 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. | ||
==Pseudocode== | ==Pseudocode== | ||
'''Input''': <math>{x \in \{0, 1\}^n} | '''Input''': <math>{x \in \{0, 1\}^n}, {y \in \{0, 1\}^n}</math> for first client and second client respectively. </br> | ||
'''Output''': | '''Output''': <math>|h_x\rangle</math>, <math>|h_y\rangle</math> sent to server </br> | ||
'''Stage 1''': Client's preparation | '''Stage 1''': Client's preparation | ||
* First | * First client prepares fingerprint <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>. | ||
* Second | * Second client prepares fingerprint <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>. | ||
* Both | * Both clients send <math>|h_x\rangle</math>, <math>|h_y\rangle</math> to the server. | ||
'''Stage 2''': Server's | '''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>. | * 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>. | ||
* Server creates an entangled state by applying the gate <math>G = {(H\otimes I)(c-SWAP)(H\otimes I)}</math>. | * Server creates an entangled state by applying the gate <math>G = {(H\otimes I)(c-SWAP)(H\otimes I)}</math>. | ||