Computational randomness from generalized hardcore sets

Chia Jung Lee*, Chi Jen Lu, Shi-Chun Tsai

*此作品的通信作者

研究成果: Conference contribution同行評審

1 引文 斯高帕斯(Scopus)

摘要

The seminal hardcore lemma of Impagliazzo states that for any mildly-hard Boolean function f, there is a subset of input, called the hardcore set, on which the function is extremely hard, almost as hard as a random Boolean function. This implies that the output distribution of f given a random input looks like a distribution with some statistical randomness. Can we have something similar for hard functions with several output bits? Can we say that the output distribution of such a general function given a random input looks like a distribution containing several bits of randomness? If so, one can simply apply any statistical extractor to extract computational randomness from the output of f. However, the conventional wisdom tells us to apply extractors with some additional reconstruction property, instead of just any extractor. Does this mean that there is no analogous hardcore lemma for general functions? We show that a general hard function does indeed have some kind of hardcore set, but it comes with the price of a security loss which is proportional to the number of output values. More precisely, consider a hard function f : {0, 1}n → [V] = {1,...,V} such that any circuit of size s can only compute f correctly on at most 1/L(1 - γ) fraction of inputs, for some L ∈ [1,V - 1] and γ ∈ (0,1). Then we show that for some I ⊆ [V] with |I| = L + 1, there exists a hardcore set HI ⊆ f -1(I) with density γ/(L+1V such that any circuit of some size s′ can only compute f correctly on at most 1+ε/L+1 fraction of inputs in HI. Here, s′ is smaller than s by some poly(V,1/ε,log(1/γ)) factor, which results in a security loss of such a factor. We show that it is basically impossible to guarantee a much larger hardcore set or a much smaller security loss. Finally, we show how our hardcore lemma can be used for extracting computational randomness from general hard functions.

原文English
主出版物標題Fundamentals of Computation Theory - 18th International Symposium, FCT 2011, Proceedings
頁面78-89
頁數12
DOIs
出版狀態Published - 2011
事件18th International Symposium on Fundamentals of Computation Theory, FCT 2011 - Oslo, Norway
持續時間: 22 8月 201125 8月 2011

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
6914 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Conference

Conference18th International Symposium on Fundamentals of Computation Theory, FCT 2011
國家/地區Norway
城市Oslo
期間22/08/1125/08/11

指紋

深入研究「Computational randomness from generalized hardcore sets」主題。共同形成了獨特的指紋。

引用此