Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

On Single-Server Delegation of RSA

Giovanni Di Crescenzo, Matluba Khodjaeva, Ta Chen, Rajesh Krishnan, David H. Shur, Delaram Kahrobaei, Vladimir Shpilrain

Published Jan 1, 2023• 1 citation
Publisher
DOI
10.1007/978-3-031-32636-3_5

Related papers

Efficient and Secure Delegation of Group Exponentiation to a Single Server

Bren Cavallo, Giovanni Di Crescenzo, Delaram Kahrobaei +1 more

Lecture notes in computer science•Jan 1, 2015•30 citations

Security Analysis of a Server-Aided RSA Key Generation Protocol

Tianjie Cao, Xianping Mao, Dongdai Lin

Lecture notes in computer science•Jan 1, 2006•9 citations

Factorizing RSA Keys

Ed Blakey

Proceedings in information and communications technology•Dec 17, 2008•2 citations

Impossibility of blind quantum sampling for classical client

Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuch +1 more

Blind quantum computing enables a client, who can only generate or measure single-qubit states, to delegate quantum computing to a remote quantum server in such a way that the input, output, and program are hidden from the server. It is an open problem whether a completely classical client can delegate quantum computing blindly (in the information theoretic sense). In this paper, we show that if a completely classical client can blindly delegate sampling of subuniversal models, such as the DQC1 model and the IQP model, then the polynomial-time hierarchy collapses to the third level. Our delegation protocol is the one where the client first sends a polynomial-length bit string to the server and then the server returns a single bit to the client. Generalizing the no-go result to more general setups is an open problem.

arXiv:1812.03703•Quantum Information and Computation•Sep 1, 2019•5 citations

Generation of Shared RSA Keys by Two Parties

Guillaume Poupard, Jacques Stern

Lecture notes in computer science•Jan 1, 1998•49 citations

Sumcheck-based delegation of quantum computing to rational server

Yuki Takeuchi, Tomoyuki Morimae, Seiichiro Tani

Delegated quantum computing enables a client with weak computational power to delegate quantum computing to a remote quantum server in such a way that the integrity of the server can be efficiently verified by the client. Recently, a new model of delegated quantum computing has been proposed, namely, rational delegated quantum computing. In this model, after the client interacts with the server, the client pays a reward to the server depending on the server's messages and the client's random bits. The rational server sends messages that maximize the expected value of the reward. It is known that the classical client can delegate universal quantum computing to the rational quantum server in one round. In this paper, we propose novel one-round rational delegated quantum computing protocols by generalizing the classical rational sumcheck protocol. An advantage of our protocols is that they are gate-set independent: the construction of the previous rational protocols depends on gate sets, while our sumcheck technique can be easily realized with any local gate set (each of whose elementary gates can be specified with a polynomial number of bits). Furthermore, as with the previous protocols, our reward function satisfies natural requirements (the reward is non-negative, upper-bounded by a constant, and its maximum expected value is lower-bounded by a constant). We also discuss the reward gap. Simply speaking, the reward gap is a minimum loss on the expected value of the server's reward incurred by the server's behavior that makes the client accept an incorrect answer. The reward gap should therefore be large enough to incentivize the server to behave optimally. Although our sumcheck-based protocols have only exponentially small reward gaps as in the previous protocols, we show that a constant reward gap can be achieved if two noncommunicating but entangled rational servers are allowed. We also discuss whether a single rational server is sufficient under the (widely believed) assumption that the learning-with-errors problem is hard for polynomial-time quantum computing. Apart from these results, we show, under a certain condition, the equivalence between rational and ordinary delegated quantum computing protocols. This equivalence then serves as a basis for a reward-gap amplification method.

arXiv:1911.04734•Theoretical Computer Science•Apr 22, 2022•5 citations
Blind quantum computing enables a client, who can only generate or measure single-qubit states, to delegate quantum computing to a remote quantum server in such a way that the input, output, and program are hidden from the server. It is an open problem whether a completely classical client can delegate quantum computing blindly (in the information theoretic sense). In this paper, we show that if a completely classical client can blindly delegate sampling of subuniversal models, such as the DQC1 model and the IQP model, then the polynomial-time hierarchy collapses to the third level. Our delegation protocol is the one where the client first sends a polynomial-length bit string to the server and then the server returns a single bit to the client. Generalizing the no-go result to more general setups is an open problem.
Delegated quantum computing enables a client with weak computational power to delegate quantum computing to a remote quantum server in such a way that the integrity of the server can be efficiently verified by the client. Recently, a new model of delegated quantum computing has been proposed, namely, rational delegated quantum computing. In this model, after the client interacts with the server, the client pays a reward to the server depending on the server's messages and the client's random bits. The rational server sends messages that maximize the expected value of the reward. It is known that the classical client can delegate universal quantum computing to the rational quantum server in one round. In this paper, we propose novel one-round rational delegated quantum computing protocols by generalizing the classical rational sumcheck protocol. An advantage of our protocols is that they are gate-set independent: the construction of the previous rational protocols depends on gate sets, while our sumcheck technique can be easily realized with any local gate set (each of whose elementary gates can be specified with a polynomial number of bits). Furthermore, as with the previous protocols, our reward function satisfies natural requirements (the reward is non-negative, upper-bounded by a constant, and its maximum expected value is lower-bounded by a constant). We also discuss the reward gap. Simply speaking, the reward gap is a minimum loss on the expected value of the server's reward incurred by the server's behavior that makes the client accept an incorrect answer. The reward gap should therefore be large enough to incentivize the server to behave optimally. Although our sumcheck-based protocols have only exponentially small reward gaps as in the previous protocols, we show that a constant reward gap can be achieved if two noncommunicating but entangled rational servers are allowed. We also discuss whether a single rational server is sufficient under the (widely believed) assumption that the learning-with-errors problem is hard for polynomial-time quantum computing. Apart from these results, we show, under a certain condition, the equivalence between rational and ordinary delegated quantum computing protocols. This equivalence then serves as a basis for a reward-gap amplification method.