Abstract
We show very efficient constructions for a pseudorandom generator and for a universal one-way hash function based on the intractability of the subset-sum problem for certain dimensions. (Pseudorandom generators can be used for private-key encryption and universal one-way hash functions for signature schemes.) The increase in efficiency in our construction is due to the fact that many bits can be generated/hashed with one application of the assumed one-way function.
All of our constructions can be implemented in NC using an optimal number of processors.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Ajtai, ∑ 11 formulas of finite structures, Ann. Pure Appl. Logic, vol. 24, 1983, pp. 1–8.
L. Babai, Random oracles separate PSPACE from the polynomial-time hierarchy, Inform. Proc. Lett., vol. 26, 1987, pp. 51–53.
M. Blum, Coin flipping by telephone, Proc. 24th IEEE Compcon, 1982, pp. 133–137.
L. Blum, M. Blum, and M. Shub, A simple unpredictable pseudo-random number generator, Siam J. Comput., Vol. 15, 1986, pp. 364–383.
M. Blum and S. Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM J. Comput., vol. 13, 1984, pp. 850–864.
R. B. Boppana and J. C. Lagarias, One-way functions and circuit complexity, in Proc. Structure in Complexity Theory, Springer-Verlag, New York, 1986, pp. 51–65.
G. Brassard, D. Chaum, and C. Crepeau, Minimum disclosure proofs of knowledge, J. Comput. System Sci., vol. 37, 1988, pp. 156–189.
E. F. Brickell, Solving low density knapsacks, Proc. Crypto '83, pp. 25–37.
E. F. Brickell and A. M. Odlyzko, Cryptanalysis: a survey of recent results, Proc. IEEE, vol. 76, 1988, pp. 578–593.
L. Carter and M. Wegman, Universal classes of hash functions, J. Comput. System Sci., vol. 18, 1979, pp. 143–154.
B. Chor and R. L. Rivest, A knapsack type public key crypto-system based on arithmetic in finite fields, IEEE Trans. Informa. Theory, vol. 34, 1988, pp. 901–909.
M. J. Coster, B. A. LaMacchia, A. M. Odlyzko, and C. P. Schnorr, An improved low-density subset sum algorithm, Proc. Advances in Cryptology—Eurocrypt '91, Springer-Verlag, Berlin, 1991, pp. 54–67.
A. Fiat and A. Shamir, How to prove yourself, Proc. Advances in Cryptology—Crypto '86, Springer-Verlag, Berlin, 1987, pp. 641–654.
A. M. Frieze, On the Lagarias-Odlyzko algorithm for the subset sum problem, SIAM J. Comput., vol. 15, 1986, pp. 536–539.
M. Furst and R. Kannan, Succinct certificates for almost all subset sum problems, SIAM J. Comput., vol. 18, 1989, pp. 550–558.
M. Furst, J. Saxe, and M. Sipser, Parity circuits and the polynomial time hierarchy, Proc. 22nd Symposium on Foundations of Computer Science, 1981, pp. 260–270.
Z. Galil and O. Margalit, An almost linear time algorithm for the dense subset sum problem, SIAM J. Comput., vol. 20, 1991, pp. 1157–1189.
O. Goldreich, S. Goldwasser, and S. Micali, How to construct random functions, J. Assoc. Comput. Mach., vol. 33, 1986, pp. 792–807.
O. Goldreich, H. Krawczyk, and M. Luby, On the existence of pseudorandom generators, Proc. 29th Symposium on the Foundation of Computer Science, 1988, pp. 12–24.
O. Goldreich and L. Levin, A hard-core predicate for all one-way functions, Proc. 21st Symposium on the Theory of Computing, 1989, pp. 25–32.
S. Goldwasser and S. Micali, Probabilistic encryption, J. Comput. System Sci., vol. 28, 1984, pp. 270–299.
O. Goldreich, S. Micali, and A. Wigderson, Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, Proc. 27th Symposium on Foundations of Computer Science, 1986, pp. 174–187.
J. Hastad, Improved lower bounds for small depth circuits, Proc. 18th Symposium on Theory of Computing, 1986, pp. 6–20.
J. Hastad, Pseudo-random generators under uniform assumptions, Proc. 19th Symposium on Theory of Computing, 1990, pp. 395–404.
R. Impagliazzo, L. Levin, and M. Luby, Pseudo-random generation from one-way functions, Proc. 21st Symposium on Theory of Computing, 1989, pp. 12–24.
R. Impagliazzo and D. Zuckerman, Recycling random bits, Proc. 30th Symposium on Foundations of Computer Science, 1989, pp. 248–253.
A. Joux and J. Stern, Improving the critical complexity of the Lagarias-Odlyzko attack against subset sum problems, Proc. 8th International Conference on Fundamentals of Computation Theory, Springer-Verlag, Berlin, 1991, pp. 258–264.
R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computation, R. E. Miller and J. W. Thatcher, eds., Plenum, New York, 1972.
M. Kharitonov, Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution, Proc. 5th COLT, Morgan Kaufman, Los Altos, CA, 1992, pp. 29–36.
M. Kharitonov, Cryptographic hardness of distribution-specific learning, Proc. 25th Symposium on Theoryof Computing, 1993, pp. 372–381.
H. Krawczyk, Secret sharing made short, Proc. Advances in Cryptology—Crypto '93, Springer-Verlag, Berlin, 1994, pp. 136–146.
J. C. Lagarias and A. M. Odlyzko, Solving low density subset sum problems, J. Assoc. Comput. Mach., vol. 32, 1985, pp. 229–246.
A. K. Lenstra, H. W. Lenstra, and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., vol. 261, 1982, pp. 515–534.
N. Linial, Y. Mansour, and N. Nisan, Constant depth circuits, Fourier transform, and learnability, J. Assoc. Comput. Mach., vol. 40, 1993, pp. 607–620.
M. Luby and C. Rackoff, How to construct a pseudo-random permutation from a pseudo-random function, SIAM J. Comput., vol. 17, 1988, pp. 373–386.
R. C. Merkle and M. Hellman, Hiding information and signature in trapdoor knapsack, IEEE Trans. Inform. Theory, vol. 24, 1978, pp. 525–530.
S. Micali and C. P. Schnorr, Efficient, perfect polynomial random number generators, J. Cryptology, vol. 3, 1991, pp. 157–172.
M. Naor, Bit commitment using pseudo-randomness, J. Cryptology, vol. 4, 1991, pp. 151–158.
M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung, Perfect zero-knowledge arguments for NP can be based on general complexity assumptions, Proc. Advances in Cryptology—Crypto '92, Springer-Verlag, Berlin, 1993, pp. 196–214.
M. Naor and M. Yung, Universal one-way hash functions and their cryptographic applications, Proc. 21st Symposium on the Theory of Computing, 1989, pp. 33–43.
A. M. Odlyzko, The rise and fall of knapsack cryptosystems, in Cryptology and Computational Number Theory, C. Pomerance ed., Proc. Sympos. Appl. Math, vol. 42, 1990, American Mathematical Society, Providence, RI, pp. 75–88.
J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proc. 22nd Symposium on Theory of Computing, 1990, pp. 387–394.
M. Santha and U. V. Vazirani, Generating quasi-random sequences from slightly-random sources, Proc. 25th Symposium on the Theory of Computing, 1984, pp. 434–440.
C. P. Schnorr and M. Euchner, Lattice base reduction: improved practical algorithms for solving subset sum problems, Math. Programming, vol. 66, 1994, pp. 181–199.
C. P. Schnorr and H. H. Hörner, Attacking the Chor-Rivest cryptosystem by improved lattice reduction, Manuscript, 1994.
R. Schroeppel and A. Shamir, A T · S 2=O(2n) time/space tradeoff for certain NP-complete problems, Proc. 20th Symposium on Foundations of Computer Science, 1979, pp. 328–336.
A. C. Yao, Theory and applications of trapdoor functions, Proc. 23rd Symposium on Foundations of Computer Science, 1982, pp. 80–91.
A. C. Yao, Separating the polynomial time hierarchy by oracles, Proc. 26th Symposium on Foundations of Computer Science, 1985, pp. 1–10.
Author information
Authors and Affiliations
Additional information
Communicated by Steven Rudich
Part of this work was done while both authors were at the University of California at Berkeley and part when the second author was at the IBM Almaden Research Center. Research supported by NSF Grant CCR 88-13632. A preliminary version of this paper appeared in Proc. 30th Symposium on Foundations of Computer Science, 1989.
Incumbent of the Morris and Rose Goldman Career Development Chair. Research supported by an Alon Fellowship and a grant from the Israel Science Foundation administered by the Israeli Academy of Sciences.
Rights and permissions
About this article
Cite this article
Impagliazzo, R., Naor, M. Efficient cryptographic schemes provably as secure as subset sum. J. Cryptology 9, 199–216 (1996). https://doi.org/10.1007/BF00189260
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00189260