【24h】

On Continual Leakage of Discrete Log Representations

机译:关于离散日志表示的连续泄漏

获取原文

摘要

Let G be a group of prime order q, and let g_1,... ,g_n be random elements of G. We say that a vector x = (x_1,...,x_n) ∈ Z_q~n is a discrete log representation of some some element y € G (with respect to g_1,..., g_n) if g_1~(x1) ... g_n~(xn) = y· Any element y has many discrete log representations, forming an affine subspace of Z_q~n. We show that these representations have a nice continuous leakage-resilience property as follows. Assume some attacker A(g_1,..., g_n, y) can repeatedly learn L bits of information on arbitrarily many random representations of y. That is, A adaptively chooses polynomially many leakage functions f_i : Z_q~n → {0,1}~L, and learns the value f_i(x_i), where X_i is a fresh and random discrete log representation of y. A wins the game if it eventually outputs a valid discrete log representation x* of y. We show that if the discrete log assumption holds in G, then no polynomially bounded A can win this game with non-negligible probability, as long as the leakage on each representation is bounded by L ≈ (n - 2) log q = (1 - 2) · |x|. As direct extensions of this property, we design very simple continuous leakage-resilient (CLR) one-way function (OWF) and public-key encryption (PKE) schemes in the so called "invisible key update" model introduced by Alwen et al. at CRYPTO'09. Our CLR-OWF is based on the standard Discrete Log assumption and our CLR-PKE is based on the standard Decisional Diffie-Hellman assumption. Prior to our work, such schemes could only be constructed in groups with a bilinear pairing. As another surprising application, we show how to design the first leakage-resilient traitor tracing scheme, where no attacker, getting the secret keys of a small subset of decoders (called "traitors") and bounded leakage on the secret keys of all other decoders, can create a valid decryption key which will not be traced back to at least one of the traitors.
机译:令G为素数阶q的一组,令g_1,...,g_n为G的随机元素。我们说向量x =(x_1,...,x_n)∈Z_q〜n是离散对数表示如果g_1〜(x1)... g_n〜(xn)= y·,则某些元素y€G的值(相对于g_1,...,g_n)•任何元素y都有许多离散的对数表示,形成了一个仿射子空间Z_q〜n。我们表明,这些表示具有良好的连续防漏弹性,如下所示。假设某些攻击者A(g_1,...,g_n,y)可以在y的许多随机表示上重复学习L位信息。即,A自适应地选择多项式许多泄漏函数f_i:Z_q〜n→{0,1}〜L,并学习值f_i(x_i),其中X_i是y的新鲜随机离散对数表示。如果A最终输出有效的y的离散对数表示x *,则它会赢得比赛。我们证明,如果离散对数假设在G中成立,那么只要每个表示形式上的泄漏以L≈(n-2)log q =(1)为界,那么多项式边界A都不会以不可忽略的概率赢得这场比赛。 -2 / n)·| x |。作为此属性的直接扩展,我们在Alwen等人引入的所谓“隐形密钥更新”模型中设计了非常简单的连续防泄漏(CLR)单向函数(OWF)和公共密钥加密(PKE)方案。在CRYPTO'09。我们的CLR-OWF基于标准的离散对数假设,而我们的CLR-PKE基于标准的决策Diffie-Hellman假设。在我们进行工作之前,只能将具有双线性对的组构建为此类方案。作为另一个令人惊讶的应用程序,我们展示了如何设计第一个防泄漏弹性的叛逆者跟踪方案,该方案中没有攻击者,不会获得一小部分解码器的秘密密钥(称为“叛徒”),而在所有其他解码器的秘密密钥上有界泄漏可以创建一个有效的解密密钥,该密钥不会追溯到至少一个叛徒。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号