• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Theory of cryptography >An Optimally Fair Coin Toss
【24h】

An Optimally Fair Coin Toss

机译：理想的抛硬币

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

摘要

We address one of the foundational problems in cryptography: the bias of coin-flipping protocols. Coin-flipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot significantly bias the output of the honest party. A classical result by Cleve [STOC '86] showed that for any two-party r-round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by Ω(1/r). However, the best previously known protocol only guarantees O(1/r~(1/2)) bias, and the question of whether Cleve's bound is tight has remained open for more than twenty years.rnIn this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve's lower bound is tight: we construct an r-round protocol with bias O(1/r).
机译：我们解决了密码学中的一个基本问题：硬币翻转协议的偏见。抛硬币协议允许互不信任的各方生成公共的无偏随机位，从而确保即使其中一方是恶意的，也不会显着偏重诚实方的输出。 Cleve [STOC '86]的经典结果表明，对于任何两方r轮硬币翻转协议，都存在一个有效的对手，该对手可以使诚实方的输出偏差Ω（1 / r）。然而，最好的已知协议只能保证O（1 / r〜（1/2））的偏倚，而且Cleve的界是否紧的问题已经存在了20多年了。在轮回复杂度和两方抛硬币协议的偏见之间切换。在标准假设下（存在遗忘转移），我们证明克利夫的下界是紧的：我们构造了一个偏差为O（1 / r）的r轮协议。

著录项

  • 来源
    《Theory of cryptography》|2009年|1-18|共18页
  • 会议地点 San Francisco CA(US);San Francisco CA(US)
  • 作者

    Tal Moran; Moni Naor; Gil Segev;

  • 作者单位

    Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel;

    Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel;

    Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 一般性问题;
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号