# Complete Classification of Bilinear Hard-Core Functions

## Thomas Holenstein and Ueli Maurer and Johan Sjödin

```
```Let $f:\{0,1\}^n\rightarrow\{0,1\}^{l}$ be a one-way function. A
function $h: \{0,1\}^n\rightarrow\n\{0,1\}^m$ is called a hard-core
function for $f$ if, when given $f(x)$ for a (secret) $x$ drawn
uniformly from $\{0,1\}^n$, it is computationally infeasible to
distinguish $h(x)$ from a uniformly random $m$-bit string. A
(randomized) function $h: \{0,1\}^n\times\n\{0,1\}^k
\rightarrow\{0,1\}^m$ is a *general* hard-core function if it
is hard-core for every one-way function
$f:\{0,1\}^n\rightarrow\{0,1\}^{l}$, where the second input to $h$
is a $k$-bit uniform random string $r$. Hard-core functions are a
crucial tool in cryptography, in particular for the construction of
pseudo-random generators and pseudo-random functions from any
one-way function.
The first general hard-core predicate, proposed by Goldreich and
Levin, and several subsequently proposed hard-core functions, are
bilinear functions in the two arguments $x$ and $r$. In this paper
we introduce a parameter of bilinear functions $h:
\{0,1\}^n\times\{0,1\}^k \rightarrow\n\{0,1\}^m$, called exponential
rank loss, and prove that it characterizes exactly whether or not
$h$ is a general hard-core function. The security proofs for the
previously proposed bilinear hard-core functions follow as simple
consequences. Our results are obtained by extending the class of
list-decodable codes and by generalizing Hast's list-decoding
algorithm from the Reed-Muller code to general codes.