Secure Client- Server Delegated Computation

Functionality Description

Delegated Computation is the task of assigning computation on hidden data to a powerful untrusted party (a device) by a weak (in terms of computational powers) party while maintaining privacy of hidden data from the powerful party. Protocols under this functionality are commonly called Client-Server protocols. Delegated Quantum Computation (DQC) protocols involve partially or fully classical Client delegating a quantum computation to fully powerful single/multiple quantum Server/Servers. All DQC protocols involve three main stages, Preparation Stage, Computation Stage and Output Correction Stage. The roles of Client and Server in the different stages may differ according to the type of communication used see Protocols list.

Tags: Two Party, Universal Tasks, Secure Verifiable Client-Server Delegated Quantum Computation, Secure Multi-Party Delegated Computation, Secure Delegated Classical Computation, Quantum Functionality

Use-case

• Quantum Task
• No classical analog for Blind Quantum Computing where input, output and computation can be hidden. Classical analogue for Homomorphic encryption techniques exist, hiding only the input and the output of the client and not the computation.
• Quantum machine learning

Protocols

• The protocols enlisted here mainly differ in terms of the type of communication channels required. An online link means it is used throughout the protocol. An offline link means it is used only at the starting or ending of the protocol (one-time use channels) and there is no continuous exchange of information. A quantum communication link is used to transfer quantum states/information and classical links are used for exchange of classical information. These terms will be related with each protocol enlisted below.

1. Prepare and Send-Universal Blind Quantum Computation:Quantum Memory Network Stage. Requires classical online communication-quantum offline communication. Hides input, output and computation of the client
2. Measurement Only-Universal Blind Quantum Computation:Quantum Memory Network Stage. Requires classical online communication-quantum online communication. Hides input, output and computation of the client.
3. Pseudo-Secret Random Qubit Generator (PSQRG):Quantum Memory Network Stage. Requires classical offline communication- quantum offline communication.
4. Prepare and Send Quantum Fully Homomorphic Encryption:Quantum Memory Network Stage. Requires classical online communication-no quantum communication. Hides input and output of the client.
5. Classical Fully Homomorphic Encryption for Quantum Circuits:Quantum Memory Network Stage. Requires classical offline communication-no quantum communication. Hides input and output of the client.

• All the above protocols require the server to be a quantum memory network stage node. However, with respect to the client, (1) requires the client to only prepare and send quantum states while (2) requires client to just receive and measure quantum states. Thus, client belongs to a simple prepare and measure network stage node. This information is useful in case there are only a few nodes with advanced technologies like quantum memory.
• Protcols for verifiable version of protocols (1), (2), (4) can be found on the page Verifiable Delegated Quantum Computation. Verifiable versions of protocols (3) and (5) are open questions.

Properties

• Universality A protocol for delegated quantum computation is universal if it client can use the server to compute any quantum circuit.
• Correctness A protocol is correct if the output of client's input after Server's processing is correct, given that both parties follow the protocol honestly.
• Blindness The protocol is blind to the server (who, in this case is the adversary/dishonest party) means that client's computation is hidden from the server during the entire protocol.
• Compactness Decryption of datat the end of the protocol should be independent of the size of the quantum circuit used for computation
• Full Homomorphism A homomorphic encryption which can perform any quantum computation

Further Information

Secure Delegated Computation was an open problem in classical computation until Gentry's work in 1994 on Homomorphic Encryption using Lattice Based Cryptography (1). An analogue was required in case of delegating quantum data. Childs proposed the first work in the field in 2005 (2). Unlike the classical scheme, this protocol could not only hide the input and output of the client from the sever but also client's computation. This was a breakthrough as there exists no such scheme in classical cryptography which could provide this additional functionality, called 'blindness'. Arrighi and Salvail later showed (3) that hiding of computation was possible only for a few functions. They also coined the notion of verifiability. In 2009, Broadbent, Fitzsimons and Kashefi developed prepare and send universal blind quantum computation, which was the first scheme to solve this problem for any quantum circuit. This property, also known as universality, opened the gates for further research in this field. New protocols came into picture, some using the measurement based quantum computation framework like blind quantum computation and some devising homomorphic encryption for quantum data. Out of which, prepare-and-send universal blind quantum computation has been proven to be universally composable i.e. it is secure in any and every scenerio possible. The only other protocol which is proven to be universally composable is Quantum Key Distribution. All the above protocols required quantum communication until the latest work by Urmila Mahadev in 2018, classical fully homomorphic encryption for quantum circuits. It requires no quantum operation on the client's side. pseudo-secret random qubit generator is a functionality different from delegation of quantum computation. It comes with multiple uses, one of which being universal blind quantum computation. This protocol also requires no quantum computation on client's side in order to instruct server to prepare her secret random qubits, of which she has complete knowledge but not the server.
Review Papers:

• Fitzsimons (2017) gives an overview of delegated quantum computation
• Dunjko et al (2013) gives the abstract cryptography framework for delegated computing and uses it prove universal composability of UBQC.

References

1. Gentry (1994)
2. Childs (2005)
3. Arrighi and Salavil (2006)

*contributed by Shraddha Singh