布尔分层one-way函数的存在性

Existence of One-Way Function in Boolean Circuit

摘要: one-way函数是否存在迄今仍为一个开问题.文献5提出了分层one-way函数的概念.本文在布尔线路中讨论了分层one-way函数的存在性并得到结果:（1）给定k≥j>0,若存在j-honest的2k-one-way函数族f_i,则UPSIZE^2j-PSIZE^k-j≠?.（2）给定k≥j>0,若UPSIZE^j∩CO-UPSIZE^j-PSIZE^k≠?,则存在j-honest的k-one-way函数族f_i,且?rang（f_i）=∑^*.（3）给定j>0,j-honest的ω-one-way函数族f_i存在当且仅当UPSIZE^2j-PSIZE≠?.

Abstract: The existence of one-way function is still an open problem. 5 submits the notion of k-one-way function. In this paper we discuss the existence of k-one-way function in Boolean circuit. We obtain the following results: （1） Given k≥j>0, if there is a family of functions f_i, which is j-honest and 2k-one-way, then UPSIZE^2j-PSIZE^k-j≠φ; （2） Given k≥j>0, if UPSIZE^∩co-UPSIZE^j-PSIZE^k≠φ, then there exists a family of functions f_i such that f_i is j-honest, k-one-way and?rang （f_i）=∑^*. （3） Given j>0, there exists a family of functions f_i, which is j-honest and ω-one-way iff UPSIZE^2j-PSIZE≠φ.