Bit Security as?Computational Cost for?Winning Games with?High Probability
Bit Security as?Computational Cost for?Winning Games with?High Probability
复制标题
比特安全作为高概率获胜游戏的计算成本
DOI：
10.1007/978-3-030-92078-4_6
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Yasunaga Kenji
中科院分区：
文献类型：
--
作者：
Watanabe Shun;Yasunaga Kenji
我们引入了一种新颖的框架来量化安全游戏的比特安全性。我们的概念是用操作意义来定义的，即有点安全的游戏需要高概率赢得游戏的总计算成本，例如 0.99。我们为搜索型和决策型游戏定义了位安全性。由于我们认为这两类游戏在结构上应该是不同的，因此我们会区别对待它们，但使用统一的框架定义比特安全性，以保证相同的操作解释。我们的比特安全概念的关键新颖之处在于采用两种类型的对手：内部对手和外部对手。当内部对手玩“通常的”安全游戏时，外部对手多次调用内部对手以放大安全游戏的获胜概率。我们从我们的框架中发现，决策博弈的比特安全性可以通过称为内部对手 1/2 阶 Rényi 散度的信息度量来表征。传统的“优势”定义为赢得游戏的概率，表征了我们对于搜索类型游戏的比特安全性。我们在框架中提出了一些安全性降低措施，以证明我们的位安全概念的合理性。我们的许多结果在数量上与 Micciincio 和 Walter 在 2018 年提出的比特安全概念的结果相匹配。从这个意义上说，我们的比特安全通过添加操作意义来强化之前的比特安全概念。与他们的工作的不同之处在于，在我们的框架中，戈德赖希-莱文定理仅针对以平衡方式输出二进制值的“平衡”对手给出最佳约简。
We introduce a novel framework for quantifying the bit security of security games. Our notion is defined with an operational meaning that a-bit secure game requires a total computational cost offor winning the game with high probability, e.g., 0.99. We define the bit security both for search-type and decision-type games. Since we identify that these two types of games should be structurally different, we treat them differently but define the bit security using the unified framework to guarantee the same operational interpretation. The key novelty of our notion of bit security is to employ two types of adversaries: inner adversary and outer adversary. While the inner adversary plays a “usual” security game, the outer adversary invokes the inner adversary many times to amplify the winning probability for the security game. We find from our framework that the bit security for decision games can be characterized by the information measure called theRényi divergenceof order 1/2 of the inner adversary. The conventional “advantage,” defined as the probability of winning the game, characterizes our bit security for search-type games. We present several security reductions in our framework for justifying our notion of bit security. Many of our results quantitatively match the results for the bit security notion proposed by Micciancio and Walter in 2018. In this sense, our bit security strengthens the previous notion of bit security by adding an operational meaning. A difference from their work is that, in our framework, the Goldreich-Levin theorem gives an optimal reduction only for “balanced” adversaries who output binary values in a balanced manner.