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

arXiv:1706.06963 · Physical Review Letters

Knowledge-Concealing Evidencing of Knowledge About a Quantum State

Emily Adlam, Adrian Kent

Published Jan 30, 2018• 3 citations
arXivHTMLPDF

Abstract

Bob has a black box that emits a single pure state qudit which is, from his perspective, uniformly distributed. Alice wishes to give Bob evidence that she has knowledge about the emitted state while giving him little or no information about it. We show that zero-knowledge evidencing of such knowledge is impossible in quantum relativistic protocols, extending a previous result of Horodecki, Horodecki, and Horodecki. We also show that no such protocol can be both sound and complete. We present a new quantum relativistic protocol which we conjecture to be close to optimal in security against Alice and which reveals little knowledge to Bob, for large dimension d. We analyze its security against general attacks by Bob and restricted attacks by Alice.

DOI
10.1103/physrevlett.120.050501

Related papers

Zero-knowledge convincing protocol on quantum bit is impossible

Pawel Horodecki, Michal Horodecki, Ryszard Horodecki

Consider two parties: Alice and Bob and suppose that Bob is given a qubit system in a quantum state ϕ , unknown to him. Alice knows ϕ and she is supposed to convince Bob that she knows ϕ sending some test message. Is it possible for her to convince Bob providing him "zero knowledge" i. e. no information about ϕ he has? We prove that there is no "zero knowledge" protocol of that kind. In fact it turns out that basing on Alice message, Bob (or third party - Eve - who can intercept the message) can synthetize a copy of the unknown qubit state ϕ with nonzero probability. This "no-go" result puts general constrains on information processing where information about quantum state is involved.

arXiv:quant-ph/0010048•Quantum•Dec 23, 2017•5 citations

Zero knowledge convincing protocol on quantum bit is impossible

Horodecki, P, Horodecki, M, Horodecki, R

Consider two parties: Alice and Bob and suppose that Bob is given a qubit system in a quantum state $\\phi$, unknown to him. Alice knows $\\phi$ and she is supposed to convince Bob that she knows $\\phi$ sending some test message. Is it possible for her to convince Bob providing him "zero knowledge" i. e. no information about $\\phi$ he has? We prove that there is no "zero knowledge" protocol of that kind. In fact it turns out that basing on Alice message, Bob (or third party - Eve - who can intercept the message) can synthetize a copy of the unknown qubit state $\\phi$ with nonzero probability. This "no-go" result puts general constrains on information processing where information {\\it about} quantum state is involved.

•Oct 12, 2000•2 citations

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

Relativistic Quantum Tasks

Emily Adlam

Quantum mechanics, which describes the behaviour of matter and energy on very small scales, is one of the most successful theories in the history of science. Einstein's theory of special relativity, which describes the relationship between space and time, is likewise a highly successful and widely accepted theory. And yet there is a well-documented tension between the two theories, to the extent that it is still not clear that the two can ever be reconciled. This thesis is concerned with furthering the current understanding of the relationship between quantum mechanics and special relativity. In the first part of the thesis we study the behaviour of quantum information in relativistic spacetime. The field of quantum information arose from the realisation that quantum information has a number of crucial properties that distinguish it from classical information, such as the no-cloning property, quantum contextuality, and quantum discord. More recently, it has been realised that placing quantum information under relativistic constraints leads to the emergence of further unique features which are not exhibited by either non-relativistic quantum information or relativistic classical information; as part of this ongoing research programme we develop a new relativistic quantum `paradox' which puts pressure on conventional views about the spatiotemporal persistence of quantum states over time. We then study a new set of relativistic quantum protocols which involve the distribution of entangled states over spacetime, defining one task involving the distribution of the two halves of a known entangled state, and another task involving the distribution of the two halves of an unknown entangled state. The second part of the thesis deals with relativistic quantum cryptography, a field which first began attracting serious attention when it was realised that a cryptographic task known as `bit commitment,' can be implemented with perfect security under relativistic constraints. This result was highly significant, since it is provably impossible to implement bit commitment with perfect security in a purely classical or purely quantum context, and hence bit commitment is an ideal starting point for probing the power of relativistic quantum cryptography. In this thesis we propose several new relativistic quantum bit commitment protocols which have notable advantages over previously known protocols. We then move to a related task, a generalization of zero-knowledge proving which we refer to as knowledge-concealing evidencing of knowledge of a quantum state; we prove no-go theorems concerning the possibility of implementing this task with perfect security, and then set out a relativistic protocol for the task which is asymptotically secure as the dimension of the state in question becomes large. These results have interesting foundational significance above and beyond their applications in the field of cryptography, providing a new perspective on the connections between knowledge, realism and quantum states.

•Sep 1, 2017•5 citations

Quantum Key Distribution with Classical Bob

Michel Boyer, Dan Kenigsberg, Tal Mor

Secure key distribution among two remote parties is impossible when both are classical, unless some unproven computation-complexity assumptions are made, such as the difficulty of factorizing large numbers. On the other hand, a secure key distribution is possible when both parties are quantum. What is possible when only one party (Alice) is quantum, yet the other (Bob) has only classical capabilities? We present a protocol with this constraint and prove its robustness against attacks: we prove that any attempt of an adversary to obtain information necessarily induces some errors that the legitimate users could notice.

arXiv:quant-ph/0703107•Physical Review Letters•Oct 5, 2007•392 citations

Quantum Key Distribution with Classical Bob

Michel Boyer, Dan Kenigsberg, Tal Mor

Secure key distribution among two remote parties is impossible when both are classical, unless some unproven (and arguably unrealistic) computation-complexity assumptions are made, such as the difficulty of factorizing large numbers. On the other hand, a secure key distribution is possible when both parties are quantum. What is possible when only one party (Alice) is quantum, yet the other (Bob) has only classical capabilities? We present two protocols with this constraint, and prove their robustness against attacks: we prove that any attempt of an adversary to obtain information (and even a tiny amount of information) necessarily induces some errors that the legitimate users could notice.

International Conference on Quantum, Nano and Micro Technologies (ICQNM)•Jan 1, 2007•79 citations
Bob has a black box that emits a single pure state qudit which is, from his perspective, uniformly distributed. Alice wishes to give Bob evidence that she has knowledge about the emitted state while giving him little or no information about it. We show that zero-knowledge evidencing of such knowledge is impossible in quantum relativistic protocols, extending a previous result of Horodecki, Horodecki, and Horodecki. We also show that no such protocol can be both sound and complete. We present a new quantum relativistic protocol which we conjecture to be close to optimal in security against Alice and which reveals little knowledge to Bob, for large dimension d. We analyze its security against general attacks by Bob and restricted attacks by Alice.
Consider two parties: Alice and Bob and suppose that Bob is given a qubit system in a quantum state ϕ , unknown to him. Alice knows ϕ and she is supposed to convince Bob that she knows ϕ sending some test message. Is it possible for her to convince Bob providing him "zero knowledge" i. e. no information about ϕ he has? We prove that there is no "zero knowledge" protocol of that kind. In fact it turns out that basing on Alice message, Bob (or third party - Eve - who can intercept the message) can synthetize a copy of the unknown qubit state ϕ with nonzero probability. This "no-go" result puts general constrains on information processing where information about quantum state is involved.
Consider two parties: Alice and Bob and suppose that Bob is given a qubit system in a quantum state phi\\phiphi, unknown to him. Alice knows phi\\phiphi and she is supposed to convince Bob that she knows phi\\phiphi sending some test message. Is it possible for her to convince Bob providing him "zero knowledge" i. e. no information about phi\\phiphi he has? We prove that there is no "zero knowledge" protocol of that kind. In fact it turns out that basing on Alice message, Bob (or third party - Eve - who can intercept the message) can synthetize a copy of the unknown qubit state phi\\phiphi with nonzero probability. This "no-go" result puts general constrains on information processing where information {\\it about} quantum state is involved.
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.
Quantum mechanics, which describes the behaviour of matter and energy on very small scales, is one of the most successful theories in the history of science. Einstein's theory of special relativity, which describes the relationship between space and time, is likewise a highly successful and widely accepted theory. And yet there is a well-documented tension between the two theories, to the extent that it is still not clear that the two can ever be reconciled. This thesis is concerned with furthering the current understanding of the relationship between quantum mechanics and special relativity. In the first part of the thesis we study the behaviour of quantum information in relativistic spacetime. The field of quantum information arose from the realisation that quantum information has a number of crucial properties that distinguish it from classical information, such as the no-cloning property, quantum contextuality, and quantum discord. More recently, it has been realised that placing quantum information under relativistic constraints leads to the emergence of further unique features which are not exhibited by either non-relativistic quantum information or relativistic classical information; as part of this ongoing research programme we develop a new relativistic quantum `paradox' which puts pressure on conventional views about the spatiotemporal persistence of quantum states over time. We then study a new set of relativistic quantum protocols which involve the distribution of entangled states over spacetime, defining one task involving the distribution of the two halves of a known entangled state, and another task involving the distribution of the two halves of an unknown entangled state. The second part of the thesis deals with relativistic quantum cryptography, a field which first began attracting serious attention when it was realised that a cryptographic task known as `bit commitment,' can be implemented with perfect security under relativistic constraints. This result was highly significant, since it is provably impossible to implement bit commitment with perfect security in a purely classical or purely quantum context, and hence bit commitment is an ideal starting point for probing the power of relativistic quantum cryptography. In this thesis we propose several new relativistic quantum bit commitment protocols which have notable advantages over previously known protocols. We then move to a related task, a generalization of zero-knowledge proving which we refer to as knowledge-concealing evidencing of knowledge of a quantum state; we prove no-go theorems concerning the possibility of implementing this task with perfect security, and then set out a relativistic protocol for the task which is asymptotically secure as the dimension of the state in question becomes large. These results have interesting foundational significance above and beyond their applications in the field of cryptography, providing a new perspective on the connections between knowledge, realism and quantum states.
Secure key distribution among two remote parties is impossible when both are classical, unless some unproven computation-complexity assumptions are made, such as the difficulty of factorizing large numbers. On the other hand, a secure key distribution is possible when both parties are quantum. What is possible when only one party (Alice) is quantum, yet the other (Bob) has only classical capabilities? We present a protocol with this constraint and prove its robustness against attacks: we prove that any attempt of an adversary to obtain information necessarily induces some errors that the legitimate users could notice.
Secure key distribution among two remote parties is impossible when both are classical, unless some unproven (and arguably unrealistic) computation-complexity assumptions are made, such as the difficulty of factorizing large numbers. On the other hand, a secure key distribution is possible when both parties are quantum. What is possible when only one party (Alice) is quantum, yet the other (Bob) has only classical capabilities? We present two protocols with this constraint, and prove their robustness against attacks: we prove that any attempt of an adversary to obtain information (and even a tiny amount of information) necessarily induces some errors that the legitimate users could notice.