2004 | OriginalPaper | Buchkapitel
Complete Classification of Bilinear Hard-Core Functions
verfasst von : Thomas Holenstein, Ueli Maurer, Johan Sjödin
Erschienen in: Advances in Cryptology – CRYPTO 2004
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let f:{0,1}n→{0,1}l be a one-way function. A function h: {0,1}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× {0,1}k →{0,1}m is a general hard-core function if it is hard-core for every one-way function f:{0,1}n→{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×{0,1}k → {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.