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)

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

Zhou Li, Siyan Qin, Xiang Zhang, Jihao Fan, Haiqiang Chen, Giuseppe Caire

Published Jun 22, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1109/isit63088.2025.11195296

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$.

IEEE Transactions on Communications•Apr 18, 2022•13 citations

Conditional Disclosure of Secrets: A Noise and Signal Alignment Approach

Zhou Li, Sun Hua

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•Feb 13, 2020•0 citations

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.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•7 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•2 citations

Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption.

Iordanis Kerenidis, Hoeteck Wee

We initiate a systematic treatment of the communication complexity of conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. We present a general upper bound and the first non-trivial lower bounds for conditional disclosure of secrets. Moreover, we achieve tight lower bounds for many interesting setting of parameters for CDS with linear reconstruction, the latter being a requirement in the application to attribute-based encryption. In particular, our lower bounds explain the trade-off between ciphertext and secret key sizes of several existing attribute-based encryption schemes based on the dual system methodology.

•Jan 1, 2015•0 citations

Linear Secret-Sharing Schemes for Forbidden Graph Access Structures

Amos Beimel, Oriol Farràs, Yuval Mintz +1 more

A secret-sharing scheme realizes the forbidden graph access structure determined by a graph$G=(V,E)$if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices in$E$(i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets (CDS) protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes, which are schemes in which the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and very dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. very dense) graph with$n$vertices and at most$n^{1+\beta }$edges (resp. at least$\binom {n}{2} - n^{1+\beta }$edges), for some$0 \leq \beta < 1$, we construct a linear secret-sharing scheme realizing its forbidden graph access structure with total share size$\tilde {O} (n^{1+\beta /2})$. Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share is$\tilde {O} (n^{1/4+\beta /4})$. We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share size$\Omega (n^{3/2})$; this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every$0 \leq \beta < 1$there exist a graph with at most$n^{1+\beta }$edges and a graph with at least$\binom {n}{2}-n^{1+\beta }$edges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures is$\Omega (n^{1+\beta /2})$. Finally, we show that for every$0 \leq \beta < 1$there exist a graph with at most$n^{1+\beta }$edges and a graph with at least$\binom {n}{2}-n^{1+\beta }$edges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures is$\Omega (n^{1/4+\beta /4})$. This shows that our constructions are optimal (up to poly-logarithmic factors).

IEEE Transactions on Information Theory•Dec 6, 2021•6 citations
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.
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 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.
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.
We initiate a systematic treatment of the communication complexity of conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. We present a general upper bound and the first non-trivial lower bounds for conditional disclosure of secrets. Moreover, we achieve tight lower bounds for many interesting setting of parameters for CDS with linear reconstruction, the latter being a requirement in the application to attribute-based encryption. In particular, our lower bounds explain the trade-off between ciphertext and secret key sizes of several existing attribute-based encryption schemes based on the dual system methodology.
A secret-sharing scheme realizes the forbidden graph access structure determined by a graphG=(V,E)G=(V,E)G=(V,E)if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices inEEE(i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets (CDS) protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes, which are schemes in which the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and very dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. very dense) graph withnnnvertices and at mostn1+βn^{1+\beta }n1+βedges (resp. at least(n2)−n1+β\binom {n}{2} - n^{1+\beta }(2n​)−n1+βedges), for some0≤β<10 \leq \beta < 10≤β<1, we construct a linear secret-sharing scheme realizing its forbidden graph access structure with total share sizeO~(n1+β/2)\tilde {O} (n^{1+\beta /2})O~(n1+β/2). Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share isO~(n1/4+β/4)\tilde {O} (n^{1/4+\beta /4})O~(n1/4+β/4). We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share sizeΩ(n3/2)\Omega (n^{3/2})Ω(n3/2); this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every0≤β<10 \leq \beta < 10≤β<1there exist a graph with at mostn1+βn^{1+\beta }n1+βedges and a graph with at least(n2)−n1+β\binom {n}{2}-n^{1+\beta }(2n​)−n1+βedges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures isΩ(n1+β/2)\Omega (n^{1+\beta /2})Ω(n1+β/2). Finally, we show that for every0≤β<10 \leq \beta < 10≤β<1there exist a graph with at mostn1+βn^{1+\beta }n1+βedges and a graph with at least(n2)−n1+β\binom {n}{2}-n^{1+\beta }(2n​)−n1+βedges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures isΩ(n1/4+β/4)\Omega (n^{1/4+\beta /4})Ω(n1/4+β/4). This shows that our constructions are optimal (up to poly-logarithmic factors).