## 摘要

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 H_{I} ⊆ f ^{-1}(I) with density γ/(_{L+1}^{V} such that any circuit of some size s′ can only compute f correctly on at most 1+ε/L+1 fraction of inputs in H_{I}. 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月 2011 → 25 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

Conference | 18th International Symposium on Fundamentals of Computation Theory, FCT 2011 |
---|---|

國家/地區 | Norway |

城市 | Oslo |

期間 | 22/08/11 → 25/08/11 |