Open main menu

Quantum Protocol Zoo β

Device-Independent Oblivious Transfer

Revision as of 18:19, 20 January 2022 by Chirag (talk | contribs)


This example protocol achieves the task of device-independent oblivious transfer in the bounded quantum storage model using a computational assumption.

Contents

Assumptions

  • The quantum storage of the receiver is bounded 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

Outline

Notation

Protocol Description

Protocol 1: Rand 1-2 OT 

  1. A device prepares   uniformly random Bell pairs  , where the first qubit of each pair goes to   along with the string  , and the second qubit of each pair goes to   along with the string  .
  2. R measures all qubits in the basis  Computational,Hadamard  where   is  's choice bit. Let   be the outcome.   then computes  , where the  -th entry of   is defined by
     
  3.   picks uniformly random   Computational, Hadamard , and measures the  -th qubit in basis  . Let   be the outcome.   then computes  , where the  -th entry of   is defined by
     
  4.   picks two uniformly random hash functions  , announces   and   to   and outputs   and   where  Computational,Hadamard 
  5.   outputs  


Protocol 2: Self-testing with a single verifier

  1. Alice chooses the state bases   {Computational,Hadamard} uniformly at random and generates key-trapdoor pairs  , where the generation procedure for   and   depends on   and a security parameter  , and likewise for   and  . Alice supplies Bob with  . Alice and Bob then respectively send   to the device.
  2. Alice and Bob receive strings   and  , respectively, from the device.
  3. Alice chooses a challenge type  , uniformly at random and sends it to Bob. Alice and Bob then send   to each component of their device.
  4. If  :
    1. Alice and Bob receive strings   and  , respectively, from the device.
  5. If  :
    1. Alice and Bob receive strings   and  , respectively, from the device.
    2. Alice chooses uniformly random measurement bases (questions)   {Computational,Hadamard} and sends   to Bob. Alice and Bob then, respectively, send   and   to the device.
    3. Alice and Bob receive answer bits   and  , respectively, from the device. Alice and Bob also receive bits   and  , respectively, from the device.

Protocol 3: DI Rand 1-2 OT 

Data generation:
  1. The sender and receiver execute   rounds of Protocol 2 (Self-testing) with the sender as Alice and receiver as Bob, and with the following modification:
    If  , then with probability  , the receiver does not use the measurement basis question supplied by the sender and instead inputs  Computational, Hadamard  where   is the receiver's choice bit. Let   be the set of indices marking the rounds where this has been done.
    For each round  , the receiver stores:
    •  
    •   if  
    • or   if  
    The sender stores   and   if   or   and   if  
  2. For every   the sender stores the variable   (round type), defined as follows:
    • if   and  Hadamard, then   Bell
    • else, set   Product
  3. For every   the sender chooses  , indicating a test round or generation round, as follows:
    • if   Bell, choose   {Test, Generate} uniformly at random
    • else, set   Test
    The sender sends ( ) to the receiver
    Testing:
  4. The receiver sends the set of indices   to the sender. The receiver publishes their output for all   Test rounds where  . Using this published data, the sender determines the bits which an honest device would have returned.
  5. The sender computes the fraction of test rounds (for which the receiver has published data for) that failed. If this exceeds some  , the protocol aborts
    Preparing data:
  6. Let   and   Generate} and  . The sender checks if there exists a   such that  . If such a   exists, the sender publishes   and, for each  , the trapdoor   corresponding to the key   (given by the sender in the execution of Protocol 2,Step 1); otherwise the protocol aborts.
  7. For each   the sender calculates   and defines   by
     
    and the receiver calculates   and defines   by
     
    Obtaining output:
  8. The sender randomly picks two hash functions  , announces   and   for each  , and outputs   and  , where  Computational,Hadamard 
  9. Receiver outputs  


Properties

Further Information

References

*contributed by Chirag Wadhwa