{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:17:46Z","timestamp":1740097066386,"version":"3.37.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319116587"},{"type":"electronic","value":"9783319116594"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-11659-4_2","type":"book-chapter","created":{"date-parts":[[2014,9,24]],"date-time":"2014-09-24T22:19:48Z","timestamp":1411597188000},"page":"22-39","source":"Crossref","is-referenced-by-count":6,"title":["On the Efficiency of Provably Secure NTRU"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Cabarcas","sequence":"first","affiliation":[]},{"given":"Patrick","family":"Weiden","sequence":"additional","affiliation":[]},{"given":"Johannes","family":"Buchmann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","unstructured":"Albrecht, M.R., Cid, C., Faug\u00e8re, J.C., Fitzpatrick, R., Perret, L.: On the complexity of the BKW algorithm on LWE. Cryptology ePrint Archive, Report 2012\/636 (2012), \n                  \n                    http:\/\/eprint.iacr.org\/2012\/636\/"},{"key":"2_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-22006-7_34","volume-title":"Automata, Languages and Programming","author":"S. Arora","year":"2011","unstructured":"Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 403\u2013415. Springer, Heidelberg (2011)"},{"issue":"4","key":"2_CR3","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A. Blum","year":"2003","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM\u00a050(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"key":"2_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-642-45239-0_4","volume-title":"Cryptography and Coding","author":"J. Bos","year":"2013","unstructured":"Bos, J., Lauter, K., Loftus, J., Naehrig, M.: Improved security for a ring-based fully homomorphic encryption scheme. In: Stam, M. (ed.) IMACC 2013. LNCS, vol.\u00a08308, pp. 45\u201364. Springer, Heidelberg (2013)"},{"key":"2_CR5","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/2488608.2488680","volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC 2013","author":"Z. Brakerski","year":"2013","unstructured":"Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehl\u00e9, D.: Classical hardness of learning with errors. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 575\u2013584. ACM, New York (2013)"},{"key":"2_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-642-22792-9_29","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"Z. Brakerski","year":"2011","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.\u00a06841, pp. 505\u2013524. Springer, Heidelberg (2011)"},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1007\/978-3-662-43414-7_20","volume-title":"SAC 2013","author":"J. Buchmann","year":"2014","unstructured":"Buchmann, J., Cabarcas, D., G\u00f6pfert, F., H\u00fclsing, A., Weiden, P.: Discrete ziggurat: A time-memory trade-off for sampling from a gaussian distribution over the integers. In: Lange, T., Lauter, K., Lison\u0115k, P. (eds.) SAC 2013. LNCS, vol.\u00a08282, pp. 402\u2013417. Springer, Heidelberg (2014)"},{"key":"2_CR8","unstructured":"Cabarcas, D., G\u00f6pfert, F., Weiden, P.: Provably secure LWE-encryption with uniform secret. Cryptology ePrint Archive, Report 2013\/164 (2013), \n                  \n                    http:\/\/eprint.iacr.org\/2013\/164"},{"key":"2_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-25385-0_1","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2011","author":"Y. Chen","year":"2011","unstructured":"Chen, Y., Nguyen, P.Q.: BKZ 2.0: Better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol.\u00a07073, pp. 1\u201320. Springer, Heidelberg (2011)"},{"key":"2_CR10","unstructured":"Ding, J.: Solving LWE problem with bounded errors in polynomial time. Cryptology ePrint Archive, Report 2010\/558 (2010), \n                  \n                    http:\/\/eprint.iacr.org\/2010\/558\/"},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-40041-4_3","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"L. Ducas","year":"2013","unstructured":"Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal gaussians. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol.\u00a08042, pp. 40\u201356. Springer, Heidelberg (2013), \n                  \n                    http:\/\/dx.doi.org\/10.1007\/978-3-642-40041-4_3"},{"key":"2_CR12","unstructured":"Galbraith, S.D., Dwarakanath, N.C.: Efficient sampling from discrete Gaussians for lattice-based cryptography on a constrained device (2012), preprint available at \n                  \n                    http:\/\/www.math.auckland.ac.nz\/~sgal018\/gen-gaussians.pdf"},{"key":"2_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1007\/978-3-642-13190-5_26","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"C. Gentry","year":"2010","unstructured":"Gentry, C., Halevi, S., Vaikuntanathan, V.: A simple BGN-type cryptosystem from LWE. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 506\u2013522. Springer, Heidelberg (2010), \n                  \n                    http:\/\/dx.doi.org\/10.1007\/978-3-642-13190-5_26"},{"key":"2_CR14","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th Annual ACM Symposium on Theory of Computing, pp. 197\u2013206. ACM Press (May 2006)"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1007\/978-3-642-33027-8_30","volume-title":"Cryptographic Hardware and Embedded Systems \u2013 CHES 2012","author":"N. G\u00f6ttert","year":"2012","unstructured":"G\u00f6ttert, N., Feller, T., Schneider, M., Buchmann, J., Huss, S.A.: On the design of hardware building blocks for modern lattice-based encryption schemes. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol.\u00a07428, pp. 512\u2013529. Springer, Heidelberg (2012)"},{"key":"2_CR16","unstructured":"Granlund, T.: The GNU multiple precision arithmetic library, \n                  \n                    http:\/\/gmplib.org\/"},{"key":"2_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BFb0054868","volume-title":"Algorithmic Number Theory","author":"J. Hoffstein","year":"1998","unstructured":"Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol.\u00a01423, pp. 267\u2013288. Springer, Heidelberg (1998)"},{"key":"2_CR18","unstructured":"Hoffstein, J., Pipher, J., Whyte, W.: A note on hybrid resistant parameter selection for NTRUEncrypt (2010) (unpublished)"},{"key":"2_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-74143-5_9","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"N. Howgrave-Graham","year":"2007","unstructured":"Howgrave-Graham, N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.\u00a04622, pp. 150\u2013169. Springer, Heidelberg (2007)"},{"key":"2_CR20","unstructured":"Kaps, J.P.: Cryptography for Ultra-Low Power Devices. Ph.D. thesis, Worcester Polytechnic Institute (2006)"},{"key":"2_CR21","unstructured":"Karney, C.F.F.: Sampling exactly from the normal distribution. Tech. rep., SRI International (March 2013), \n                  \n                    http:\/\/arxiv.org\/abs\/1303.6257"},{"key":"2_CR22","unstructured":"Knuth, D.E., Yao, A.C.: The complexity of non uniform random number generation. In: Algorithms and Complexity: New Directions and Recent Results, pp. 357\u2013428 (1976)"},{"key":"2_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-19074-2_21","volume-title":"Topics in Cryptology \u2013 CT-RSA 2011","author":"R. Lindner","year":"2011","unstructured":"Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol.\u00a06558, pp. 319\u2013339. Springer, Heidelberg (2011)"},{"key":"2_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/978-3-642-36095-4_19","volume-title":"Topics in Cryptology \u2013 CT-RSA 2013","author":"M. Liu","year":"2013","unstructured":"Liu, M., Nguyen, P.Q.: Solving BDD by enumeration: An update. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol.\u00a07779, pp. 293\u2013309. Springer, Heidelberg (2013)"},{"key":"2_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-13190-5_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"V. Lyubashevsky","year":"2010","unstructured":"Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 1\u201323. Springer, Heidelberg (2010)"},{"key":"2_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-642-40041-4_2","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"D. Micciancio","year":"2013","unstructured":"Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol.\u00a08042, pp. 21\u201339. Springer, Heidelberg (2013), \n                  \n                    http:\/\/dx.doi.org\/10.1007\/978-3-642-40041-4_2"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J.A., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 147\u2013191. Springer (2008)","DOI":"10.1007\/978-3-540-88702-7_5"},{"key":"2_CR28","first-page":"113","volume-title":"Proceedings of the 3rd ACM Cloud Computing Security Workshop, CCSW 2011","author":"M. Naehrig","year":"2011","unstructured":"Naehrig, M., Lauter, K., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: Proceedings of the 3rd ACM Cloud Computing Security Workshop, CCSW 2011, pp. 113\u2013124. ACM, New York (2011)"},{"issue":"4","key":"2_CR29","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1109\/TC.2003.1190585","volume":"52","author":"C. O\u2019Rourke","year":"2003","unstructured":"O\u2019Rourke, C., Sunar, B.: Achieving NTRU with Montgomery multiplication. IEEE Transactions on Computers\u00a052(4), 440\u2013448 (2003)","journal-title":"IEEE Transactions on Computers"},{"key":"2_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/978-3-642-14623-7_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"C. Peikert","year":"2010","unstructured":"Peikert, C.: An efficient and parallel Gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 80\u201397. Springer, Heidelberg (2010)"},{"key":"2_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-642-35999-6_18","volume-title":"Selected Areas in Cryptography","author":"T. Plantard","year":"2013","unstructured":"Plantard, T., Susilo, W., Zhang, Z.: Lattice reduction for modular knapsack. In: Knudsen, L.R., Wu, H. (eds.) SAC 2012. LNCS, vol.\u00a07707, pp. 275\u2013286. Springer, Heidelberg (2013), \n                  \n                    http:\/\/dx.doi.org\/10.1007\/978-3-642-35999-6_18"},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th Annual ACM Symposium on Theory of Computing, pp. 84\u201393. ACM Press (May 2005)","DOI":"10.1145\/1060590.1060603"},{"key":"2_CR33","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF01581144","volume":"66","author":"C.P. Schnorr","year":"1994","unstructured":"Schnorr, C.P., Euchner, M.: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical Programming\u00a066, 181\u2013199 (1994)","journal-title":"Mathematical Programming"},{"key":"2_CR34","unstructured":"Shoup, V.: Number theory library (NTL) for C++, \n                  \n                    http:\/\/www.shoup.net\/ntl\/"},{"key":"2_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-642-20465-4_4","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"D. Stehl\u00e9","year":"2011","unstructured":"Stehl\u00e9, D., Steinfeld, R.: Making NTRU as secure as worst-case problems over ideal lattices. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol.\u00a06632, pp. 27\u201347. Springer, Heidelberg (2011)"},{"key":"2_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-642-10366-7_36","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"D. Stehl\u00e9","year":"2009","unstructured":"Stehl\u00e9, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.\u00a05912, pp. 617\u2013635. Springer, Heidelberg (2009), \n                  \n                    http:\/\/dx.doi.org\/10.1007\/978-3-642-10366-7_36"}],"container-title":["Lecture Notes in Computer Science","Post-Quantum Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-11659-4_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T20:07:56Z","timestamp":1558987676000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-11659-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319116587","9783319116594"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-11659-4_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}