Cryptology ePrint Archive: Report 2015/665

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

Romain Gay and Iordanis Kerenidis and Hoeteck Wee

Abstract: 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.

Category / Keywords: communication complexity, conditional disclosure of secrets, attribute-based encryption

Original Publication (with major differences): IACR-CRYPTO-2015

Date: received 2 Jul 2015

Contact author: rgay at di ens fr

Available format(s): PDF | BibTeX Citation

Version: 20150705:175957 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]