The Goldreich-Levin Theorem

Objective of the theorem: Find a hardcore predicate for a one-way function.

A hardcore predicate is a concept in cryptography that is related to the security of one-way functions. One-way functions are functions that are easy to compute in one direction but computationally difficult to invert. A hardcore predicate is a function that is hard to predict even when the value of the one-way function is known.

Note: In computational complexity theory, problems are classified into various complexity classes based on how efficiently they can be solved by algorithms. The polynomial hierarchy is a structure that extends the classes P and NP to higher levels of complexity.

The polynomial hierarchy is organized into levels: Σ0P\Sigma_0^P, Π0P\Pi_0^P, Σ1P\Sigma_1^P, Π1P\Pi_1^P, Σ2P\Sigma_2^P, Π2P\Pi_2^P, and so on. Each level contains problems that are "harder" to solve than the levels below it. The third level of the polynomial hierarchy is represented as Σ3P\Sigma_3^P and Π3P\Pi_3^P.

The Goldreich-Levin Theorem: Let ff be a function from {0,1}n\{0, 1\}^n to {0,1}\{0, 1\} such that there exists a nondeterministic finite automaton (NFA) AA with nn input bits and s(n)s(n) states that accepts xx with probability f(x)f(x), where s(n)s(n) is a polynomial in nn. Then, unless the polynomial hierarchy collapses to its third level, there is no efficient (i.e., polynomial-time) algorithm that approximates f(x)f(x) significantly better than the trivial algorithm.

[under construction]

Note: I've been away for a while, very happy to announce thoughtForest (opens in a new tab) is now live!


Lecture 6: The Goldreich Levin Theorum by Pandey (opens in a new tab)