Blind delegation protocols allow a client to delegate a computation to a server so that the server learns nothing about the input to the computation apart from its size. For the specific case of quantum computation we know that blind delegation protocols can achieve information-theoretic security. In this paper we prove, provided certain complexity-theoretic conjectures are true, that the power of information-theoretically secure blind delegation protocols for quantum computation (ITS-BQC protocols) is in a number of ways constrained. In the first part of our paper we provide some indication that ITS-BQC protocols for delegating $\sf BQP$ computations in which the client and the server interact only classically are unlikely to exist. We first show that having such a protocol with $O(n^d)$ bits of classical communication implies that $\mathsf{BQP} \subset \mathsf{MA/O(n^d)}$ . We conjecture that this containment is unlikely by providing an oracle relative to which $\mathsf{BQP} \not\subset \mathsf{MA/O(n^d)}$ . We then show that if an ITS-BQC protocol exists with polynomial classical communication and which allows the client to delegate quantum sampling problems, then there exist non-uniform circuits of size $2^{n - \mathsfΩ(n/log(n))}$ , making polynomially-sized queries to an $\sf NP^{NP}$ oracle, for computing the permanent of an $n \times n$ matrix. The second part of our paper concerns ITS-BQC protocols in which the client and the server engage in one round of quantum communication and then exchange polynomially many classical messages. First, we provide a complexity-theoretic upper bound on the types of functions that could be delegated in such a protocol, namely $\mathsf{QCMA/qpoly \cap coQCMA/qpoly}$ . Then, we show that having such a protocol for delegating $\mathsf{NP}$ -hard functions implies $\mathsf{coNP^{NP^{NP}}} \subseteq \mathsf{NP^{NP^{PromiseQMA}}}$ .Blind delegation protocols allow a client to delegate a computation to a server so that the server learns nothing about the input to the computation apart from its size. For the specific case of quantum computation we know that blind delegation protocols can achieve information-theoretic security. In this paper we prove, provided certain complexity-theoretic conjectures are true, that the power of information-theoretically secure blind delegation protocols for quantum computation (ITS-BQC protocols) is in a number of ways constrained. In the first part of our paper we provide some indication that ITS-BQC protocols for delegating $\sf BQP$ computations in which the client and the server interact only classically are unlikely to exist. We first show that having such a protocol with $O(n^d)$ bits of classical communication implies that $\mathsf{BQP} \subset \mathsf{MA/O(n^d)}$. We conjecture that this containment is unlikely by providing an oracle relative to which $\mathsf{BQP} \not\subset \mathsf{MA/O(n^d)}$. We then show that if an ITS-BQC protocol exists with polynomial classical communication and which allows the client to delegate quantum sampling problems, then there exist non-uniform circuits of size $2^{n - \mathsfΩ(n/log(n))}$, making polynomially-sized queries to an $\sf NP^{NP}$ oracle, for computing the permanent of an $n \times n$ matrix. The second part of our paper concerns ITS-BQC protocols in which the client and the server engage in one round of quantum communication and then exchange polynomially many classical messages. First, we provide a complexity-theoretic upper bound on the types of functions that could be delegated in such a protocol, namely $\mathsf{QCMA/qpoly \cap coQCMA/qpoly}$. Then, we show that having such a protocol for delegating $\mathsf{NP}$-hard functions implies $\mathsf{coNP^{NP^{NP}}} \subseteq \mathsf{NP^{NP^{PromiseQMA}}}$.

arXiv:1704.08482Leibniz international proceedings in informaticsApr 27, 20179 citations

ID-based Tripartite Multiple Key Agreement Protocol Facilitating Computer Auditing and Transaction Refereeing

Hung‐Yu Chien

Computer auditing and transaction refereeing require the system to keep genuine records. However, it is difficult for an auditor or a referee to on-line audit the contents or involve in the communication while the communication is kept confidential from others. This problem has a promising solution, when Joux proposed the first efficient tripartite key agreement protocol that enables three parties (that might include one referee) to establish a secure session key. However, several published schemes are not secure. This paper examines the weaknesses, and then proposes an ID-based tripartite multiple key agreement protocol to raise the level of security and improve the efficiency. The security is proved in a modified Bellare-Pointcheval-Rogaway model.Computer auditing and transaction refereeing require the system to keep genuine records. However, it is difficult for an auditor or a referee to on-line audit the contents or involve in the communication while the communication is kept confidential from others. This problem has a promising solution, when Joux proposed the first efficient tripartite key agreement protocol that enables three parties (that might include one referee) to establish a secure session key. However, several published schemes are not secure. This paper examines the weaknesses, and then proposes an ID-based tripartite multiple key agreement protocol to raise the level of security and improve the efficiency. The security is proved in a modified Bellare-Pointcheval-Rogaway model.

Oct 1, 20064 citations

Classical computation

A. Kitaev, Alexander Khanievich Shen', M. Vyalyi

Graduate studies in mathematicsMay 31, 20021 citation

Theory of Computation

Salvador Elías Venegas-Andraca

Synthesis lectures on quantum computingJan 1, 20080 citations

\sf BQP

computations in which the client and the server interact only classically are unlikely to exist. We first show that having such a protocol with

O(n^d)

bits of classical communication implies that

\mathsf{BQP} \subset \mathsf{MA/O(n^d)}

. We conjecture that this containment is unlikely by providing an oracle relative to which

\mathsf{BQP} \not\subset \mathsf{MA/O(n^d)}

. We then show that if an ITS-BQC protocol exists with polynomial classical communication and which allows the client to delegate quantum sampling problems, then there exist non-uniform circuits of size

2^{n - \mathsfΩ(n/log(n))}

, making polynomially-sized queries to an

\sf NP^{NP}

oracle, for computing the permanent of an

n \times n

matrix. The second part of our paper concerns ITS-BQC protocols in which the client and the server engage in one round of quantum communication and then exchange polynomially many classical messages. First, we provide a complexity-theoretic upper bound on the types of functions that could be delegated in such a protocol, namely

\mathsf{QCMA/qpoly \cap coQCMA/qpoly}

. Then, we show that having such a protocol for delegating

\mathsf{NP}

-hard functions implies

\mathsf{coNP^{NP^{NP}}} \subseteq \mathsf{NP^{NP^{PromiseQMA}}}