Latest revision |
Your text |
Line 11: |
Line 11: |
| * The device used is computationally bounded - it cannot solve the Learning with Errors (LWE) problem during the execution of the protocol | | * The device used is computationally bounded - it cannot solve the Learning with Errors (LWE) problem during the execution of the protocol |
| * The device behaves in an IID manner - it behaves independently and identically during each round of the protocol | | * The device behaves in an IID manner - it behaves independently and identically during each round of the protocol |
|
| |
|
| |
| ==Requirements==
| |
| * '''Network Stage: ''' [[:Category:Entanglement Distribution Network stage| Entanglement Distribution]]
| |
| * Classical communication between the parties
| |
| * Extended noisy trapdoor claw-free (ENTCF) function family
| |
|
| |
|
| ==Outline== | | ==Outline== |
| <!-- A non-mathematical detailed outline which provides a rough idea of the concerned protocol --> | | <!-- A non-mathematical detailed outline which provides a rough idea of the concerned protocol --> |
| * The protocol consists of multiple rounds, which are randomly chosen for testing or string generation
| |
| * The testing rounds are carried out to ensure that the devices used are following the expected behaviour. The self-testing protocol used is a modification of the one used in [[Device-Independent Quantum Key Distribution | DIQKD]]. This modification is necessary as, unlike the DIQKD scenario, the parties involved in OT may not trust each other to cooperate. The self-testing protocol uses the computational assumptions associated with ''Extended noisy trapdoor claw-free'' (ENTCF) function families to certify that the device has created the desired quantum states. If the fraction of failed testing rounds exceeds a certain limit, the protocol is aborted.
| |
| * At the end of the protocol, the honest sender outputs two randomly generated strings of equal length, and the honest receiver outputs their chosen string out of the two.
| |
|
| |
|
| ==Notation== | | ==Notation== |
| <!-- Connects the non-mathematical outline with further sections. --> | | <!-- Connects the non-mathematical outline with further sections. --> |
| * <math>S</math>: The sender
| | |
| * <math>R</math>: The receiver
| |
| * <math>l</math>: Length of the output strings
| |
| * <math>s_0, s_1</math>: The strings output by the sender
| |
| * <math>c</math>: A bit denoting the receiver's choice
| |
| * For any bit <math>r</math>, ['''Computational, Hadamard''']<math>_r = \begin{cases}\mbox{Computational, if } r = 0\\ \mbox{Hadamard, if } r = 1\end{cases}</math>
| |
| * <math>\sigma_X = \begin{pmatrix}0 & 1 \\ 1 & 0 \end{pmatrix} </math>
| |
| * <math>\sigma_Z = \begin{pmatrix}1 & 0 \\ 0 & -1 \end{pmatrix} </math>
| |
| * For bits <math>v^{\alpha},v^{\beta}: |\phi^{(v^{\alpha},v^{\beta})}\rangle = (\sigma_Z^{v^{\alpha}}\sigma_X^{v^{\beta}} \otimes I) \frac{|00\rangle+|11\rangle}{\sqrt{2}}</math>
| |
| * An ENTCF family consists of two families of function pairs: <math>F</math> and <math>G</math>. A function pair <math>(f_{k,0},f_{k,1})</math>is indexed by a public key <math>k</math>. If <math>(f_{k,0},f_{k,1}) \in F</math>, then it is a ''claw-free pair''; and if <math>(f_{k,0},f_{k,1}) \in G</math>, then it is called an ''injective pair''. ENTCF families satisfy the following properties:
| |
| *# For a fixed <math>k \in K_F, f_{k,0}</math> and <math>f_{k,1}</math> are bijections with the same image; for every image <math>y</math>, there exists a unique pair <math>(x_0,x_1)</math>, called a ''claw'', such that <math>f_{k,0}(x_0) = f_{k,1}(x_1) = y</math>
| |
| *# Given a ''key'' <math>k \in K_F</math>, for a claw-free pair, it is quantum-computationally intractable (without access to ''trapdoor'' information) to compute both a <math>x_i</math> and a single generalized bit of <math>x_0 \oplus x_1</math>, where <math>(x_0,x_1)</math> forms a valid claw. This is known as the ''adaptive hardcore bit'' property.
| |
| *# For a fixed <math>k \in K_G, f_{k,0}</math> and <math>f_{k_1}</math> are injunctive functions with disjoint images.
| |
| *# Given a key <math>k \in K_F \cup K_G</math>, it is quantum-computationally hard (without access to ''trapdoor'' information) to determine whether <math>k</math> is a key for a claw-free or an injective pair. This property is known as ''injective invariance''.
| |
| *# For every <math>k \in K_F \cup K_G</math>, there exists a trapdoor <math>t_k</math> which can be sampled together with <math>k</math> and with which 2 and 4 are computationally easy.
| |
| <!-- ==Knowledge Graph== --> | | <!-- ==Knowledge Graph== --> |
| <!-- Add this part if the protocol is already in the graph --> | | <!-- Add this part if the protocol is already in the graph --> |
Line 47: |
Line 24: |
| ==Protocol Description== | | ==Protocol Description== |
| <!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. --> | | <!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. --> |
| ===Protocol 1: Rand 1-2 OT<math>^l</math>=== | | ===Protocol 1: DI Rand 1-2 OT<math>^l</math>=== |
| '''Requirements:''' Entanglement distribution, classical communication
| |
| | |
| '''Input:''' Receiver - a bit <math>c</math>
| |
| | |
| '''Output:''' Sender outputs randomly generated <math>s_0,s_1 \in \{0,1\}^l</math>, Receiver outputs <math>s_c</math>
| |
| # A device prepares <math>n</math> uniformly random Bell pairs <math>|\phi^{(v_i^{\alpha},v_i^{\beta})}\rangle, i = 1,...,n</math>, where the first qubit of each pair goes to <math>S</math> along with the string <math>v^{\alpha}</math>, and the second qubit of each pair goes to <math>R</math> along with the string <math>v^{\beta}</math>.
| |
| # R measures all qubits in the basis <math>y = [</math>'''Computational,Hadamard'''<math>]_c</math> where <math>c</math> is <math>R</math>'s choice bit. Let <math>b \in \{0,1\}^n</math> be the outcome. <math>R</math> then computes <math>b \oplus w^{\beta}</math>, where the <math>i</math>-th entry of <math>w^{\beta}</math> is defined by
| |
| #: <math>w_i^{\beta} := \begin{cases} 0, \mbox{if } y = \mbox{ Hadamard}\\ v_i^{\beta}, \mbox{if } y = \mbox{ Computational}\end{cases}</math>
| |
| # <math>S</math> picks uniformly random <math>x \in \{</math> '''Computational, Hadamard'''<math>\}^n</math>, and measures the <math>i</math>-th qubit in basis <math>x_i</math>. Let <math>a \in \{0,1\}^n</math> be the outcome. <math>S</math> then computes <math>a \oplus w^{\alpha}</math>, where the <math>i</math>-th entry of <math>w^{\alpha}</math> is defined by
| |
| #: <math>w_i^{\alpha} := \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{ Hadamard}\\ 0, \mbox{if } x_i = \mbox{ Computational}\end{cases}</math>
| |
| # <math>S</math> picks two uniformly random hash functions <math>f_0,f_1 \in F</math>, announces <math>x</math> and <math>f_0,f_1</math> to <math>R</math> and outputs <math>s_0 := f_0(a \oplus w^{\alpha} |_{I_0})</math> and <math>s_1 := f_1(a \oplus w^{\alpha} |_{I_1})</math> where <math>I_r := \{i \in I: x_i = [</math>'''Computational,Hadamard'''<math>]_r\}</math>
| |
| # <math>R</math> outputs <math>s_c = f_c(b \oplus w^{\beta} |_{I_c})</math>
| |
| | |
| | |
| ===Protocol 2: Self-testing with a single verifier===
| |
| '''Requirements:''' ENTCF function family, classical communication
| |
| | |
| # Alice chooses the state bases <math>\theta^A,\theta^B \in </math> {'''Computational,Hadamard'''} uniformly at random and generates key-trapdoor pairs <math>(k^A,t^A),(k^B,t^B)</math>, where the generation procedure for <math>k^A</math> and <math>t^A</math> depends on <math>\theta^A</math> and a security parameter <math>\eta</math>, and likewise for <math>k^B</math> and <math>t^B</math>. Alice supplies Bob with <math>k^B</math>. Alice and Bob then respectively send <math>k^A, k^B</math> to the device.
| |
| # Alice and Bob receive strings <math>c^A</math> and <math>c^B</math>, respectively, from the device.
| |
| # Alice chooses a ''challenge type'' <math>CT \in \{a,b\}</math>, uniformly at random and sends it to Bob. Alice and Bob then send <math>CT</math> to each component of their device.
| |
| # If <math>CT = a</math>:
| |
| ## Alice and Bob receive strings <math>z^A</math> and <math>z^B</math>, respectively, from the device.
| |
| # If <math>CT = b</math>:
| |
| ## Alice and Bob receive strings <math>d^A</math> and <math>d^B</math>, respectively, from the device.
| |
| ## Alice chooses uniformly random ''measurement bases (questions)'' <math>x,y \in</math> {'''Computational,Hadamard'''} and sends <math>y</math> to Bob. Alice and Bob then, respectively, send <math>x</math> and <math>y</math> to the device.
| |
| ## Alice and Bob receive answer bits <math>a</math> and <math>b</math>, respectively, from the device. Alice and Bob also receive bits <math>h^A</math> and <math>h^B</math>, respectively, from the device.
| |
| | |
| ===Protocol 3: DI Rand 1-2 OT<math>^l</math>===
| |
| '''Requirements:''' Entanglement distribution, ENTCF function family, classical communication
| |
| | |
| '''Input:''' Receiver - a bit <math>c</math>
| |
| | |
| '''Output:''' Sender outputs randomly generated <math>s_0,s_1 \in \{0,1\}^l</math>, Receiver outputs <math>s_c</math>
| |
| ::'''Data generation:''' | | ::'''Data generation:''' |
| # The sender and receiver execute <math>n</math> rounds of '''Protocol 2''' (Self-testing) with the sender as Alice and receiver as Bob, and with the following modification: | | # The sender and receiver execute <math>n</math> rounds of '''Protocol 2''' (Self-testing) with the sender as Alice and receiver as Bob, and with the following modification: |
Line 104: |
Line 48: |
| # Let <math>\tilde{I} := \{i : i \in I</math> and <math>T_i = </math> '''Generate'''} and <math>n^{\prime} = |\tilde{I}|</math>. The sender checks if there exists a <math> k > 0 </math> such that <math>\gamma n^{\prime} \leq n^{\prime}/4 - 2l -kn^{\prime}</math>. If such a <math>k</math> exists, the sender publishes <math>\tilde{I}</math> and, for each <math>i \in \tilde{I}</math>, the trapdoor <math>t_i^B</math> corresponding to the key <math>k_i^B</math> (given by the sender in the execution of '''Protocol 2,Step 1'''); otherwise the protocol aborts. | | # Let <math>\tilde{I} := \{i : i \in I</math> and <math>T_i = </math> '''Generate'''} and <math>n^{\prime} = |\tilde{I}|</math>. The sender checks if there exists a <math> k > 0 </math> such that <math>\gamma n^{\prime} \leq n^{\prime}/4 - 2l -kn^{\prime}</math>. If such a <math>k</math> exists, the sender publishes <math>\tilde{I}</math> and, for each <math>i \in \tilde{I}</math>, the trapdoor <math>t_i^B</math> corresponding to the key <math>k_i^B</math> (given by the sender in the execution of '''Protocol 2,Step 1'''); otherwise the protocol aborts. |
| <!-- INCLUDE V_i^ALPHA CALCULATION --> | | <!-- INCLUDE V_i^ALPHA CALCULATION --> |
| # For each <math>i \in \tilde{I},</math> the sender calculates <math>v_i^{\alpha} = d^A_i.(x_{i,0}^A \oplus x_{i,1}^A)</math> and defines <math>w^{\alpha}</math> by | | # For each <math>i \in \tilde{I},</math> the sender calculates <math>v_i^{\alpha}</math> and defines <math>w^{\alpha}</math> by |
| #:<math>w_i^{\alpha} = \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{Hadamard}\\ 0, \mbox{if } x_i = \mbox{Computational}\end{cases}</math> | | #:<math>w_i^{\alpha} = \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{Hadamard}\\ 0, \mbox{if } x_i = \mbox{Computational}\end{cases}</math> |
| #: and the receiver calculates <math>v_i^{\beta} = = d^B_i.(x_{i,0}^B \oplus x_{i,1}^B)</math> and defines <math>w^{\beta}</math> by | | #: and the receiver calculates <math>v_i^{\beta}</math> and defines <math>w^{\beta}</math> by |
| #:<math>w_i^{\beta} = \begin{cases} 0, \mbox{if } y_i = \mbox{Hadamard}\\ v_i^{\beta}, \mbox{if } y_i = \mbox{Computational}\end{cases}</math> | | #:<math>w_i^{\beta} = \begin{cases} 0, \mbox{if } y_i = \mbox{Hadamard}\\ v_i^{\beta}, \mbox{if } y_i = \mbox{Computational}\end{cases}</math> |
| #: '''Obtaining output:''' | | #: '''Obtaining output:''' |
Line 113: |
Line 57: |
|
| |
|
|
| |
|
| | ===Protocol 2: Self-testing with a single verifier=== |
| | # Alice chooses the state bases <math>\theta^A,\theta^B \in </math> {'''Computational,Hadamard'''} uniformly at random and generates key-trapdoor pairs <math>(k^A,t^A),(k^B,t^B)</math>, where the generation procedure for <math>k^A</math> and <math>t^A</math> depends on <math>\theta^A</math> and a security parameter <math>\eta</math>, and likewise for <math>k^B</math> and <math>t^B</math>. Alice supplies Bob with <math>k^B</math>. Alice and Bob then respectively send <math>k^A, k^B</math> to the device. |
| | # Alice and Bob receive strings <math>c^A</math> and <math>c^B</math>, respectively, from the device. |
| | # Alice chooses a ''challenge type'' <math>CT \in \{a,b\}</math>, uniformly at random and sends it to Bob. Alice and Bob then send <math>CT</math> to each component of their device. |
| | # If <math>CT = a</math>: |
| | ## Alice and Bob receive strings <math>z^A</math> and <math>z^B</math>, respectively, from the device. |
| | # If <math>CT = b</math>: |
| | ## Alice and Bob receive strings <math>d^A</math> and <math>d^B</math>, respectively, from the device. |
| | ## Alice chooses uniformly random ''measurement bases (questions)'' <math>x,y \in</math> {'''Computational,Hadamard'''} and sends <math>y</math> to Bob. Alice and Bob then, respectively, send <math>x</math> and <math>y</math> to the device. |
| | ## Alice and Bob receive answer bits <math>a</math> and <math>b</math>, respectively, from the device. Alice and Bob also receive bits <math>h^A</math> and <math>h^B</math>, respectively, from the device. |
| ==Properties== | | ==Properties== |
| <!-- important information on the protocol: parameters (threshold values), security claim, success probability... --> | | <!-- important information on the protocol: parameters (threshold values), security claim, success probability... --> |
| * <math>\epsilon</math>-'''Receiver security:''' If <math>R</math> is honest, then for any <math>\tilde{S}</math>, there exist random variables <math>S_0^{\prime}, S_1^{\prime}</math> such that Pr[<math>Y = S_c^{\prime}] \geq 1 - \epsilon</math> and <math>D(\rho_{c,S_0^{\prime}, S_1^{\prime},\tilde{S}}, \rho_c \otimes \rho_{S_0^{\prime}, S_1^{\prime},\tilde{S}}) \leq \epsilon</math>
| | |
| *: Protocol 3 is perfectly receiver secure, i.e. <math>\epsilon</math> = 0
| | |
| * <math>\epsilon</math>-'''Sender security:''' If S is honest, then for any <math>\tilde{R}</math>, there exist a random variable <math>c^{\prime}</math> such that <math>D(\rho_{S_{1-c^{\prime}},S_{c^{\prime}},c^{\prime},\tilde{R}}, \frac{1}{2^l}I \otimes \rho_{S_{c^{\prime}},c^{\prime},\tilde{R}}) \leq \epsilon</math>
| | ==Further Information== |
| *: Protocol 3 is <math>\epsilon^{\prime}</math>-sender secure, where <math>\epsilon^{\prime}</math> can be made negligible in certain conditions.
| | <!-- theoretical and experimental papers including requirements, security proof (important), which protocol does it implement, benchmark values... --> |
|
| |
|
| ==References== | | ==References== |
| * The protocol and its security proofs can be found in [https://arxiv.org/abs/2111.08595 Broadbent and Yuen(2021)]
| | |
| <div style='text-align: right;'>''*contributed by Chirag Wadhwa''</div> | | <div style='text-align: right;'>''*contributed by Chirag Wadhwa''</div> |