Complete Classification of Bilinear Hard-Core Functions
Thomas Holenstein, 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\{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\{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\{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.
BibTeX Citation
@inproceedings{HoMaSj04,
author = {Thomas Holenstein and Ueli Maurer and Johan Sjödin},
title = {Complete Classification of Bilinear Hard-Core Functions},
editor = {Matthew Franklin},
booktitle = {Advances in Cryptology --- CRYPTO 2004},
pages = 73--91,
series = {Lecture Notes in Computer Science},
volume = 3152,
year = 2004,
month = 8,
publisher = {Springer-Verlag},
}