{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T03:23:22Z","timestamp":1768965802647,"version":"3.49.0"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,4,15]],"date-time":"2017-04-15T00:00:00Z","timestamp":1492214400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100021796","name":"Check Point Institute for Information Security","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100021796","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Israel Ministry of Science and Technology","award":["3-9094"],"award-info":[{"award-number":["3-9094"]}]},{"name":"GIF","award":["1152\/2011"],"award-info":[{"award-number":["1152\/2011"]}]},{"name":"ERC starting","award":["639813 ERC-CLC"],"award-info":[{"award-number":["639813 ERC-CLC"]}]},{"name":"ISF","award":["1155\/11"],"award-info":[{"award-number":["1155\/11"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>\n            We study the possibility of computing cryptographic primitives in a fully black-box arithmetic model over a finite field\n            <jats:bold>F<\/jats:bold>\n            . In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits that make only a black-box use of the underlying field, and the adversary has a full (non-black-box) access to the field. This model captures many standard information-theoretic constructions.\n          <\/jats:p>\n          <jats:p>We prove several positive and negative results in this model for various cryptographic tasks. On the positive side, we show that, under coding-related intractability assumptions, computational primitives like commitment schemes, public-key encryption, oblivious transfer, and general secure two-party computation can be implemented in this model. On the negative side, we prove that garbled circuits, additively homomorphic encryption, and secure computation with low online complexity cannot be achieved in this model. Our results reveal a qualitative difference between the standard Boolean model and the arithmetic model, and explain, in retrospect, some of the limitations of previous constructions.<\/jats:p>","DOI":"10.1145\/3046675","type":"journal-article","created":{"date-parts":[[2017,4,17]],"date-time":"2017-04-17T12:26:58Z","timestamp":1492432018000},"page":"1-74","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Arithmetic Cryptography"],"prefix":"10.1145","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4792-369X","authenticated-orcid":false,"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[{"name":"Tel Aviv University"}]},{"given":"Jonathan","family":"Avron","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}]},{"given":"Chris","family":"Brzuska","sequence":"additional","affiliation":[{"name":"Technical University of Hamburg"}]}],"member":"320","published-online":{"date-parts":[[2017,4,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374481"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01001-9_2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.35"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.20"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0211-8"},{"key":"e_1_2_1_8_1","volume-title":"Andrew Chi-Chih Yao (Ed.)","author":"Applebaum Benny","unstructured":"Benny Applebaum , Yuval Ishai , and Eyal Kushilevitz . 2010. Cryptography by cellular automata or how fast can complexity emerge in nature? In 1st Innovations in Computer Science , Andrew Chi-Chih Yao (Ed.) . Tsinghua University Press , 1--19. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. 2010. Cryptography by cellular automata or how fast can complexity emerge in nature? In 1st Innovations in Computer Science, Andrew Chi-Chih Yao (Ed.). Tsinghua University Press, 1--19."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.40"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40084-1_10"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44750-4_8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382279"},{"key":"e_1_2_1_15_1","volume-title":"20th Annual ACM Symposium on Theory of Computing. ACM Press, 1--10","author":"Ben-Or Michael","year":"1988","unstructured":"Michael Ben-Or , Shafi Goldwasser , and Avi Wigderson . 1988 . Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract) . In 20th Annual ACM Symposium on Theory of Computing. ACM Press, 1--10 . Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In 20th Annual ACM Symposium on Theory of Computing. ACM Press, 1--10."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20465-4_11"},{"key":"e_1_2_1_17_1","volume-title":"Lipton","author":"Blum Avrim","year":"1993","unstructured":"Avrim Blum , Merrick L. Furst , Michael J. Kearns , and Richard J . Lipton . 1993 . Cryptographic primitives based on hard learning problems. In Advances in Cryptology -- CRYPTO\u201993 (Lecture Notes in Computer Science), Douglas R. Stinson (Ed.), Vol. 773 . Springer , 278--291. Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. 1993. Cryptographic primitives based on hard learning problems. In Advances in Cryptology -- CRYPTO\u201993 (Lecture Notes in Computer Science), Douglas R. Stinson (Ed.), Vol. 773. Springer, 278--291."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.72"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.12"},{"key":"e_1_2_1_21_1","volume-title":"20th Annual ACM Symposium on Theory of Computing. ACM Press, 11--19","author":"Chaum David","year":"1988","unstructured":"David Chaum , Claude Cr\u00e9peau , and Ivan Damg\u00e5rd . 1988 . Multiparty unconditionally secure protocols (extended abstract) . In 20th Annual ACM Symposium on Theory of Computing. ACM Press, 11--19 . David Chaum, Claude Cr\u00e9peau, and Ivan Damg\u00e5rd. 1988. Multiparty unconditionally secure protocols (extended abstract). In 20th Annual ACM Symposium on Theory of Computing. ACM Press, 11--19."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44987-6_18"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.7146\/brics.v9i8.21726"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-39200-9_37"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_38"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36178-2_6"},{"key":"e_1_2_1_27_1","volume-title":"Advances in Cryptology -- CRYPTO\u201991 (Lecture Notes in Computer Science)","author":"Desmedt Yvo","unstructured":"Yvo Desmedt and Yair Frankel . 1991. Shared generation of authenticators and signatures (extended abstract) . In Advances in Cryptology -- CRYPTO\u201991 (Lecture Notes in Computer Science) , Joan Feigenbaum (Ed.), Vol. 576 . Springer , 457--469. Yvo Desmedt and Yair Frankel. 1991. Shared generation of authenticators and signatures (extended abstract). In Advances in Cryptology -- CRYPTO\u201991 (Lecture Notes in Computer Science), Joan Feigenbaum (Ed.), Vol. 576. Springer, 457--469."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/060651380"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0258-4"},{"key":"e_1_2_1_30_1","volume-title":"Vadhan","author":"Dvir Zeev","year":"2011","unstructured":"Zeev Dvir , Dan Gutfreund , Guy N. Rothblum , and Salil P . Vadhan . 2011 . On approximating the entropy of polynomial mappings. In 2nd Innovations in Computer Science (ICS\u2019 10). 460--475. Zeev Dvir, Dan Gutfreund, Guy N. Rothblum, and Salil P. Vadhan. 2011. On approximating the entropy of polynomial mappings. In 2nd Innovations in Computer Science (ICS\u201910). 460--475."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1993.1022"},{"key":"e_1_2_1_32_1","volume-title":"Advances in Cryptology -- CRYPTO\u201984 (Lecture Notes in Computer Science)","author":"ElGamal Taher","unstructured":"Taher ElGamal . 1984. A public key cryptosystem and a signature scheme based on discrete logarithms . In Advances in Cryptology -- CRYPTO\u201984 (Lecture Notes in Computer Science) , G. R. Blakley and David Chaum (Eds.), Vol. 196 . Springer , 10--18. Taher ElGamal. 1984. A public key cryptosystem and a signature scheme based on discrete logarithms. In Advances in Cryptology -- CRYPTO\u201984 (Lecture Notes in Computer Science), G. R. Blakley and David Chaum (Eds.), Vol. 196. Springer, 10--18."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195408"},{"key":"e_1_2_1_34_1","volume-title":"Franklin and Stuart Haber","author":"Matthew","year":"1993","unstructured":"Matthew K. Franklin and Stuart Haber . 1993 . Joint encryption and message-efficient secure computation. In Advances in Cryptology -- CRYPTO\u201993 (Lecture Notes in Computer Science), Douglas R. Stinson (Ed.), Vol. 773 . Springer , 266--277. Matthew K. Franklin and Stuart Haber. 1993. Joint encryption and message-efficient secure computation. In Advances in Cryptology -- CRYPTO\u201993 (Lecture Notes in Computer Science), Douglas R. Stinson (Ed.), Vol. 773. Springer, 266--277."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_2_1_37_1","volume-title":"Advances in Cryptology -- CRYPTO\u201910 (Lecture Notes in Computer Science)","author":"Gentry Craig","unstructured":"Craig Gentry , Shai Halevi , and Vinod Vaikuntanathan . 2010. i-Hop homomorphic encryption and rerandomizable Yao circuits . In Advances in Cryptology -- CRYPTO\u201910 (Lecture Notes in Computer Science) , Tal Rabin (Ed.), Vol. 6223 . Springer , 155--172. Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. 2010. i-Hop homomorphic encryption and rerandomizable Yao circuits. In Advances in Cryptology -- CRYPTO\u201910 (Lecture Notes in Computer Science), Tal Rabin (Ed.), Vol. 6223. Springer, 155--172."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_55"},{"key":"e_1_2_1_39_1","volume-title":"Foundations of Cryptography: Basic Tools","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2001. Foundations of Cryptography: Basic Tools . Vol. 1 . Cambridge University Press , Cambridge, UK . xix + 372 pages. Oded Goldreich. 2001. Foundations of Cryptography: Basic Tools. Vol. 1. Cambridge University Press, Cambridge, UK. xix + 372 pages."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21917"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_2_1_44_1","volume-title":"19th Annual ACM Symposium on Theory of Computing, Alfred Aho (Ed.). ACM Press, 218--229","author":"Goldreich Oded","year":"1987","unstructured":"Oded Goldreich , Silvio Micali , and Avi Wigderson . 1987 . How to play any mental game or a completeness theorem for protocols with honest majority . In 19th Annual ACM Symposium on Theory of Computing, Alfred Aho (Ed.). ACM Press, 218--229 . Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to play any mental game or a completeness theorem for protocols with honest majority. In 19th Annual ACM Symposium on Theory of Computing, Alfred Aho (Ed.). ACM Press, 218--229."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766262"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_2_1_48_1","series-title":"Cryptology and Information Security Series","volume-title":"Randomization techniques for secure computation","author":"Ishai Yuval","unstructured":"Yuval Ishai . 2012. Randomization techniques for secure computation . In Secure Multi-Party Computation, Manoj Prabhakaran and Amit Sahai (Eds.). Cryptology and Information Security Series , Vol. 10 . IOS Press , Amsterdam , 222--248. Yuval Ishai. 2012. Randomization techniques for secure computation. In Secure Multi-Party Computation, Manoj Prabhakaran and Amit Sahai (Eds.). Cryptology and Information Security Series, Vol. 10. IOS Press, Amsterdam, 222--248."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892118"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_34"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30576-7_24"},{"key":"e_1_2_1_52_1","volume-title":"Advances in Cryptology -- CRYPTO\u201908 (Lecture Notes in Computer Science)","author":"Ishai Yuval","unstructured":"Yuval Ishai , Manoj Prabhakaran , and Amit Sahai . 2008. Founding cryptography on oblivious transfer - efficiently . In Advances in Cryptology -- CRYPTO\u201908 (Lecture Notes in Computer Science) , David Wagner (Ed.), Vol. 5157 . Springer , 572--591. Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. 2008. Founding cryptography on oblivious transfer - efficiently. In Advances in Cryptology -- CRYPTO\u201908 (Lecture Notes in Computer Science), David Wagner (Ed.), Vol. 5157. Springer, 572--591."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_18"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34961-4_40"},{"key":"e_1_2_1_55_1","volume-title":"Introduction to Modern Cryptography","author":"Katz Jonathan","unstructured":"Jonathan Katz and Yehuda Lindell . 2008. Introduction to Modern Cryptography . Chapman and Hall\/CRC. Jonathan Katz and Yehuda Lindell. 2008. Introduction to Modern Cryptography. Chapman and Hall\/CRC."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.37"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20465-4_3"},{"key":"e_1_2_1_58_1","volume-title":"10th IMA International Conference on Cryptography and Coding (Lecture Notes in Computer Science), Nigel P. Smart (Ed.)","volume":"3796","author":"Maurer Ueli M.","year":"2005","unstructured":"Ueli M. Maurer . 2005 . Abstract models of computation in cryptography (invited paper) . In 10th IMA International Conference on Cryptography and Coding (Lecture Notes in Computer Science), Nigel P. Smart (Ed.) , Vol. 3796 . Springer, 1--12. Ueli M. Maurer. 2005. Abstract models of computation in cryptography (invited paper). In 10th IMA International Conference on Cryptography and Coding (Lecture Notes in Computer Science), Nigel P. Smart (Ed.), Vol. 3796. Springer, 1--12."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0054118"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196774"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301312"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27660-6_9"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195134"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-69053-0_18"},{"key":"e_1_2_1_68_1","first-page":"3","article-title":"Arithmetic circuits: A survey of recent results and open questions","volume":"5","author":"Shpilka Amir","year":"2010","unstructured":"Amir Shpilka and Amir Yehudayoff . 2010 . Arithmetic circuits: A survey of recent results and open questions . Foundations and Trends in Theoretical Computer Science 5 , 3 -- 4 (2010), 207--388. Amir Shpilka and Amir Yehudayoff. 2010. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5, 3--4 (2010), 207--388.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_2_1_69_1","unstructured":"Atri Rudra Venkatesan Guruswami and Madhu Sudan. 2014. Essential Coding Theory (Unpublished Book). http:\/\/www.cse.buffalo.edu\/&sim;atri\/courses\/coding-theory\/book\/.  Atri Rudra Venkatesan Guruswami and Madhu Sudan. 2014. Essential Coding Theory (Unpublished Book). http:\/\/www.cse.buffalo.edu\/&sim;atri\/courses\/coding-theory\/book\/."},{"key":"e_1_2_1_70_1","volume-title":"23rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 80--91","author":"Chi-Chih Yao Andrew","year":"1982","unstructured":"Andrew Chi-Chih Yao . 1982 . Theory and applications of trapdoor functions (extended abstract) . In 23rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 80--91 . Andrew Chi-Chih Yao. 1982. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 80--91."},{"key":"e_1_2_1_71_1","volume-title":"27th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 162--167","author":"Chi-Chih Yao Andrew","year":"1986","unstructured":"Andrew Chi-Chih Yao . 1986 . How to generate and exchange secrets (extended abstract) . In 27th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 162--167 . Andrew Chi-Chih Yao. 1986. How to generate and exchange secrets (extended abstract). In 27th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 162--167."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3046675","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3046675","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:50:24Z","timestamp":1750218624000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3046675"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,15]]},"references-count":72,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/3046675"],"URL":"https:\/\/doi.org\/10.1145\/3046675","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,15]]},"assertion":[{"value":"2015-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}