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

Additive Conditional Disclosure of Secrets And Applications

Sven Laur, Helger Lipmaa

Published Jan 1, 2005• 12 citations
OpenAlex

Abstract

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.

Related papers

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

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•14 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: 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

Comparing classical and quantum conditional disclosure of secrets

Uma Girish, Alex May, Leo Orshansky +1 more

The conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum computation and position-based cryptography, CDS with quantum resources has recently been considered. Here, we study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in information-theoretic cryptography. We establish the following results:1) We prove a Ω ( log ⁡ R 0 , A → B ( f ) + log ⁡ R 0 , B → A ( f ) ) lower bound on quantum CDS where R 0 , A → B ( f ) is the classical one-way communication complexity with perfect correctness.2) We prove a lower bound on quantum CDS in terms of two round, public coin, two-prover interactive proofs.3) For perfectly correct CDS, we give a separation for a promise version of the not-equals function, showing a quantum upper bound of O ( log ⁡ n ) and classical lower bound of Ω ( n ) .4) We give a logarithmic upper bound for quantum CDS on forrelation, while the best known classical algorithm is linear. We interpret this as preliminary evidence that classical and quantum CDS are separated even with correctness and security error allowed.We also give a separation for classical and quantum private simultaneous message passing for a partial function, improving on an earlier relational separation. Our results use novel combinations of techniques from non-local quantum computation and communication complexity.

arXiv:2505.02939•Quantum•Apr 1, 2026•2 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$. 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
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.
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.
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) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum computation and position-based cryptography, CDS with quantum resources has recently been considered. Here, we study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in information-theoretic cryptography. We establish the following results:1) We prove a Ω ( log ⁡ R 0 , A → B ( f ) + log ⁡ R 0 , B → A ( f ) ) lower bound on quantum CDS where R 0 , A → B ( f ) is the classical one-way communication complexity with perfect correctness.2) We prove a lower bound on quantum CDS in terms of two round, public coin, two-prover interactive proofs.3) For perfectly correct CDS, we give a separation for a promise version of the not-equals function, showing a quantum upper bound of O ( log ⁡ n ) and classical lower bound of Ω ( n ) .4) We give a logarithmic upper bound for quantum CDS on forrelation, while the best known classical algorithm is linear. We interpret this as preliminary evidence that classical and quantum CDS are separated even with correctness and security error allowed.We also give a separation for classical and quantum private simultaneous message passing for a partial function, improving on an earlier relational separation. Our results use novel combinations of techniques from non-local quantum computation and communication complexity.
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.