New Implications and Improved Efficiency of Constructions Based on One-way Functions.

摘要

Since most interesting cryptographic tasks are impossible to achieve with absolute, information-theoretic security, modern cryptography aims to design cryptographic primitives (i.e., algorithms/protocols) that are computationally infeasible to break (i.e., secure against computationally bounded adversaries). Proving lower bounds of the type needed, however, seems beyond the reach of current techniques in complexity theory. 1 Thus, research in the Foundations of Cryptography has aimed to design primitives based on complexity assumptions that are as weak as possible. It is well known that the assumption that one-way functions exist, is necessary for most cryptographic primitives. It is then natural to pose the opposite question. Namely, does the existence of one-way functions imply the existence of all cryptographic primitives? Here we consider some of the most fundamental primitives in cryptography and prove the following results about the power of one-way functions in implementing these primitives.;Statistically hiding commitments. Statistically hiding commitments (ones where the hiding property holds against even computationally unbounded adversaries) are among the few fundamental primitives for which we have failed to find exact characterization. That is, until recently it was only known how to build these primitives from seemingly stronger assumptions than the existence of one-way functions, yet there was no black-box separation between these primitives and one-way functions.;We resolve the complexity of statistically hiding commitments, giving a construction of statistically hiding commitment schemes under the minimal complexity assumption that one-way functions exist. By this we give a positive answer to an open question posed by Naor, Ostrovsky, Venkatesan, and Yung (CRYPTO '92, J. Cryptology '98).;Pseudorandom generators. We present a construction of pseudorandom generators based on regular one-way functions that is significantly better (in terms of security and efficiency) than the previous construction of Goldreich, Krawczyk and Luby (FOCS '88, SIAM J. on Computing '99) (i.e., the input length of our generator is theta(n log n) compared to theta(n3) in Goldreich et al., where n is the input length of the underlying one-way function). In addition, we present a construction of pseudorandom generators from any one-way function that improves the construction of Hastad, Impagliazzo, Levin and Luby (STOC '89, STOC '90, SIAM J. on Computing '99). Finally, we show a rather efficient construction of pseudorandom generator (input length theta(n2)) based on one-way functions with exponential hardness. Our construction significantly improves the previous construction due to Holenstein (TCC '06) (input length theta( n5)).;Interactive hashing. We give an alternative proof for interactive hashing protocol of Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92, J. Cryptology '98), which seems to us significantly simpler and more intuitive than the original one. Moreover, the new proof achieves much better parameters (in terms of how security preserving the reduction is). Finally, our proof implies a more versatile interactive hashing theorem in a more general setting than that of Naor et al.;Hardness amplifications. We present a reduction for security amplification of regular one-way functions, which incur only theta(n log(n)) blow-up in the input length. This improves upon the reduction of Goldreich, Impagliazzo, Levin, Venkatesan and Zuckerman (FOCS '90) in that the reduction does not need to know the regularity parameter of the functions (in terms of security, the two reductions are incomparable).;1Indeed, it would require at least proving that P ≠ NP.