文章基本信息

标题：A remark on one-wayness versus pseudorandomness
本地全文：下载
作者：Periklis Papakonstantinou ; Guang Yang
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Every pseudorandom generator is in particular a one-way function. If we only consider part of the output of the pseudorandom generator is this still one-way? Here is a general setting formalizing this question. Suppose G:01n01(n) is a pseudorandom generator with stretch (n)n. Let MR01m(n)(n) be a linear operator computable in polynomial time given randomness R. Consider the function F(xR)=MRG(x)R We obtain the following results. - There exists a pseudorandom generator such that for every constant 1 and for an arbitrary polynomial time computable MR01(1−)n(n) , F is not one-way. Furthermore, our construction yields a tradeoff between the hardness of the pseudorandom generator and the output length m(n). For example, given =(n) and a 2cn-hard pseudorandom generator we construct a 2cn-hard pseudorandom generator such that F is not one-way, where m(n)n and +=1−o(1) . - We show this tradeoff to be tight for 1-1 pseudorandom generators. That is, for any G which is a 2n-hard 1-1 pseudorandom generator, if +=1+ then there is MR01n(n) such that F is a (2n)-hard one-way function.
关键词：one-way function, pseudorandom generator