Abstract
We propose a semantically-secure public-key encryption scheme whose security is polynomial-time equivalent to the hardness of solving random instances of the subset sum problem. The subset sum assumption required for the security of our scheme is weaker than that of existing subset-sum based encryption schemes, namely the lattice-based schemes of Ajtai and Dwork (STOC’97), Regev (STOC’03, STOC’05), and Peikert (STOC’09). Additionally, our proof of security is simple and direct. We also present a natural variant of our scheme that is secure against key-leakage attacks, and an oblivious transfer protocol that is secure against semi-honest adversaries.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-642-11799-2_36
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 595–618. Springer, Heidelberg (2009)
Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: STOC (1997); An improved version is described in ECCC 2007
Akavia, A., Goldwasser, S., Vaikuntanathan, V.: Simultaneous hardcore bits and cryptography against memory attacks. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 474–495. Springer, Heidelberg (2009)
Alekhnovich, M.: More on average case vs approximation complexity. In: FOCS (2003)
Crépeau, C.: Equivalence between two flavours of oblivious transfers. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 350–354. Springer, Heidelberg (1988)
Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Computing 38(1) (2008)
Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. In: CRYPTO (1982)
Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Communications of the ACM 28(6) (1985)
Flaxman, A., Przydatek, B.: Solving medium-density subset sum problems in expected polynomial time. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 305–314. Springer, Heidelberg (2005)
Frieze, A.: On the Lagarias-Odlyzko algorithm for the subset sum problem. SIAM Journal on Computing 15 (1986)
Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: FOCS (2000)
Goldreich, O., Micali, S., Wigderson, A.: How to play a mental game - a completeness theorem for protocols with honest majority. In: STOC (1987)
Goldreich, O.: Foundations of Cryptography - Volume 2 (Basic Applications). Cambridge University Press, Cambridge (2004)
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices, and new cryptographic constructions. In: STOC (2008)
Haitner, I.: Semi-honest to malicious oblivious transfer – The black-box way. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 412–426. Springer, Heidelberg (2008)
Hoeffding, W.: Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58(301) (1963)
Halderman, J.A., Schoen, S.D., Heninger, N., Clarkson, W., Paul, W., Calandrino, J.A., Feldman, A.J., Appelbaum, J., Felten, E.W.: Lest we remember: Cold boot attacks on encryption keys. In: USENIX Security (2008)
Impagliazzo, R., Naor, M.: Efficient cryptographic schemes provably as secure as subset sum. Journal of Cryptology 9(4) (1996)
Kilian, J.: Founding cryptography on oblivious transfer. In: STOC (1988)
Lyubashevsky, V., Micciancio, D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 577–594. Springer, Heidelberg (2009)
Lagarias, J.C., Odlyzko, A.M.: Solving low density subset sum problems. Journal of the ACM 32 (1985)
Lyubashevsky, V., Palacio, A., Segev, G.: Public-key cryptographic primitives provably as secure as subset sum. ePrint (2009)
Lyubashevsky, V.: The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol. 3624, pp. 378–389. Springer, Heidelberg (2005)
Merkle, R.C., Hellman, M.E.: Hiding information and signatures in trapdoor knapsacks. IEEE Trans. on Inf. Theory IT-24 (1978)
Naor, M., Segev, G.: Public-key cryptosystems resilient to key leakage. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 18–35. Springer, Heidelberg (2009)
Odlyzko, A.: The rise and fall of knapsack cryptosystems. In: Symposia of Applied Mathematics (1990)
Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: STOC (2009)
Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008)
Peikert, C., Waters, B.: Lossy Trapdoor Functions and Their Applications. In: STOC (2008)
Rabin, M.O.: How to exchange secret keys by oblivious transfer. In: Technical Report TR-81. Harvard Aiken Computation Laboratory (1981)
Regev, O.: New lattice based cryptographic constructions. In: STOC (2003)
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC (2005)
Shallue, A.: An improved multi-set algorithm for the dense subset sum problem. In: van der Poorten, A.J., Stein, A. (eds.) ANTS-VIII 2008. LNCS, vol. 5011, pp. 416–429. Springer, Heidelberg (2008)
Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5) (1997)
Yao, A.C.: How to generate and exchange secrets. In: FOCS (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lyubashevsky, V., Palacio, A., Segev, G. (2010). Public-Key Cryptographic Primitives Provably as Secure as Subset Sum. In: Micciancio, D. (eds) Theory of Cryptography. TCC 2010. Lecture Notes in Computer Science, vol 5978. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11799-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-11799-2_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11798-5
Online ISBN: 978-3-642-11799-2
eBook Packages: Computer ScienceComputer Science (R0)