{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:40:00Z","timestamp":1787341200576,"version":"build-2736575974"},"reference-count":56,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>Randomized encodings of functions can be used to replace a \u201ccomplex\u201d function $f(x)$ by a \u201csimpler\u201d randomized mapping $\\hat{f}(x;r)$ whose output distribution on an input $x$ encodes the value of $f(x)$ and hides any other information about $x$. One desirable feature of randomized encodings is low online complexity. That is, the goal is to obtain a randomized encoding $\\hat{f}$ of $f$ in which most of the output can be precomputed and published before seeing the input $x$. When the input $x$ is available, it remains to publish only a short string $\\hat{x}$, where the online complexity of computing $\\hat{x}$ is independent of (and is typically much smaller than) the complexity of computing $f$. Yao's garbled circuit construction gives rise to such randomized encodings in which the online part $\\hat{x}$ consists of $n$ encryption keys of length $\\kappa$ each, where $n=|x|$ and $\\kappa$ is a security parameter. Thus, the online rate $|\\hat{x}|\/|x|$ of this encoding is proportional to the security parameter $\\kappa$. In this paper, we show that the online rate can be dramatically improved. Specifically, we show how to encode any polynomial-time computable function $f:\\{0,1\\}^n\\to\\{0,1\\}^{m(n)}$ with online rate of $1+o(1)$ and with nearly linear online computation. More concretely, the online part $\\hat{x}$ consists of an $n$-bit string and a single encryption key. These constructions can be based on the decisional Diffie--Hellman (DDH) assumption, the learning with errors (LWE) assumption, or the RSA assumption. We also present a variant of this result which applies to arithmetic formulas, where the encoding only makes use of arithmetic operations, as well as several negative results which complement our positive results. Our positive results can lead to efficiency improvements in most contexts where randomized encodings of functions are used. We demonstrate this by presenting several concrete applications. These include protocols for secure multiparty computation and for noninteractive verifiable computation in the preprocessing model which achieve, for the first time, an optimal online communication complexity, as well as noninteractive zero-knowledge proofs which simultaneously minimize the online communication and the prover's online computation.<\/jats:p>","DOI":"10.1137\/130929643","type":"journal-article","created":{"date-parts":[[2015,4,14]],"date-time":"2015-04-14T13:37:41Z","timestamp":1429018661000},"page":"433-466","source":"Crossref","is-referenced-by-count":11,"title":["Encoding Functions with Constant Online Rate, or How to Compress Garbled Circuit Keys"],"prefix":"10.1137","volume":"44","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eyal","family":"Kushilevitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brent","family":"Waters","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,4,14]]},"reference":[{"key":"atypb1","first-page":"527","author":"Applebaum B.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb2","first-page":"595","author":"Applebaum B.","year":"2009","journal-title":"Berlin"},{"key":"atypb3","first-page":"45","author":"Applebaum B.","year":"2011","journal-title":"Beijing"},{"key":"atypb4","unstructured":"B. Applebaum, Y. Ishai, and E. Kushilevitz,\n                      Cryptography in NC$^0$\n                      , in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 166-175."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0211-8"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"B. Applebaum, Y. Ishai, and E. Kushilevitz,\n                      From secrecy to soundness: Efficient verification via secure computation\n                      , in Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), Part I, Lecture Notes in Comput. Sci. 6198, S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, and P. G. Spirakis, eds., Springer, Berlin, 2010, pp. 152-163.","DOI":"10.1007\/978-3-642-14165-2_14"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"B. Applebaum, Y. Ishai, and E. Kushilevitz,\n                      How to garble arithmetic circuits\n                      , in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, R. Ostrovsky, ed., 2011, pp. 120-129.","DOI":"10.1109\/FOCS.2011.40"},{"key":"atypb8","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, and B. Waters,\n                      Encoding Functions with Constant Online Rate or How to Compress Garbled Circuits Keys\n                      , Cryptology ePrint Archive, Report 2012\/693, 2012; available online from http:\/\/eprint.iacr.org\/2012\/693."},{"key":"atypb9","first-page":"166","author":"Applebaum B.","year":"2013","journal-title":"Heidelberg"},{"key":"atypb10","first-page":"423","author":"Barak B.","year":"2010","journal-title":"Berlin"},{"key":"atypb11","first-page":"97","author":"Beaver D.","year":"1995","journal-title":"Berlin"},{"key":"atypb12","first-page":"134","author":"Bellare M.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"M. Bellare, V. T. Hoang, and P. Rogaway,\n                      Foundations of garbled circuits\n                      , in Proceedings of the 19th ACM Conference on Computer and Communications Security, T. Yu, G. Danezis, and V. D. Gligor, eds., 2012, pp. 784-796.","DOI":"10.1145\/2382196.2382279"},{"key":"atypb14","first-page":"169","author":"Bendlin R.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb15","first-page":"533","author":"Boneh D.","year":"2014","journal-title":"Heidelberg"},{"key":"atypb16","first-page":"253","author":"Boneh D.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"C. Cachin, J. Camenisch, J. Kilian, and J. M\u00fcller,\n                      One-round secure computation and secure autonomous mobile agents\n                      , in Proceedings of the 27th International Colloquium on Automata, Languages and Programming (ICALP 2000), Lecture Notes in Comput. Sci. 1853, U. Montanari, J. D. P. Rolim, and E. Welzl, eds., Springer, Berlin, 2000, pp. 512-523.","DOI":"10.1007\/3-540-45022-X_43"},{"key":"atypb18","first-page":"483","author":"Chung K.-M.","year":"2010","journal-title":"Berlin"},{"key":"atypb19","first-page":"596","author":"Cramer R.","year":"2003","journal-title":"Berlin"},{"key":"atypb20","first-page":"501","author":"Ishai I.","year":"2006","journal-title":"Berlin"},{"key":"atypb21","first-page":"643","author":"I.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02254791"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"U. Feige, J. Kilian, and M. Naor,\n                      A minimal model for secure computation (extended abstract)\n                      , in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994, pp. 554-563.","DOI":"10.1145\/195058.195408"},{"key":"atypb24","first-page":"465","author":"Gennaro R.","year":"2010","journal-title":"Berlin"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"C. Gentry,\n                      Fully homomorphic encryption using ideal lattices\n                      , in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, M. Mitzenmacher, ed., 2009, pp. 169-178.","DOI":"10.1145\/1536414.1536440"},{"key":"atypb26","unstructured":"H. Gilbert, M. J. B. Robshaw, and Y. Seurin,\n                      How to encrypt with the LPN problem\n                      , in Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Part II, Lecture Notes in Comput. Sci. 5126, L. Aceto, I. Damg\\aard, L. A. Goldberg, M. M. Halld\u00f3rsson, A. Ing\u00f3lfsd\u00f3ttir, and I. Walukiewicz, eds., Springer, Berlin, 2008, pp. 679-690."},{"key":"atypb27","unstructured":"O. Goldreich,\n                      Foundations of Cryptography: Basic Applications\n                      , Vol. 2, Cambridge University Press, Cambridge, UK, 2004."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-002-0169-0"},{"key":"atypb29","first-page":"536","author":"Goldwasser S.","year":"2013","journal-title":"Heidelberg"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, Y. T. Kalai, R. A. Popa, V. Vaikuntanathan, and N. Zeldovich,\n                      Reusable garbled circuits and succinct functional encryption\n                      , in Proceedings of the 45th Annual ACM Symposium on Theory of Computing, D. Boneh, T. Roughgarden, and J. Feigenbaum, eds., 2013, pp. 555-564.","DOI":"10.1145\/2488608.2488678"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, Y. T. Kalai, and G. N. Rothblum,\n                      Delegating computation: Interactive proofs for muggles\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, R. E. Ladner and C. Dwork, eds., 2008, pp. 113-122.","DOI":"10.1145\/1374376.1374396"},{"key":"atypb32","first-page":"39","author":"Goldwasser S.","year":"2008","journal-title":"Berlin"},{"key":"atypb33","first-page":"162","author":"Gorbunov S.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb34","first-page":"308","author":"Goyal V.","year":"2010","journal-title":"Berlin"},{"key":"atypb35","unstructured":"J. Groth,\n                      Minimizing Non-interactive Zero-Knowledge Proofs Using Fully Homomorphic Encryption\n                      , Cryptology ePrint Archive, Report 2011\/012, 2011; available online from http:\/\/eprint.iacr.org\/2011\/012."},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"D. Harnik and M. Naor,\n                      On the compressibility of NP instances and cryptographic applications\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 719-728.","DOI":"10.1109\/FOCS.2006.54"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"Y. Ishai and E. Kushilevitz,\n                      Randomizing polynomials: A new representation with applications to round-efficient secure computation\n                      , in Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2000, pp. 294-304.","DOI":"10.1109\/SFCS.2000.892118"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"Y. Ishai and E. Kushilevitz,\n                      Perfect constant-round secure computation via perfect randomizing polynomials\n                      , in Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP 2002), Lecture Notes in Comput. Sci. 2380, P. Widmayer, F. T. Ruiz, R. M. Bueno, M. Hennessy, S. Eidenbenz, and R. Conejo, eds., Springer, Berlin, 2002, pp. 244-256.","DOI":"10.1007\/3-540-45465-9_22"},{"key":"atypb40","first-page":"600","author":"Ishai Y.","year":"2013","journal-title":"Berlin"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai,\n                      Cryptography with constant computational overhead\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, R. E. Ladner and C. Dwork, eds., 2008, pp. 433-442.","DOI":"10.1145\/1374376.1374438"},{"key":"atypb42","first-page":"572","author":"Ishai Y.","year":"2008","journal-title":"Berlin"},{"key":"atypb43","first-page":"143","author":"Kalai Y. T.","year":"2009","journal-title":"Berlin"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"J. Kilian,\n                      Founding cryptography on oblivious transfer\n                      , in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 20-31.","DOI":"10.1145\/62212.62215"},{"key":"atypb45","first-page":"719","author":"Lu S.","year":"2013","journal-title":"Berlin"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365746"},{"key":"atypb47","first-page":"111","author":"Nielsen J. B.","year":"2002","journal-title":"Berlin"},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"C. Peikert,\n                      Public-key cryptosystems from the worst-case shortest vector problem: Extended abstract\n                      , in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, M. Mitzenmacher, ed., 2009, pp. 333-342.","DOI":"10.1145\/1536414.1536461"},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"O. Regev,\n                      On lattices, learning with errors, random linear codes, and cryptography\n                      , in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, H. N. Gabow and R. Fagin, eds., 2005, pp. 84-93.","DOI":"10.1145\/1060590.1060603"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"A. Sahai and H. Seyalioglu,\n                      Worry-free encryption: Functional encryption with public keys\n                      , in Proceedings of the 17th ACM Conference on Computer and Communications Security, E. Al-Shaer, A. D. Keromytis, and V. Shmatikov, eds., 2010, pp. 463-472.","DOI":"10.1145\/1866307.1866359"},{"key":"atypb52","doi-asserted-by":"crossref","unstructured":"T. Sander, A. Young, and M. Yung,\n                      Non-interactive cryptocomputing for NC$1$\n                      , in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 554-567.","DOI":"10.1109\/SFFCS.1999.814630"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1145\/357353.357357"},{"key":"atypb54","first-page":"355","author":"Shamir A.","year":"2001","journal-title":"Berlin"},{"key":"atypb55","unstructured":"R. Sion and B. Carbunar,\n                      On the practicality of private information retrieval\n                      , in Proceedings of the 14th Annual Network & Distributed System Security Symposium (NDSS 2007), The Internet Society, 2007."},{"key":"atypb56","doi-asserted-by":"crossref","unstructured":"A. C.C. Yao,\n                      How to generate and exchange secrets (extended abstract)\n                      , in Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, pp. 162-167.","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130929643","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:09:22Z","timestamp":1787339362000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130929643"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130929643"],"URL":"https:\/\/doi.org\/10.1137\/130929643","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}