{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:36:50Z","timestamp":1766281010716,"version":"3.41.0"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319783710"},{"type":"electronic","value":"9783319783727"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-319-78372-7_12","type":"book-chapter","created":{"date-parts":[[2018,3,30]],"date-time":"2018-03-30T06:13:04Z","timestamp":1522390384000},"page":"371-390","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On the Complexity of Simulating Auxiliary Input"],"prefix":"10.1007","author":[{"given":"Yi-Hsiu","family":"Chen","sequence":"first","affiliation":[]},{"given":"Kai-Min","family":"Chung","sequence":"additional","affiliation":[]},{"given":"Jyun-Jie","family":"Liao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,31]]},"reference":[{"issue":"1","key":"12_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theory Comput. 8(1), 121\u2013164 (2012)","journal-title":"Theory Comput."},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/978-3-642-22935-0_32","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S Artemenko","year":"2011","unstructured":"Artemenko, S., Shaltiel, R.: Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) APPROX\/RANDOM -2011. LNCS, vol. 6845, pp. 377\u2013388. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22935-0_32"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-662-46494-6_4","volume-title":"Theory of Cryptography","author":"K-M Chung","year":"2015","unstructured":"Chung, K.-M., Lui, E., Pass, R.: From weak to strong zero-knowledge and applications. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9014, pp. 66\u201392. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46494-6_4"},{"key":"12_CR4","unstructured":"49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, USA, 25\u201328 October 2008. IEEE Computer Society (2008)"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Dziembowski, S., Pietrzak, K.: Leakage-resilient cryptography. In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, USA, 25\u201328 October 2008 [DBL08], pp. 293\u2013302","DOI":"10.1109\/FOCS.2008.56"},{"issue":"2","key":"12_CR6","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s004930050052","volume":"19","author":"AM Frieze","year":"1999","unstructured":"Frieze, A.M., Kannan, R.: Quick approximation to matrices and applications. Combinatorica 19(2), 175\u2013220 (1999)","journal-title":"Combinatorica"},{"issue":"2","key":"12_CR7","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1006\/inco.1995.1136","volume":"121","author":"Y Freund","year":"1995","unstructured":"Freund, Y.: Boosting a weak learning algorithm by majority. Inf. Comput. 121(2), 256\u2013285 (1995)","journal-title":"Inf. Comput."},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Freund, Y., Schapire, R.E.: Game theory, on-line prediction and boosting. In: Blum, A., Kearns, M. (eds.) Proceedings of the Ninth Annual Conference on Computational Learning Theory, COLT 1996, Desenzano del Garda, Italy, 28 June\u20131 July 1996, pp. 325\u2013332. ACM (1996)","DOI":"10.1145\/238061.238163"},{"key":"12_CR9","unstructured":"Goldreich, O., Nisan, N., Wigderson, A.: On Yao\u2019s XOR-lemma. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 2, no. 50 (1995)"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Fortnow, L., Vadhan, S.P. (eds.) Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6\u20138 June 2011, pp. 99\u2013108. ACM (2011)","DOI":"10.1145\/1993636.1993651"},{"issue":"4","key":"12_CR11","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Holenstein, T.: Key agreement from weak bit agreement. In: Gabow, H.N., Fagin, R. (eds.) Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, 22\u201324 May 2005, pp. 664\u2013673. ACM (2005)","DOI":"10.1145\/1060590.1060689"},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4","volume-title":"Theory of Cryptography","year":"2016","unstructured":"Hirt, M., Smith, A. (eds.): TCC 2016-B. LNCS, vol. 9985. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53641-4"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, 23\u201325 October 1995, pp. 538\u2013545. IEEE Computer Society (1995)","DOI":"10.1109\/SFCS.1995.492584"},{"key":"12_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/978-3-642-54242-8_24","volume-title":"Theory of Cryptography","author":"D Jetchev","year":"2014","unstructured":"Jetchev, D., Pietrzak, K.: How to fake auxiliary input. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 566\u2013590. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54242-8_24"},{"issue":"1","key":"12_CR16","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s00037-011-0003-7","volume":"20","author":"C-J Lu","year":"2011","unstructured":"Lu, C.-J., Tsai, S.-C., Wu, H.-L.: Complexity of hard-core set proofs. Comput. Complex. 20(1), 145\u2013171 (2011)","journal-title":"Comput. Complex."},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Pietrzak, K., Sk\u00f3rski, M.: Pseudoentropy: lower-bounds for chain rules and transformations. In: Hirt and Smith [HS16], pp. 183\u2013203","DOI":"10.1007\/978-3-662-53641-4_8"},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"Roughgarden, T.: No-Regret Dynamics, pp. 230\u2013246. Cambridge University Press, Cambridge (2016)","DOI":"10.1017\/CBO9781316779309.018"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Reingold, O., Trevisan, L., Tulsiani, M., Vadhan, S.P.: Dense subsets of pseudorandom sets. In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, USA, 25\u201328 October 2008 [DBL08], pp. 76\u201385","DOI":"10.1109\/FOCS.2008.38"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"Sk\u00f3rski, M.: Simulating auxiliary inputs, revisited. In: Hirt and Smith [HS16], pp. 159\u2013179","DOI":"10.1007\/978-3-662-53641-4_7"},{"key":"12_CR21","unstructured":"Sk\u00f3rski, M.: A subgradient algorithm for computational distances and applications to cryptography. IACR Cryptology ePrint Archive, 2016:158 (2016)"},{"issue":"7","key":"12_CR22","doi-asserted-by":"publisher","first-page":"3122","DOI":"10.1137\/080735096","volume":"39","author":"R Shaltiel","year":"2010","unstructured":"Shaltiel, R., Viola, E.: Hardness amplification proofs require majority. SIAM J. Comput. 39(7), 3122\u20133154 (2010)","journal-title":"SIAM J. Comput."},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Trevisan, L., Tulsiani, M., Vadhan, S.P.: Regularity, boosting, and efficiently simulating every high-entropy distribution. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15\u201318 July 2009, pp. 126\u2013136. IEEE Computer Society (2009)","DOI":"10.1109\/CCC.2009.41"},{"key":"12_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-40041-4_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"S Vadhan","year":"2013","unstructured":"Vadhan, S., Zheng, C.J.: A uniform min-max theorem with applications in cryptography. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 93\u2013110. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40041-4_6"},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3\u20135 November 1982, pp. 80\u201391. IEEE Computer Society (1982)","DOI":"10.1109\/SFCS.1982.45"},{"key":"12_CR26","unstructured":"Zhang, J.: On the query complexity for showing dense model. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 18, p. 38 (2011)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2018"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-78372-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T04:00:12Z","timestamp":1751515212000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-78372-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319783710","9783319783727"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-78372-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"31 March 2018","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":"Tel Aviv","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Israel","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 May 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2018\/index.html","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"}]}}