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

IEEE International Symposium on Information Theory (ISIT)

Conditional Disclosure of Secrets: A Noise and Signal Alignment Approach

Zhou Li, Hua Sun

Published Jun 1, 2020• 6 citations
Publisher

Abstract

In the conditional disclosure of secrets (CDS) problem, Alice and Bob (each holds an input and a common secret) wish to disclose, as efficiently as possible, the secret to Carol if and only if their inputs satisfy some function. The capacity of CDS is the maximum number of bits of the secret that can be securely disclosed per bit of total communication. We characterize the necessary and sufficient condition for the extreme case where the capacity of CDS is the highest and is equal to 1/2.

DOI
10.1109/isit44484.2020.9174262

Related papers

Conditional Disclosure of Secrets: A Noise and Signal Alignment Approach

Zhou Li, Hua Sun

In the conditional disclosure of secrets (CDS) problem, Alice and Bob (each holds an input and a common secret) wish to disclose, as efficiently as possible, the secret to Carol if and only if their inputs satisfy some function. The capacity of CDS is the maximum number of bits of the secret that can be securely disclosed per bit of total communication. We characterize the necessary and sufficient condition for the extreme case where the capacity of CDS is the highest and is equal to$1/2$. For the simplest instance where the capacity is smaller than$1/2$, we show that the linear capacity is$2/5$.

arXiv:2002.05691•IEEE Transactions on Communications•Apr 18, 2022•12 citations

Noise Capacity of Conditional Disclosure of Secrets: A Graph-Theoretic Perspective

Zhou Li, Siyan Qin, Xiang Zhang +3 more

In the problem of conditional disclosure of secrets (CDS), two parties, Alice and Bob, each has an input and shares a common secret. Their goal is to reveal the secret to a third party, Carol, as efficiently as possible, only if the inputs of Alice and Bob satisfy a certain functional relation$f$. To prevent leakage of the secret to Carol when the input combination is unqualified, both Alice and Bob introduce noise. This work aims to determine the noise capacity, defined as the maximum number of secret bits that can be securely revealed to Carol, normalized by the total number of independent noise bits held jointly by Alice and Bob. Our contributions are twofold. First, we establish the necessary and sufficient conditions under which the CDS noise capacity attains its maximum value of 1. Second, in addition to the above best-case scenarios, we derive an upper bound on the linear noise capacity for any CDS instance. In particular, this upper bound is equal to$(\rho-1)(d-1) /(\rho d-1)$, where$\rho$is the covering parameter of the graph representation of$f$, and$d$is the number of unqualified edges in residing unqualified path.

IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•0 citations

Conditional disclosure of secrets with quantum resources

Vahid R. Asadi, Kohdai Kuroiwa, Debbie Leung +3 more

The conditional disclosure of secrets (CDS) primitive is among the simplest cryptographic settings in which to study the relationship between communication, randomness, and security. CDS involves two parties, Alice and Bob, who do not communicate but who wish to reveal a secret z to a referee if and only if a Boolean function f has f ( x , y ) = 1 . Alice knows x , z , Bob knows y , and the referee knows x , y . Recently, a quantum analogue of this primitive called CDQS was defined and related to f -routing, a task studied in the context of quantum position-verification. CDQS has the same inputs, outputs, and communication pattern as CDS but allows the use of shared entanglement and quantum messages. We initiate the systematic study of CDQS, with the aim of better understanding the relationship between privacy and quantum resources in the information theoretic setting. We begin by looking for quantum analogues of results already established in the classical CDS literature. Doing so we establish a number of basic properties of CDQS, including lower bounds on entanglement and communication stated in terms of measures of communication complexity. Because of the close relationship to the f -routing position-verification scheme, our results have relevance to the security of these schemes.

arXiv:2404.14491•Quantum•Oct 16, 2025•8 citations

Laconic Conditional Disclosure of Secrets and Applications

Nico Döttling, Sanjam Garg, Vipul Goyal +1 more

In a Conditional Disclosure of Secrets (CDS) a verifier V wants to reveal a message m to a prover P conditioned on the fact that x is an accepting instance of some NP-language L. An honest prover (holding the corresponding witness w) always obtains the message m at the end of the interaction. On the other hand, if x ∉ L we require that no PPT P* can learn the message m. We introduce laconic CDS, a two round CDS protocol with optimal computational cost for the verifier V and optimal communication cost. More specifically, the verifier's computation and overall communication grows with poly(|x|; λ; log(T)), where λ is the security parameter and T is the verification time for checking that x ϵ L (given w). We obtain constructions of laconic CDS under standard assumptions, such as CDH or LWE. Laconic CDS serves as a powerful tool for maliciousifying semi-honest protocols while preserving their computational and communication complexities. To substantiate this claim, we consider the setting of non-interactive secure computation: Alice wants to publish a short digest corresponding to a private large input x on her web page such that (possibly many) Bob, with a private input y, can send a short message to Alice allowing her to learn C(x; y) (where C is a public circuit). The protocol must be reusable in the sense that Bob can engage in arbitrarily many executions on the same digest. In this context we obtain the following new implications. 1) UC Secure Bob-optimized 2PC: We obtain a UC secure protocol where Bob's computational cost and the communication cost of the protocol grows with poly(|x|; |y|; λ; d), where d is the depth of the computed circuit C. 2) Malicious Laconic Function Evaluation: Next, we move on to the setting where Alice's input x is large. For this case, UC secure protocols must have communication cost growing with |x|. Thus, with the goal of achieving better efficiency, we consider a weaker notion of malicious security. For this setting, we obtain a protocol for which Bob's computational cost and the communication cost of the protocol grows with poly(|y|; λ; d), where d is the depth of the computed circuit C.

Annual Symposium on Foundations of Computer Science•Nov 1, 2019•16 citations

Additive Conditional Disclosure of Secrets And Applications

Sven Laur, Helger Lipmaa

During a conditional disclosure of secrets (CDS) protocol, Alice obtains a secret, held by Bob, if and only if her inputs to the protocol were "valid". As an output masking technique, CDS protocol can be used as a subroutine in other protocols to guarantee either Bob-privacy or correctness against a malicious Alice. Using a simple seeded randomness extractor, we extend the Aiello-Ishai-Reingold CDS protocol to work over additively homomorphic public-key cryptosystems. Based on this, we construct several new two-message protocols like an oblivious transfer protocol with log-squared communication and a millionaire's protocol with logarithmic communication.

•Jan 1, 2005•12 citations

New lower bounds for CDS and $f$-routing

Atsuya Hasegawa, Ranitha Mataraarachchi

Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and other areas. A central special case is $f$-routing, motivated in part by quantum position verification. Proving lower bounds on its entanglement cost in the fully robust setting has been a major open problem in NLQC. Motivated by this problem, we establish two related lower bounds. First, we study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and $f$-routing established by Allerstorfer et al. (Quantum 2024) makes understanding the randomness complexity of robust CDS a natural step toward lower bounds for the fully robust routing problem. We show that the shared-randomness cost of robust CDS is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. Our lower bound is tight for the equality function. Second, we consider one-sided-perfect $f$-routing, in which the protocol is exact on one input class and has constant error on the other. By exploiting the positivity of the low-rank matrix in the method of Asadi, Culf, and May (ITCS 2025), we derive a lower bound on the entanglement cost in terms of sign rank. In particular, this yields a linear lower bound on the entanglement cost of routing for the inner-product function in both one-sided-perfect settings, matching the known upper bound.

quant-pharXiv:2609.24291•Sep 22, 2026•0 citations
In the conditional disclosure of secrets (CDS) problem, Alice and Bob (each holds an input and a common secret) wish to disclose, as efficiently as possible, the secret to Carol if and only if their inputs satisfy some function. The capacity of CDS is the maximum number of bits of the secret that can be securely disclosed per bit of total communication. We characterize the necessary and sufficient condition for the extreme case where the capacity of CDS is the highest and is equal to 1/2.
In the conditional disclosure of secrets (CDS) problem, Alice and Bob (each holds an input and a common secret) wish to disclose, as efficiently as possible, the secret to Carol if and only if their inputs satisfy some function. The capacity of CDS is the maximum number of bits of the secret that can be securely disclosed per bit of total communication. We characterize the necessary and sufficient condition for the extreme case where the capacity of CDS is the highest and is equal to1/21/21/2. For the simplest instance where the capacity is smaller than1/21/21/2, we show that the linear capacity is2/52/52/5.
In the problem of conditional disclosure of secrets (CDS), two parties, Alice and Bob, each has an input and shares a common secret. Their goal is to reveal the secret to a third party, Carol, as efficiently as possible, only if the inputs of Alice and Bob satisfy a certain functional relationfff. To prevent leakage of the secret to Carol when the input combination is unqualified, both Alice and Bob introduce noise. This work aims to determine the noise capacity, defined as the maximum number of secret bits that can be securely revealed to Carol, normalized by the total number of independent noise bits held jointly by Alice and Bob. Our contributions are twofold. First, we establish the necessary and sufficient conditions under which the CDS noise capacity attains its maximum value of 1. Second, in addition to the above best-case scenarios, we derive an upper bound on the linear noise capacity for any CDS instance. In particular, this upper bound is equal to(ρ−1)(d−1)/(ρd−1)(\rho-1)(d-1) /(\rho d-1)(ρ−1)(d−1)/(ρd−1), whereρ\rhoρis the covering parameter of the graph representation offff, anddddis the number of unqualified edges in residing unqualified path.
The conditional disclosure of secrets (CDS) primitive is among the simplest cryptographic settings in which to study the relationship between communication, randomness, and security. CDS involves two parties, Alice and Bob, who do not communicate but who wish to reveal a secret z to a referee if and only if a Boolean function f has f ( x , y ) = 1 . Alice knows x , z , Bob knows y , and the referee knows x , y . Recently, a quantum analogue of this primitive called CDQS was defined and related to f -routing, a task studied in the context of quantum position-verification. CDQS has the same inputs, outputs, and communication pattern as CDS but allows the use of shared entanglement and quantum messages. We initiate the systematic study of CDQS, with the aim of better understanding the relationship between privacy and quantum resources in the information theoretic setting. We begin by looking for quantum analogues of results already established in the classical CDS literature. Doing so we establish a number of basic properties of CDQS, including lower bounds on entanglement and communication stated in terms of measures of communication complexity. Because of the close relationship to the f -routing position-verification scheme, our results have relevance to the security of these schemes.
In a Conditional Disclosure of Secrets (CDS) a verifier V wants to reveal a message m to a prover P conditioned on the fact that x is an accepting instance of some NP-language L. An honest prover (holding the corresponding witness w) always obtains the message m at the end of the interaction. On the other hand, if x ∉ L we require that no PPT P* can learn the message m. We introduce laconic CDS, a two round CDS protocol with optimal computational cost for the verifier V and optimal communication cost. More specifically, the verifier's computation and overall communication grows with poly(|x|; λ; log(T)), where λ is the security parameter and T is the verification time for checking that x ϵ L (given w). We obtain constructions of laconic CDS under standard assumptions, such as CDH or LWE. Laconic CDS serves as a powerful tool for maliciousifying semi-honest protocols while preserving their computational and communication complexities. To substantiate this claim, we consider the setting of non-interactive secure computation: Alice wants to publish a short digest corresponding to a private large input x on her web page such that (possibly many) Bob, with a private input y, can send a short message to Alice allowing her to learn C(x; y) (where C is a public circuit). The protocol must be reusable in the sense that Bob can engage in arbitrarily many executions on the same digest. In this context we obtain the following new implications. 1) UC Secure Bob-optimized 2PC: We obtain a UC secure protocol where Bob's computational cost and the communication cost of the protocol grows with poly(|x|; |y|; λ; d), where d is the depth of the computed circuit C. 2) Malicious Laconic Function Evaluation: Next, we move on to the setting where Alice's input x is large. For this case, UC secure protocols must have communication cost growing with |x|. Thus, with the goal of achieving better efficiency, we consider a weaker notion of malicious security. For this setting, we obtain a protocol for which Bob's computational cost and the communication cost of the protocol grows with poly(|y|; λ; d), where d is the depth of the computed circuit C.
During a conditional disclosure of secrets (CDS) protocol, Alice obtains a secret, held by Bob, if and only if her inputs to the protocol were "valid". As an output masking technique, CDS protocol can be used as a subroutine in other protocols to guarantee either Bob-privacy or correctness against a malicious Alice. Using a simple seeded randomness extractor, we extend the Aiello-Ishai-Reingold CDS protocol to work over additively homomorphic public-key cryptosystems. Based on this, we construct several new two-message protocols like an oblivious transfer protocol with log-squared communication and a millionaire's protocol with logarithmic communication.
New lower bounds for CDS and fff-routing
Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and other areas. A central special case is fff-routing, motivated in part by quantum position verification. Proving lower bounds on its entanglement cost in the fully robust setting has been a major open problem in NLQC. Motivated by this problem, we establish two related lower bounds. First, we study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and fff-routing established by Allerstorfer et al. (Quantum 2024) makes understanding the randomness complexity of robust CDS a natural step toward lower bounds for the fully robust routing problem. We show that the shared-randomness cost of robust CDS is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. Our lower bound is tight for the equality function. Second, we consider one-sided-perfect fff-routing, in which the protocol is exact on one input class and has constant error on the other. By exploiting the positivity of the low-rank matrix in the method of Asadi, Culf, and May (ITCS 2025), we derive a lower bound on the entanglement cost in terms of sign rank. In particular, this yields a linear lower bound on the entanglement cost of routing for the inner-product function in both one-sided-perfect settings, matching the known upper bound.