布尔分层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≠?.

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≠φ.