Complete Classification of Bilinear Hard-Core Functions

Thomas Holenstein, Ueli Maurer, and Johan Sjödin

Advances in Cryptology — CRYPTO 2004, Lecture Notes in Computer Science, Springer-Verlag, vol. 3152, pp. 73–91, Aug 2004.

Let $f : {0, 1}^{n} \to {0, 1}^{l}$ be a one-way function. A function $h : {0, 1}^{n} \to {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} \to {0, 1}^{m}$ is a general hard-core function if it is hard-core for every one-way function $f : {0, 1}^{n} \to {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} \to {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},
}