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

Impossibility Results for Static Input Secure Computation

Sanjam Garg, Abishek Kumarasubramanian, Rafail Ostrovsky, Ivan Visconti

Published Jan 1, 2012• 21 citations
Publisher
DOI
10.1007/978-3-642-32009-5_25

Related papers

Secure Two-Party Quantum Computation Over Classical Channels

Michele Ciampi, Alexandru Cojocaru, Elham Kashefi +1 more

Secure two-party computation considers the problem of two parties computing a joint function of their private inputs without revealing anything beyond the output. In this work, we consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. Our first result shows that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. In particular, we show that the existence of a secure quantum computing protocol that relies only on classical channels would contradict the quantum no-cloning argument. We circumvent this impossibility following three different approaches. The first is by considering a weaker security notion called one-sided simulation security. This notion protects the input of one party (the quantum Bob) in the standard simulation-based sense and protects the privacy of the other party's input (the classical Alice). We show how to realize a protocol that satisfies this notion relying on the learning with errors assumption. The second way to circumvent the impossibility result, while at the same time providing standard simulation-based security also against a malicious Bob, is by assuming that the quantum input has an efficient classical representation. Finally, we focus our attention on the class of zero-knowledge functionalities and provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties. The direct implication of our result is that Mahadev's protocol for classical verification of quantum computations (FOCS'18) can be turned into a zero-knowledge proof of quantum knowledge with classical verifiers. To the best of our knowledge, we are the first to instantiate such a primitive.

arXiv:2010.07925•Oct 15, 2020•7 citations

Almost-Everywhere Secure Computation

Juan A. Garay, Rafail Ostrovsky

Springer eBooks•Apr 4, 2008•56 citations

Succinct Non-interactive Secure Computation

Andrew Morgan, Rafael Pass, Antigoni Polychroniadou

Lecture notes in computer science•Jan 1, 2020•10 citations

A Constant Lower Bound for Any Quantum Protocol for Secure Function Evaluation

Osborn, Sarah A., Jamie Sikora

Secure function evaluation is a two-party cryptographic primitive where Bob computes a function of Alice's and his respective inputs, and both hope to keep their inputs private from the other party. It has been proven that perfect (or near perfect) security is impossible, even for quantum protocols. We generalize this no-go result by exhibiting a constant lower bound on the cheating probabilities for any quantum protocol for secure function evaluation, and present many applications from oblivious transfer to the millionaire's problem. Constant lower bounds are of practical interest since they imply the impossibility to arbitrarily amplify the security of quantum protocols by any means.

arXiv:2203.08268•Leibniz international proceedings in informatics•Jan 1, 2022•2 citations

An nnn-Card Threshold Protocol Is Impossible

Shizuru Iino, Yang Li, Kazuo Sakiyama +1 more

Card-based cryptography uses a physical deck of playing cards to achieve secure computations. The first card-based protocol, called the five-card trick, allows Alice and Bob to decide whether to have a date without revealing their actual minds, i.e., it performs a secure computation of the logical two-input AND function. It uses a two-color deck of red and black cards, and the Boolean values are encoded based on the arrangement order of two distinct cards. The five-card trick was later optimized into a four-card AND protocol, achieving the minimal number of cards, because each input bit is encoded using two cards. Afterward, an alternative encoding, where each bit is represented by a single card, enabled a three-card AND protocol with a minor modification to the five-card trick. However, the construction of a two-card AND protocol remains an open problem. In this study, we provide a negative result for the problem: a two-card AND protocol is impossible. We extend this result to a more general class of functions, and consequently, derive the main impossibility theorem: an$n$-card$n$-input threshold protocol is impossible. Our result implies that the three-card AND protocol uses the minimal number of cards. A unique aspect of our proof is its simplicity; we show that it suffices to consider the initial and its subsequent states, unlike previous impossibility proofs that enumerate all possible states.

IEEE Annual Computing and Communication Workshop and Conference (CCWC)•Jan 5, 2026•0 citations

Efficient Non-interactive Secure Computation

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky +2 more

Lecture notes in computer science•Jan 1, 2011•118 citations
Secure two-party computation considers the problem of two parties computing a joint function of their private inputs without revealing anything beyond the output. In this work, we consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. Our first result shows that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. In particular, we show that the existence of a secure quantum computing protocol that relies only on classical channels would contradict the quantum no-cloning argument. We circumvent this impossibility following three different approaches. The first is by considering a weaker security notion called one-sided simulation security. This notion protects the input of one party (the quantum Bob) in the standard simulation-based sense and protects the privacy of the other party's input (the classical Alice). We show how to realize a protocol that satisfies this notion relying on the learning with errors assumption. The second way to circumvent the impossibility result, while at the same time providing standard simulation-based security also against a malicious Bob, is by assuming that the quantum input has an efficient classical representation. Finally, we focus our attention on the class of zero-knowledge functionalities and provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties. The direct implication of our result is that Mahadev's protocol for classical verification of quantum computations (FOCS'18) can be turned into a zero-knowledge proof of quantum knowledge with classical verifiers. To the best of our knowledge, we are the first to instantiate such a primitive.
Secure function evaluation is a two-party cryptographic primitive where Bob computes a function of Alice's and his respective inputs, and both hope to keep their inputs private from the other party. It has been proven that perfect (or near perfect) security is impossible, even for quantum protocols. We generalize this no-go result by exhibiting a constant lower bound on the cheating probabilities for any quantum protocol for secure function evaluation, and present many applications from oblivious transfer to the millionaire's problem. Constant lower bounds are of practical interest since they imply the impossibility to arbitrarily amplify the security of quantum protocols by any means.
Card-based cryptography uses a physical deck of playing cards to achieve secure computations. The first card-based protocol, called the five-card trick, allows Alice and Bob to decide whether to have a date without revealing their actual minds, i.e., it performs a secure computation of the logical two-input AND function. It uses a two-color deck of red and black cards, and the Boolean values are encoded based on the arrangement order of two distinct cards. The five-card trick was later optimized into a four-card AND protocol, achieving the minimal number of cards, because each input bit is encoded using two cards. Afterward, an alternative encoding, where each bit is represented by a single card, enabled a three-card AND protocol with a minor modification to the five-card trick. However, the construction of a two-card AND protocol remains an open problem. In this study, we provide a negative result for the problem: a two-card AND protocol is impossible. We extend this result to a more general class of functions, and consequently, derive the main impossibility theorem: annnn-cardnnn-input threshold protocol is impossible. Our result implies that the three-card AND protocol uses the minimal number of cards. A unique aspect of our proof is its simplicity; we show that it suffices to consider the initial and its subsequent states, unlike previous impossibility proofs that enumerate all possible states.