Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings
Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings
复制标题
DOI：
10.1007/11535218
复制
发表时间：
2005-08
影响因子：
8.6
通讯作者：
V. Shoup
中科院分区：
文献类型：
--
作者：
V. Shoup
我们研究两个函数的顺序或并行组合（每个函数都无法通过非自适应区分器与随机函数区分）是否对自适应区分器是安全的问题。 F和G的顺序组合是函数G(F())，并行组合是FG，其中⋆是某个群运算。事实证明，组合确实在信息论环境中提供了自适应安全性，但不幸的是，证明并没有转化为更有趣的计算情况。在这项工作中，我们表明，在计算设置中，组合并不意味着自适应安全：如果存在决策 Diffie-Hellman 假设成立的素数阶循环群，则存在函数 F 和 G，它们无法被非自适应多项式时间限制的对手区分，但其并行组合可以完全被打破（即我们恢复密钥）仅用三个自适应查询。我们对于顺序组合给出了类似的结果。有趣的是，我们需要来自非对称（又名公钥）世界的标准假设来证明对称（又名私钥）系统的负面结果。
We study the question whether the sequential or parallel composition of two functions, each indistinguishable from a random function by non-adaptive distinguishers is secure against adaptive distinguishers. The sequential composition ofFandGis the functionG(F()), the parallel composition isFGwhere ⋆ is some group operation. It has been shown that composition indeed gives adaptive security in the information theoretic setting, but unfortunately the proof does not translate into the more interesting computational case.In this work we show that in the computational setting composition does not imply adaptive security: If there is a prime order cyclic group where the decisional Diffie-Hellman assumption holds, then there are functionsFandGwhich are indistinguishable by non-adaptive polynomially time-bounded adversaries, but whose parallel composition can be completely broken (i.e. we recover the key) with only three adaptive queries. We give a similar result for sequential composition. Interestingly, we need a standard assumption from the asymmetric (aka. public-key) world to prove a negative result for symmetric (aka. private-key) systems.