{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:36:48Z","timestamp":1766281008795},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319566191"},{"type":"electronic","value":"9783319566207"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-56620-7_17","type":"book-chapter","created":{"date-parts":[[2017,3,31]],"date-time":"2017-03-31T02:29:18Z","timestamp":1490927358000},"page":"479-500","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack"],"prefix":"10.1007","author":[{"given":"Ronald","family":"Cramer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivan","family":"Damg\u00e5rd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chaoping","family":"Xing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chen","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,1]]},"reference":[{"issue":"3","key":"17_CR1","first-page":"81","volume":"17","author":"L Bassalygo","year":"1981","unstructured":"Bassalygo, L.: Asymptotically optimal switching circuits. Probl. Inf. Transm. 17(3), 81\u201388 (1981)","journal-title":"Probl. Inf. Transm."},{"key":"17_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/978-3-662-53015-3_17","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"C Baum","year":"2016","unstructured":"Baum, C., Damg\u00e5rd, I., Larsen, K.G., Nielsen, M.: How to prove knowledge of small secrets. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 478\u2013498. Springer, Heidelberg (2016). doi:\n                      10.1007\/978-3-662-53015-3_17\n                      \n                    . Cryptology ePrint Archive, Report 2016\/538 (2016)"},{"key":"17_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-20465-4_11","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"R Bendlin","year":"2011","unstructured":"Bendlin, R., Damg\u00e5rd, I., Orlandi, C., Zakarias, S.: Semi-homomorphic encryption and multiparty computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 169\u2013188. Springer, Heidelberg (2011). doi:\n                      10.1007\/978-3-642-20465-4_11"},{"key":"17_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/3-540-48071-4_28","volume-title":"Advances in Cryptology \u2014 CRYPTO 19 92","author":"M Bellare","year":"1993","unstructured":"Bellare, M., Goldreich, O.: On defining proofs of knowledge. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 390\u2013420. Springer, Heidelberg (1993). doi:\n                      10.1007\/3-540-48071-4_28"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 2012, pp. 309\u2013325. ACM, New York (2012)","DOI":"10.1145\/2090236.2090262"},{"issue":"2","key":"17_CR6","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1137\/120868669","volume":"43","author":"Z Brakerski","year":"2014","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. SIAM J. Comput. 43(2), 831\u2013871 (2014)","journal-title":"SIAM J. Comput."},{"key":"17_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-03356-8_11","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"R Cramer","year":"2009","unstructured":"Cramer, R., Damg\u00e5rd, I.: On the amortized complexity of zero-knowledge protocols. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 177\u2013191. Springer, Heidelberg (2009). doi:\n                      10.1007\/978-3-642-03356-8_11"},{"issue":"2","key":"17_CR8","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/s00145-013-9145-x","volume":"27","author":"R Cramer","year":"2014","unstructured":"Cramer, R., Damg\u00e5rd, I., Keller, M.: On the amortized complexity of zero-knowledge protocols. J. Cryptol. 27(2), 284\u2013316 (2014)","journal-title":"J. Cryptol."},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"Capalbo, M., Reingold, O., Vadhan, S., Wigderson, A.: Randomness conductors and constant-degree lossless expanders. In: STOC, pp. 659\u2013668 (2002)","DOI":"10.1145\/509907.510003"},{"key":"17_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/3-540-36178-2_8","volume-title":"Advances in Cryptology \u2014 ASIACRYPT 2002","author":"I Damg\u00e5rd","year":"2002","unstructured":"Damg\u00e5rd, I., Fujisaki, E.: A statistically-hiding integer commitment scheme based on groups with hidden order. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 125\u2013142. Springer, Heidelberg (2002). doi:\n                      10.1007\/3-540-36178-2_8"},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-40203-6_1","volume-title":"Computer Security \u2013 ESORICS 2013","author":"I Damg\u00e5rd","year":"2013","unstructured":"Damg\u00e5rd, I., Keller, M., Larraia, E., Pastro, V., Scholl, P., Smart, N.P.: Practical covertly secure MPC for dishonest majority \u2013 or: breaking the SPDZ limits. In: Crampton, J., Jajodia, S., Mayes, K. (eds.) ESORICS 2013. LNCS, vol. 8134, pp. 1\u201318. Springer, Heidelberg (2013). doi:\n                      10.1007\/978-3-642-40203-6_1"},{"key":"17_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-642-32009-5_38","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"I Damg\u00e5rd","year":"2012","unstructured":"Damg\u00e5rd, I., Pastro, V., Smart, N., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 643\u2013662. Springer, Heidelberg (2012). doi:\n                      10.1007\/978-3-642-32009-5_38"},{"key":"17_CR13","unstructured":"Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 3, pp. 236\u2013241 (1996)"},{"key":"17_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-40041-4_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"C Gentry","year":"2013","unstructured":"Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 75\u201392. Springer, Heidelberg (2013). doi:\n                      10.1007\/978-3-642-40041-4_5"},{"key":"17_CR15","doi-asserted-by":"crossref","DOI":"10.1201\/b17668","volume-title":"Introduction to Modern Cryptography","author":"J Katz","year":"2014","unstructured":"Katz, J., Lindell, Y.: Introduction to Modern Cryptography. CRC Press, Boca Raton (2014)"},{"key":"17_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-540-71039-4_4","volume-title":"Fast Software Encryption","author":"V Lyubashevsky","year":"2008","unstructured":"Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: a modest proposal for FFT hashing. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 54\u201372. Springer, Heidelberg (2008). doi:\n                      10.1007\/978-3-540-71039-4_4"},{"key":"17_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-540-78440-1_10","volume-title":"Public Key Cryptography \u2013 PKC 2008","author":"V Lyubashevsky","year":"2008","unstructured":"Lyubashevsky, V.: Lattice-based identification schemes secure under active attacks. In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 162\u2013179. Springer, Heidelberg (2008). doi:\n                      10.1007\/978-3-540-78440-1_10"},{"key":"17_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1007\/978-3-642-10366-7_35","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"V Lyubashevsky","year":"2009","unstructured":"Lyubashevsky, V.: Fiat-shamir with aborts: applications to lattice and factoring-based signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 598\u2013616. Springer, Heidelberg (2009). doi:\n                      10.1007\/978-3-642-10366-7_35"},{"key":"17_CR19","unstructured":"Reingold, O.: Private communication to the authors, July 2016"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Vadhan, S.: Pseudorandomness. Now publishers (2012)","DOI":"10.1561\/9781601985958"},{"key":"17_CR21","unstructured":"Z\u00e9mor, G.: Private communication to the authors, July 2016"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2017"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-56620-7_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T00:08:20Z","timestamp":1586477300000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-56620-7_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319566191","9783319566207"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-56620-7_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"1 April 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 April 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 May 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"36","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt2017.di.ens.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}