Deja Q: Using Dual Systems to Revisit q-Type Assumptions
Deja Q: Using Dual Systems to Revisit q-Type Assumptions
复制标题
DOI：
10.1007/978-3-642-55220-5_34
复制
发表时间：
2014-05
期刊：
影响因子：
--
通讯作者：
Melissa Chase;S. Meiklejohn
中科院分区：
文献类型：
--
作者：
Melissa Chase;S. Meiklejohn
经过十多年的使用，双线性群已经在密码学经典中建立了自己的地位，可以构建许多高级密码学原语。不幸的是，这种功能的爆炸伴随着用于证明安全性的假设的复杂性的类似增长。这些假设中的许多已经被收集在“超级假设”的保护伞下，然而这些假设中的某些类别-即q型假设-比它们的静态对应物更强大，需要更大的参数大小。在本文中，我们表明，在某些双线性群，许多类的q-型假设实际上隐含的子群隐藏（一个完善的，静态的假设）。我们在这奋进的主要工具是双系统技术，这是沃茨在2009年推出的。作为一个案例研究，我们首先表明，在复合阶组，我们可以证明的安全性的Dodis-Yampolskiy的PRF仅基于子群隐藏，并允许一个域的任意大小（原来的证明只允许一个几何尺寸的域）。然后，我们把注意力转向类的q型假设，并表明它们是隐含的，当实例化在适当的群体，仅由子群隐藏。这些类是相当一般的，包括假设，如q-SDH。具体地说，我们的结果意味着每个建筑都依赖于这样的安全假设（例如，Boneh-Boyen签名）在适当的复合阶双线性群中实例化时，可以在子群隐藏下证明是安全的。
After more than a decade of usage, bilinear groups have established their place in the cryptographic canon by enabling the construction of many advanced cryptographic primitives. Unfortunately, this explosion in functionality has been accompanied by an analogous growth in the complexity of the assumptions used to prove security. Many of these assumptions have been gathered under the umbrella of the “uber-assumption,” yet certain classes of these assumptions—namely,q-typeassumptions—are stronger and require larger parameter sizes than their static counterparts. In this paper, we show that in certain bilinear groups, many classes ofq-type assumptions are in fact implied by subgroup hiding (a well-established, static assumption). Our main tool in this endeavor is thedual-systemtechnique, as introduced by Waters in 2009. As a case study, we first show that in composite-order groups, we can prove the security of the Dodis-Yampolskiy PRF based solely on subgroup hiding and allow for a domain of arbitrary size (the original proof only allowed a logarithmically-sized domain). We then turn our attention to classes ofq-type assumptions and show that they are implied—when instantiated in appropriate groups—solely by subgroup hiding. These classes are quite general and include assumptions such asq-SDH. Concretely, our result implies that every construction relying on such assumptions for security (e.g., Boneh-Boyen signatures) can, when instantiated in appropriate composite-order bilinear groups, be proved secure under subgroup hiding instead.