Abstract
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.
Chapter PDF
Similar content being viewed by others
References
Alexi, W., Chor, B., Golreich, O., Schnorr, C.P.: RSA and Rabin functions: Certain parts are as hard as the whole. Siam Journal on Computation 17(2), 194–209 (1988)
Akavia, A., Goldwasser, S., Safra, S.: Proving hard-core predicates using list decoding. In: The 44th Annual Symposium on Foundations of Computer Science, pp. 146–157 (2003)
Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. Siam Journal on Computation 13(4), 850–864 (1984)
Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pp. 25–32 (1989)
Goldreich, O.: Basic Tools. In: Goldreich, O. (ed.) Foundations of Cryptography, 1st edn., Cambridge University Press, Cambridge (2001)
Goldreich, O., Rubinfeld, R., Sudan, M.: Learning polynomials with queries: The highly noisy case. Siam Journal on Discrete Mathematics 13(4), 535–570 (2000)
Gennaro, R., Trevisan, L.: Trevisan Lower bounds on the efficiency of generic cryptographic constructions. In: The 41st Annual Symposium on Foundations of Computer Science, pp. 305–313 (2000)
Hast, G.: Nearly one-sided tests and the Goldreich-Levin predicate. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 195–210. Springer, Heidelberg (2003)
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. Siam Journal on Computation 28(4), 1364–1396 (1999)
Levin, L.A.: One-way functions and pseudorandom generators. Combinatorica 7(4), 357–363 (1987)
Luby, M.: Pseudorandomness and Cryptographic Applications, 1st edn. Princeton University Press, Princeton (1996)
Näslund, M.: Universal hash functions & hard core bits. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 356–366. Springer, Heidelberg (1995)
Näslund, M.: All bits in ax + b mod p are hard. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 114–128. Springer, Heidelberg (1996)
Sudan, M., Trevisan, L., Pseudorandom, S.V.: generators without the XOR lemma. Journal of Computer and System Sciences 62(2), 236–266 (2001)
Sudan, M.: List decoding: Algorithms and applications. SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory 31(1), 16–27 (2000)
Yao, A.C.: Theory and applications of trapdoor functions (extended abstract). In: The 23rd Annual Symposium on Foundations of Computer Science, pp. 80–91 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Holenstein, T., Maurer, U., Sjödin, J. (2004). Complete Classification of Bilinear Hard-Core Functions. In: Franklin, M. (eds) Advances in Cryptology – CRYPTO 2004. CRYPTO 2004. Lecture Notes in Computer Science, vol 3152. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28628-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-28628-8_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22668-0
Online ISBN: 978-3-540-28628-8
eBook Packages: Springer Book Archive