{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T10:58:55Z","timestamp":1778065135308,"version":"3.51.4"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032018830","type":"print"},{"value":"9783032018847","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-032-01884-7_19","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T09:31:18Z","timestamp":1755336678000},"page":"589-618","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Lower Bounds for\u00a0Garbled Circuits from\u00a0Shannon-Type Information Inequalities"],"prefix":"10.1007","author":[{"given":"Jake","family":"Januzelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mike","family":"Rosulek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lawrence","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"key":"19_CR1","unstructured":"Baek, C.,\u00a0Kim, T.: Can we beat three halves lower bound?: (Im)possibility of reducing communication cost for garbled circuits. Cryptology ePrint Archive, Report 2024\/803 (2024)"},{"key":"19_CR2","first-page":"565","volume-title":"ACM CCS 2016","author":"M Ball","year":"2016","unstructured":"Ball, M., Malkin, T., Rosulek, M.: Garbling gadgets for Boolean and arithmetic circuits. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 565\u2013577. ACM Press (2016)"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Beaver, D.,\u00a0Micali, S.,\u00a0Rogaway, P.: The round complexity of secure protocols (extended abstract). In: 22nd ACM STOC, pp. 503\u2013513. ACM Press (1990)","DOI":"10.1145\/100216.100287"},{"key":"19_CR4","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/978-3-642-00457-5_32","volume-title":"TCC 2009","author":"A Beimel","year":"2009","unstructured":"Beimel, A., Orlov, I.: Secret sharing and non-Shannon information inequalities. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 539\u2013557. Springer, Berlin, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00457-5_32"},{"key":"19_CR5","first-page":"784","volume-title":"ACM CCS 2012","author":"M Bellare","year":"2012","unstructured":"Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Yu, T., Danezis, G., Gligor, V.D. (eds.) ACM CCS 2012, pp. 784\u2013796. ACM Press (2012)"},{"key":"19_CR6","unstructured":"Cover, T.M.: Elements of Information Theory. Wiley (1999)"},{"key":"19_CR7","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BFb0053420","volume-title":"EUROCRYPT\u201994","author":"L Csirmaz","year":"1995","unstructured":"Csirmaz, L.: The size of a share must be large. In: De Santis, A. (ed.) EUROCRYPT\u201994. LNCS, vol. 950, pp. 13\u201322. Springer, Berlin, Heidelberg (1995). https:\/\/doi.org\/10.1007\/BFb0053420"},{"key":"19_CR8","unstructured":"Fan, L.,\u00a0Lu, Z., Zhou, H.-S.: Column-wise garbling, and how to go beyond the linear model. Cryptology ePrint Archive, Report 2024\/415 (2024)"},{"key":"19_CR9","unstructured":"Forrest, J., et al. COIN-OR\/Clp: Release releases\/1.17.9 (2023)"},{"key":"19_CR10","series-title":"Part II, volume 9057 of LNCS","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-662-46803-6_7","volume-title":"EUROCRYPT 2015","author":"TK Frederiksen","year":"2015","unstructured":"Frederiksen, T.K., Nielsen, J.B., Orlandi, C.: Privacy-free garbled circuits with applications to efficient zero-knowledge. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. Part II, volume 9057 of LNCS, pp. 191\u2013219. Springer, Berlin, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46803-6_7"},{"key":"19_CR11","unstructured":"Gl\u00e4\u00dfle, T.: Citip: information theoretic inequality prover (2015). https:\/\/github.com\/coldfix\/Citip"},{"key":"19_CR12","first-page":"567","volume-title":"ACM CCS 2015","author":"S Gueron","year":"2015","unstructured":"Gueron, S., Lindell, Y., Nof, A., Pinkas, B.: Fast garbling of circuits under standard assumptions. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015, pp. 567\u2013578. ACM Press (2015)"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R.: A personal view of average-case complexity. In: Proceedings of the Tenth Annual Structure in Complexity Theory Conference, Minneapolis, Minnesota, USA, June 19\u201322, 1995, pp. 134\u2013147 (1995)","DOI":"10.1109\/SCT.1995.514853"},{"key":"19_CR14","series-title":"Part II, volume 10032 of LNCS","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1007\/978-3-662-53890-6_32","volume-title":"ASIACRYPT 2016","author":"C Kempka","year":"2016","unstructured":"Kempka, C., Kikuchi, R., Suzuki, K.: How to circumvent the two-ciphertext lower bound for linear garbling schemes. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. Part II, volume 10032 of LNCS, pp. 967\u2013997. Springer, Berlin, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53890-6_32"},{"key":"19_CR15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/11593447_8","volume-title":"ASIACRYPT 2005","author":"V Kolesnikov","year":"2005","unstructured":"Kolesnikov, V.: Gate evaluation secret sharing and secure one-round two-party computation. In: Roy, B.K. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 136\u2013155. Springer, Berlin, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11593447_8"},{"key":"19_CR16","series-title":"Part II, volume 5126 of LNCS","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/978-3-540-70583-3_40","volume-title":"ICALP 2008","author":"V Kolesnikov","year":"2008","unstructured":"Kolesnikov, V., Schneider, T.: Improved garbled circuit: free XOR gates and applications. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. Part II, volume 5126 of LNCS, pp. 486\u2013498. Springer, Berlin, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70583-3_40"},{"key":"19_CR17","series-title":"Part I, volume 10401 of LNCS","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-319-63688-7_7","volume-title":"CRYPTO 2017","author":"Y Kondi","year":"2017","unstructured":"Kondi, Y., Patra, A.: Privacy-free garbled circuits for formulas: size zero and information-theoretic. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. Part I, volume 10401 of LNCS, pp. 188\u2013222. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_7"},{"key":"19_CR18","unstructured":"Li, R., Guo, C., Wang, X.: Towards optimal garbled circuits in the standard model. Cryptology ePrint Archive, Paper 2024\/1907 (2024)"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"Naor, M.,\u00a0Pinkas, B.,\u00a0Sumner, R.: Privacy preserving auctions and mechanism design. In: Proceedings of the 1st ACM Conference on Electronic Commerce, pp. 129\u2013139. ACM, New York, NY, USA (1999)","DOI":"10.1145\/336992.337028"},{"key":"19_CR20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/978-3-642-12200-2_31","volume-title":"LATIN 2010","author":"C Padr\u00f3","year":"2010","unstructured":"Padr\u00f3, C., V\u00e1zquez, L.: Finding lower bounds on the complexity of secret sharing schemes by linear programming. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 344\u2013355. Springer, Berlin, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-12200-2_31"},{"key":"19_CR21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-10366-7_15","volume-title":"ASIACRYPT 2009","author":"B Pinkas","year":"2009","unstructured":"Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure two-party computation is practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 250\u2013267. Springer, Berlin, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10366-7_15"},{"key":"19_CR22","unstructured":"Pulikkoonattu, R.,\u00a0Perron, E.,\u00a0Diggavi, S.: Xitip: information theoretic inequalities prover (2007). https:\/\/xitip.epfl.ch\/"},{"key":"19_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/978-3-030-84242-0_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"M Rosulek","year":"2021","unstructured":"Rosulek, M., Roy, L.: Three halves make a whole? Beating the half-gates lower bound for garbled circuits. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 94\u2013124. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84242-0_5"},{"issue":"10","key":"19_CR24","doi-asserted-by":"publisher","first-page":"102202","DOI":"10.1063\/1.4987135","volume":"58","author":"ME Shirokov","year":"2017","unstructured":"Shirokov, M.E.: Tight uniform continuity bounds for the quantum conditional mutual information, for the holevo quantity, and for capacities of quantum channels. J. Math. Phys. 58(10), 102202 (2017)","journal-title":"J. Math. Phys."},{"key":"19_CR25","unstructured":"Wang, Y., Malluhi, Q.M.: Reducing garbled circuit size while preserving circuit gate privacy. Cryptology ePrint Archive, Report 2017\/041 (2017)"},{"issue":"1","key":"19_CR26","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s00220-016-2609-8","volume":"347","author":"A Winter","year":"2016","unstructured":"Winter, A.: Tight uniform continuity bounds for quantum entropies: conditional entropy, relative entropy distance and energy constraints. Commun. Math. Phys. 347(1), 291\u2013313 (2016)","journal-title":"Commun. Math. Phys."},{"key":"19_CR27","unstructured":"Xu, F.,\u00a0Hu, H.,\u00a0Xu, C.: Bitwise garbling schemes \u2014 a model with $$\\frac{3}{2}\\kappa $$-bit lower bound of ciphertexts. Cryptology ePrint Archive, Paper 2024\/1532 (2024)"},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162\u2013167. IEEE Computer Society Press (1986)","DOI":"10.1109\/SFCS.1986.25"},{"key":"19_CR29","series-title":"Part II, volume 9057 of LNCS","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/978-3-662-46803-6_8","volume-title":"EUROCRYPT 2015","author":"S Zahur","year":"2015","unstructured":"Zahur, S., Rosulek, M., Evans, D.: Two halves make a whole - reducing data transfer in garbled circuits using half gates. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. Part II, volume 9057 of LNCS, pp. 220\u2013250. Springer, Berlin, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46803-6_8"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-01884-7_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T14:59:11Z","timestamp":1757429951000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01884-7_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783032018830","9783032018847"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01884-7_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"17 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"45","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}