{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T20:36:57Z","timestamp":1769719017598,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642117985","type":"print"},{"value":"9783642117992","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11799-2_23","type":"book-chapter","created":{"date-parts":[[2010,2,2]],"date-time":"2010-02-02T08:55:48Z","timestamp":1265100948000},"page":"382-400","source":"Crossref","is-referenced-by-count":54,"title":["Public-Key Cryptographic Primitives Provably as Secure as Subset Sum"],"prefix":"10.1007","author":[{"given":"Vadim","family":"Lyubashevsky","sequence":"first","affiliation":[]},{"given":"Adriana","family":"Palacio","sequence":"additional","affiliation":[]},{"given":"Gil","family":"Segev","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/978-3-642-03356-8_35","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"B. Applebaum","year":"2009","unstructured":"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.\u00a05677, pp. 595\u2013618. Springer, Heidelberg (2009)"},{"key":"#cr-split#-23_CR2.1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case\/average-case equivalence. In: STOC (1997);","DOI":"10.1145\/258533.258604"},{"key":"#cr-split#-23_CR2.2","unstructured":"An improved version is described in ECCC 2007"},{"key":"23_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1007\/978-3-642-00457-5_28","volume-title":"TCC 2009","author":"A. Akavia","year":"2009","unstructured":"Akavia, A., Goldwasser, S., Vaikuntanathan, V.: Simultaneous hardcore bits and cryptography against memory attacks. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 474\u2013495. Springer, Heidelberg (2009)"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: FOCS (2003)","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"23_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1007\/3-540-48184-2_30","volume-title":"Advances in Cryptology - CRYPTO \u201987","author":"C. Cr\u00e9peau","year":"1988","unstructured":"Cr\u00e9peau, C.: Equivalence between two flavours of oblivious transfers. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol.\u00a0293, pp. 350\u2013354. Springer, Heidelberg (1988)"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Computing\u00a038(1) (2008)","DOI":"10.1137\/060651380"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. In: CRYPTO (1982)","DOI":"10.1007\/978-1-4757-0602-4_19"},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Communications of the ACM\u00a028(6) (1985)","DOI":"10.1145\/3812.3818"},{"key":"23_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-540-31856-9_25","volume-title":"STACS 2005","author":"A. Flaxman","year":"2005","unstructured":"Flaxman, A., Przydatek, B.: Solving medium-density subset sum problems in expected polynomial time. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 305\u2013314. Springer, Heidelberg (2005)"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"Frieze, A.: On the Lagarias-Odlyzko algorithm for the subset sum problem. SIAM Journal on Computing\u00a015 (1986)","DOI":"10.1137\/0215038"},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: FOCS (2000)","DOI":"10.1109\/SFCS.2000.892121"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play a mental game - a completeness theorem for protocols with honest majority. In: STOC (1987)","DOI":"10.1145\/28395.28420"},{"key":"23_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography - Volume 2 (Basic Applications)","author":"O. Goldreich","year":"2004","unstructured":"Goldreich, O.: Foundations of Cryptography - Volume 2 (Basic Applications). Cambridge University Press, Cambridge (2004)"},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices, and new cryptographic constructions. In: STOC (2008)","DOI":"10.1145\/1374376.1374407"},{"key":"23_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/978-3-540-78524-8_23","volume-title":"Theory of Cryptography","author":"I. Haitner","year":"2008","unstructured":"Haitner, I.: Semi-honest to malicious oblivious transfer \u2013 The black-box way. In: Canetti, R. (ed.) TCC 2008. LNCS, vol.\u00a04948, pp. 412\u2013426. Springer, Heidelberg (2008)"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association\u00a058(301) (1963)","DOI":"10.1080\/01621459.1963.10500830"},{"key":"23_CR17","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1145\/1506409.1506429"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Naor, M.: Efficient cryptographic schemes provably as secure as subset sum. Journal of Cryptology\u00a09(4) (1996)","DOI":"10.1007\/BF00189260"},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"Kilian, J.: Founding cryptography on oblivious transfer. In: STOC (1988)","DOI":"10.1145\/62212.62215"},{"key":"23_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/978-3-642-03356-8_34","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"V. Lyubashevsky","year":"2009","unstructured":"Lyubashevsky, V., Micciancio, D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 577\u2013594. Springer, Heidelberg (2009)"},{"key":"23_CR21","doi-asserted-by":"crossref","unstructured":"Lagarias, J.C., Odlyzko, A.M.: Solving low density subset sum problems. Journal of the ACM\u00a032 (1985)","DOI":"10.1145\/2455.2461"},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V., Palacio, A., Segev, G.: Public-key cryptographic primitives provably as secure as subset sum. ePrint (2009)","DOI":"10.1007\/978-3-642-11799-2_23"},{"key":"23_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/11538462_32","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V. Lyubashevsky","year":"2005","unstructured":"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.\u00a03624, pp. 378\u2013389. Springer, Heidelberg (2005)"},{"key":"23_CR24","doi-asserted-by":"crossref","unstructured":"Merkle, R.C., Hellman, M.E.: Hiding information and signatures in trapdoor knapsacks. IEEE Trans. on Inf. Theory\u00a0IT-24 (1978)","DOI":"10.1109\/TIT.1978.1055927"},{"key":"23_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-642-03356-8_2","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"M. Naor","year":"2009","unstructured":"Naor, M., Segev, G.: Public-key cryptosystems resilient to key leakage. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 18\u201335. Springer, Heidelberg (2009)"},{"key":"23_CR26","doi-asserted-by":"crossref","unstructured":"Odlyzko, A.: The rise and fall of knapsack cryptosystems. In: Symposia of Applied Mathematics (1990)","DOI":"10.1090\/psapm\/042\/1095552"},{"key":"23_CR27","doi-asserted-by":"crossref","unstructured":"Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: STOC (2009)","DOI":"10.1145\/1536414.1536461"},{"key":"23_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-540-85174-5_31","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"C. Peikert","year":"2008","unstructured":"Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.\u00a05157, pp. 554\u2013571. Springer, Heidelberg (2008)"},{"key":"23_CR29","doi-asserted-by":"crossref","unstructured":"Peikert, C., Waters, B.: Lossy Trapdoor Functions and Their Applications. In: STOC (2008)","DOI":"10.1145\/1374376.1374406"},{"key":"23_CR30","unstructured":"Rabin, M.O.: How to exchange secret keys by oblivious transfer. In: Technical Report TR-81. Harvard Aiken Computation Laboratory (1981)"},{"key":"23_CR31","doi-asserted-by":"crossref","unstructured":"Regev, O.: New lattice based cryptographic constructions. In: STOC (2003)","DOI":"10.1145\/780542.780603"},{"key":"23_CR32","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"23_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/978-3-540-79456-1_28","volume-title":"Algorithmic Number Theory","author":"A. Shallue","year":"2008","unstructured":"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.\u00a05011, pp. 416\u2013429. Springer, Heidelberg (2008)"},{"key":"23_CR34","doi-asserted-by":"crossref","unstructured":"Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput.\u00a026(5) (1997)","DOI":"10.1137\/S0097539795293172"},{"key":"23_CR35","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: How to generate and exchange secrets. In: FOCS (1986)","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11799-2_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T10:29:14Z","timestamp":1558780154000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11799-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642117985","9783642117992"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11799-2_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}