{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T09:58:41Z","timestamp":1767261521850,"version":"3.48.0"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031252105"},{"type":"electronic","value":"9783031252112"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-25211-2_1","type":"book-chapter","created":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T19:02:42Z","timestamp":1674673362000},"page":"3-14","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Reductions and\u00a0Algorithms for\u00a0Subset Product"],"prefix":"10.1007","author":[{"given":"Pranjal","family":"Dutta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahesh Sreekumar","family":"Rajasree","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,26]]},"reference":[{"issue":"1","key":"1_CR1","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.cor.2007.09.009","volume":"36","author":"C Bazgan","year":"2009","unstructured":"Bazgan, C., Hugot, H., Vanderpooten, D.: Solving efficiently the 0\u20131 multi-objective knapsack problem. Comput. Oper. Res. 36(1), 260\u2013279 (2009)","journal-title":"Comput. Oper. Res."},{"key":"1_CR2","unstructured":"Bellman, R.E.: Dynamic programming (1957)"},{"key":"1_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-642-38616-9_2","volume-title":"Post-Quantum Cryptography","author":"DJ Bernstein","year":"2013","unstructured":"Bernstein, D.J., Jeffery, S., Lange, T., Meurer, A.: Quantum algorithms for the subset-sum problem. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 16\u201333. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38616-9_2"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Bringmann, K.: A near-linear pseudopolynomial time algorithm for subset sum. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1073\u20131084. SIAM (2017)","DOI":"10.1137\/1.9781611974782.69"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Wellnitz, P.: On near-linear-time algorithms for dense subset sum. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1777\u20131796. SIAM (2021)","DOI":"10.1137\/1.9781611976465.107"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/11761679_11","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"S Contini","year":"2006","unstructured":"Contini, S., Lenstra, A.K., Steinfeld, R.: VSH, an efficient and provable collision-resistant hash function. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 165\u2013182. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11761679_11"},{"key":"1_CR7","unstructured":"Draziotis, K.A., Martidis, V., Tiganourias, S.: Product subset problem: applications to number theory and cryptography. arXiv preprint arXiv:2002.07095 (2020)"},{"key":"1_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-030-95018-7_19","volume-title":"Algorithms and Discrete Applied Mathematics","author":"P Dutta","year":"2022","unstructured":"Dutta, P., Rajasree, M.S.: Algebraic algorithms for\u00a0variants of\u00a0subset sum. In: Balachandran, N., Inkulu, R. (eds.) CALDAM 2022. LNCS, vol. 13179, pp. 237\u2013251. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-95018-7_19"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Esser, A., May, A.: Low weight discrete logarithm and subset sum in 20. 65n with polynomial memory. memory 1, 2 (2020)","DOI":"10.1007\/978-3-030-45727-3_4"},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-662-49384-7_2","volume-title":"Public-Key Cryptography \u2013 PKC 2016","author":"S Faust","year":"2016","unstructured":"Faust, S., Masny, D., Venturi, D.: Chosen-ciphertext security from subset sum. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9614, pp. 35\u201346. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49384-7_2"},{"key":"1_CR11","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 174. Freeman, San Francisco (1979)"},{"key":"1_CR12","unstructured":"Helm, A., May, A.: Subset sum quantumly in 1.17$$\\hat{\\,}$$ n. In: 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). pp. 1\u201315. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Jin, C., Vyas, N., Williams, R.: Fast low-space algorithms for subset sum. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1757\u20131776. SIAM (2021)","DOI":"10.1137\/1.9781611976465.106"},{"key":"1_CR14","unstructured":"Jin, C., Wu, H.: A simple near-linear pseudopolynomial time randomized algorithm for subset sum. arXiv preprint arXiv:1807.11597 (2018)"},{"key":"1_CR15","unstructured":"Kane, D.M.: Unary subset-sum is in logspace. arXiv preprint arXiv:1012.1336 (2010)"},{"issue":"17","key":"1_CR16","doi-asserted-by":"publisher","first-page":"1908","DOI":"10.1016\/j.dam.2010.08.001","volume":"158","author":"MY Kovalyov","year":"2010","unstructured":"Kovalyov, M.Y., Pesch, E.: A generic approach to proving np-hardness of partition type problems. Discret. Appl. Math. 158(17), 1908\u20131912 (2010)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"1_CR17","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1090\/S0894-0347-1992-1137100-0","volume":"5","author":"HW Lenstra","year":"1992","unstructured":"Lenstra, H.W., Pomerance, C.: A rigorous time bound for factoring integers. J. Am. Math. Soc. 5(3), 483\u2013516 (1992)","journal-title":"J. Am. Math. Soc."},{"key":"1_CR18","unstructured":"Lewis, H.R.: Computers and Intractability. A Guide to the Theory of NP-Completeness, Freeman, San Francisco (1983)"},{"key":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/978-3-642-11799-2_23","volume-title":"Theory of Cryptography","author":"V Lyubashevsky","year":"2010","unstructured":"Lyubashevsky, V., Palacio, A., Segev, G.: Public-key cryptographic primitives provably as secure as subset sum. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 382\u2013400. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11799-2_23"},{"issue":"4","key":"1_CR20","first-page":"177","volume":"28","author":"J Nagura","year":"1952","unstructured":"Nagura, J.: On the interval containing at least one prime number. Proc. Jpn. Acad. 28(4), 177\u2013181 (1952)","journal-title":"Proc. Jpn. Acad."},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Pferschy, U., Schauer, J., Thielen, C.: Approximating the product knapsack problem. Optim. Lett. 15, 2529\u20132540 (2021)","DOI":"10.1007\/s11590-021-01760-x"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-25211-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T09:55:33Z","timestamp":1767261333000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-25211-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031252105","9783031252112"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-25211-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"26 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Gandhinagar","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 February 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 February 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/caldam2023.daiict.ac.in\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}