• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Cryptology >Placing Conditional Disclosure of Secrets in the Communication Complexity Universe
【24h】

Placing Conditional Disclosure of Secrets in the Communication Complexity Universe

机译：在通信复杂性宇宙中放置条件披露秘密

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the conditional disclosure of secrets (CDS) problem (Gertner et al. in J Comput Syst Sci, 2000) Alice and Bob, who hold n-bit inputs x and y respectively, wish to release a common secret z to Carol, who knows both x and y, if and only if the input (x, y) satisfies some predefined predicate f. Alice and Bob are allowed to send a single message to Carol which may depend on their inputs and some shared randomness, and the goal is to minimize the communication complexity while providing information-theoretic security. Despite the growing interest in this model, very few lower-bounds are known. In this paper, we relate the CDS complexity of a predicate f to its communication complexity under various communication games. For several basic predicates our results yield tight, or almost tight, lower-bounds of Omega(n) or Omega(n(1-epsilon)), providing an exponential improvement over previous logarithmic lower-bounds. We also define new communication complexity classes that correspond to different variants of the CDS model and study the relations between them and their complements. Notably, we show that allowing for imperfect correctness can significantly reduce communication-a seemingly new phenomenon in the context of information-theoretic cryptography. Finally, our results show that proving explicit super-logarithmic lower-bounds for imperfect CDS protocols is a necessary step towards proving explicit lower-bounds against the communication complexity class AM(cc), or even AM(cc)boolean AND co-AM(cc)-a well known open problem in the theory of communication complexity. Thus imperfect CDS forms a new minimal class which is placed just beyond the boundaries of the "civilized" part of the communication complexity world for which explicit lower-bounds are known.
机译：在秘密披露（CDS）问题的条件披露中（Gertner等人。在J计算SYST SCI，2000）Alice和Bob，谁分别持有n位输入x和y，希望将公共秘密z释放到Carol，谁知道x和y，如果且仅当输入（x，y）满足一些预定义的谓词f。 Alice和Bob被允许向Carol发送单个信息，这可能取决于其输入和一些共享的随机性，并且目标是在提供信息理论上的同时最小化通信复杂性。尽管对该模型的兴趣日益越来越感兴趣，但很少有较少的较低限制。在本文中，我们将谓词F的CDS复杂性与其在各种通信游戏下的通信复杂性相关联。对于几个基本谓词，我们的结果屈服，或几乎紧密，ω或ω（n（1-epsilon））的较差，较低，提供了对先前对数下限的指数改进。我们还定义了与CDS模型的不同变体相对应的新通信复杂性等级，并研究了它们之间的关系及其补充。值得注意的是，我们表明，允许不完美的正确性可以显着降低通信 - 在信息理论密码学的背景下看似新的现象。最后，我们的结果表明，对于不完美CDS协议来说，证明了显式超对数较低限制是针对通信复杂性AM（CC），甚至是（CC）布尔和CO-AM（ CC） - 在通信复杂性理论中众所周知的开放问题。因此，不完美的CD构成了一种新的最小类，其被放置在通信复杂性世界的“文明”部分的界限之外，这是已知的明确下限。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号