Device-Independent Oblivious Transfer
Jump to navigation
Jump to search
This example protocol achieves the task of device-independent oblivious transfer in the bounded quantum storage model using a computational assumption.
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: DI Rand 1-2 OT
- Data generation:
- 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, HadamardFailed 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} where is the receiver's choice bit. Let 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 I} 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
- For every the sender stores the variable (round type), defined as follows:
- if and Hadamard, then Bell
- else, set Product
- 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:
- 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.
- 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:
- 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.
- For each the sender calculates and defines by
- and the receiver calculates and defines by
- Obtaining output:
- The sender randomly picks two hash functions , announces and for each , and outputs and , where Computational,Hadamard
- Receiver outputs
Protocol 2: Self-testing with a single verifier
- 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.
- Alice and Bob receive strings and , respectively, from the device.
- Alice chooses a challenge type , uniformly at random and sends it to Bob. Alice and Bob then send to each component of their device.
- If :
- Alice and Bob receive strings and , respectively, from the device.
- If :
- Alice and Bob receive strings and , respectively, from the device.
- Alice chooses uniformly random measurement bases (questions) {Computational,Hadamard} and sends to Bob. Alice and Bob then, respectively, send and to the device.
- Alice and Bob receive answer bits and , respectively, from the device. Alice and Bob also receive bits and , respectively, from the device.
Properties
Further Information
References
*contributed by Chirag Wadhwa