{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T11:38:00Z","timestamp":1770982680866,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2015,1,11]],"date-time":"2015-01-11T00:00:00Z","timestamp":1420934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1155\/11"],"award-info":[{"award-number":["1155\/11"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"German-Israeli Foundation for Scientific Research and Development","award":["1152\/2011"],"award-info":[{"award-number":["1152\/2011"]}]},{"name":"Israel Ministry of Science and Technology","award":["3-9094"],"award-info":[{"award-number":["3-9094"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2015,1,11]]},"DOI":"10.1145\/2688073.2688114","type":"proceedings-article","created":{"date-parts":[[2015,1,12]],"date-time":"2015-01-12T20:42:45Z","timestamp":1421095365000},"page":"143-151","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Arithmetic Cryptography"],"prefix":"10.1145","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]},{"given":"Jonathan","family":"Avron","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]},{"given":"Christina","family":"Brzuska","sequence":"additional","affiliation":[{"name":"Microsoft Research Cambridge, Cambridge, England UK"}]}],"member":"320","published-online":{"date-parts":[[2015,1,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374481"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01001-9_2"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946338"},{"key":"e_1_3_2_1_4_1","first-page":"1","volume-title":"ICS 2010","author":"Applebaum B.","year":"2010","unstructured":"B. Applebaum , Y. Ishai , and E. Kushilevitz . Cryptography by cellular automata or how fast can complexity emerge in nature? In A. C.-C. Yao, editor , ICS 2010 , pages 1 -- 19 . Tsinghua University Press , Jan. 2010 . B. Applebaum, Y. Ishai, and E. Kushilevitz. Cryptography by cellular automata or how fast can complexity emerge in nature? In A. C.-C. Yao, editor, ICS 2010, pages 1--19. Tsinghua University Press, Jan. 2010."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.40"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"B.\n      Applebaum Y.\n      Ishai E.\n      Kushilevitz and \n      B.\n      Waters\n  . \n  Encoding functions with constant online rate or how to compress garbled circuits keys\n  . In R. Canetti and J. A. Garay editors CRYPTO \n  2013 Part II volume \n  8043\n   of \n  LNCS pages \n  166\n  --\n  184\n  . \n  Springer Aug. 2013.  B. Applebaum Y. Ishai E. Kushilevitz and B. Waters. Encoding functions with constant online rate or how to compress garbled circuits keys. In R. Canetti and J. A. Garay editors CRYPTO 2013 Part II volume 8043 of LNCS pages 166--184. Springer Aug. 2013.","DOI":"10.1007\/978-3-642-40084-1_10"},{"key":"e_1_3_2_1_7_1","first-page":"4","article-title":"Relativizations of the P =? NP question","year":"1975","unstructured":"Baker, Gill, and Solovay . Relativizations of the P =? NP question . SICOMP: SIAM Journal on Computing , 4 , 1975 . Baker, Gill, and Solovay. Relativizations of the P =? NP question. SICOMP: SIAM Journal on Computing, 4, 1975.","journal-title":"SICOMP: SIAM Journal on Computing"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"D.\n      Beaver\n    .\n  Precomputing oblivious transfer\n  . In D. Coppersmith editor CRYPTO'95 volume \n  963\n   of \n  LNCS pages \n  97\n  --\n  109\n  . \n  Springer Aug. \n  1995\n  .   D. Beaver. Precomputing oblivious transfer. In D. Coppersmith editor CRYPTO'95 volume 963 of LNCS pages 97--109. Springer Aug. 1995.","DOI":"10.1007\/3-540-44750-4_8"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382279"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"R.\n      Bendlin I.\n      Damg\u00e5rd C.\n      Orlandi and \n      S.\n      Zakarias\n  . \n  Semi-homomorphic encryption and multiparty computation\n  . In K. G. Paterson editor EUROCRYPT \n  2011 volume \n  6632\n   of \n  LNCS pages \n  169\n  --\n  188\n  . \n  Springer May 2011.   R. Bendlin I. Damg\u00e5rd C. Orlandi and S. Zakarias. Semi-homomorphic encryption and multiparty computation. In K. G. Paterson editor EUROCRYPT 2011 volume 6632 of LNCS pages 169--188. Springer May 2011.","DOI":"10.1007\/978-3-642-20465-4_11"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"A.\n      Blum M. L.\n      Furst M. J.\n      Kearns and \n      R. J.\n      Lipton\n  . \n  Cryptographic primitives based on hard learning problems\n  . In D. R. Stinson editor CRYPTO'93 volume \n  773\n   of \n  LNCS pages \n  278\n  --\n  291\n  . \n  Springer Aug. \n  1993\n  .   A. Blum M. L. Furst M. J. Kearns and R. J. Lipton. Cryptographic primitives based on hard learning problems. In D. R. Stinson editor CRYPTO'93 volume 773 of LNCS pages 278--291. Springer Aug. 1993.","DOI":"10.1007\/3-540-48329-2_24"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.72"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.12"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62214"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"R.\n      Cramer I.\n      Damg\u00e5rd and \n      J. B.\n      Nielsen\n  . \n  Multiparty computation from threshold homomorphic encryption\n  . In B. Pfitzmann editor EUROCRYPT \n  2001 volume \n  2045\n   of \n  LNCS pages \n  280\n  --\n  299\n  . \n  Springer May 2001.   R. Cramer I. Damg\u00e5rd and J. B. Nielsen. Multiparty computation from threshold homomorphic encryption. In B. Pfitzmann editor EUROCRYPT 2001 volume 2045 of LNCS pages 280--299. Springer May 2001.","DOI":"10.1007\/3-540-44987-6_18"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"R.\n      Cramer\n     and \n      S.\n      Fehr\n  . \n  Optimal black-box secret sharing over arbitrary Abelian groups\n  . In M. Yung editor CRYPTO \n  2002 volume \n  2442\n   of \n  LNCS pages \n  272\n  --\n  287\n  . \n  Springer Aug. 2002.   R. Cramer and S. Fehr. Optimal black-box secret sharing over arbitrary Abelian groups. In M. Yung editor CRYPTO 2002 volume 2442 of LNCS pages 272--287. Springer Aug. 2002.","DOI":"10.1007\/3-540-45708-9_18"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"R.\n      Cramer S.\n      Fehr Y.\n      Ishai and \n      E.\n      Kushilevitz\n  . \n  Efficient multi-party computation over rings\n  . In E. Biham editor EUROCRYPT \n  2003 volume \n  2656\n   of \n  LNCS pages \n  596\n  --\n  613\n  . \n  Springer May 2003.   R. Cramer S. Fehr Y. Ishai and E. Kushilevitz. Efficient multi-party computation over rings. In E. Biham editor EUROCRYPT 2003 volume 2656 of LNCS pages 596--613. Springer May 2003.","DOI":"10.1007\/3-540-39200-9_37"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"I.\n      Damg\u00e5rd V.\n      Pastro N. P.\n      Smart and \n      S.\n      Zakarias\n  . \n  Multiparty computation from somewhat homomorphic encryption\n  . In R. Safavi-Naini and R. Canetti editors CRYPTO \n  2012 volume \n  7417\n   of \n  LNCS pages \n  643\n  --\n  662\n  . \n  Springer Aug. 2012.  I. Damg\u00e5rd V. Pastro N. P. Smart and S. Zakarias. Multiparty computation from somewhat homomorphic encryption. In R. Safavi-Naini and R. Canetti editors CRYPTO 2012 volume 7417 of LNCS pages 643--662. Springer Aug. 2012.","DOI":"10.1007\/978-3-642-32009-5_38"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"A. W.\n      Dent\n    .\n  Adapting the weaknesses of the random oracle model to the generic group model\n  . In Y. Zheng editor ASIACRYPT \n  2002 volume \n  2501\n   of \n  LNCS pages \n  100\n  --\n  109\n  . \n  Springer Dec. 2002.   A. W. Dent. Adapting the weaknesses of the random oracle model to the generic group model. In Y. Zheng editor ASIACRYPT 2002 volume 2501 of LNCS pages 100--109. Springer Dec. 2002.","DOI":"10.1007\/3-540-36178-2_6"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Y.\n      Desmedt\n     and \n      Y.\n      Frankel\n  . \n  Shared generation of authenticators and signatures (extended abstract)\n  . In J. Feigenbaum editor CRYPTO'91 volume \n  576\n   of \n  LNCS pages \n  457\n  --\n  469\n  . \n  Springer Aug. \n  1991\n  .   Y. Desmedt and Y. Frankel. Shared generation of authenticators and signatures (extended abstract). In J. Feigenbaum editor CRYPTO'91 volume 576 of LNCS pages 457--469. Springer Aug. 1991.","DOI":"10.1007\/3-540-46766-1_37"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.26"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"T.\n      ElGamal\n    .\n  A public key cryptosystem and a signature scheme based on discrete logarithms\n  . In G. R. Blakley and D. Chaum editors CRYPTO'84 volume \n  196\n   of \n  LNCS pages \n  10\n  --\n  18\n  . \n  Springer Aug. \n  1984\n  .   T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In G. R. Blakley and D. Chaum editors CRYPTO'84 volume 196 of LNCS pages 10--18. Springer Aug. 1984.","DOI":"10.1007\/3-540-39568-7_2"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195408"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"M. K.\n      Franklin\n     and \n      S.\n      Haber\n  . \n  Joint encryption and message-efficient secure computation\n  . In D. R. Stinson editor CRYPTO'93 volume \n  773\n   of \n  LNCS pages \n  266\n  --\n  277\n  . \n  Springer Aug. \n  1993\n  .   M. K. Franklin and S. Haber. Joint encryption and message-efficient secure computation. In D. R. Stinson editor CRYPTO'93 volume 773 of LNCS pages 266--277. Springer Aug. 1993.","DOI":"10.1007\/3-540-48329-2_23"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"S.\n      Garg C.\n      Gentry and \n      S.\n      Halevi\n  . \n  Candidate multilinear maps from ideal lattices\n  . In T. Johansson and P. Q. Nguyen editors EUROCRYPT \n  2013 volume \n  7881\n   of \n  LNCS pages \n  1\n  --\n  17\n  . \n  Springer May 2013.  S. Garg C. Gentry and S. Halevi. Candidate multilinear maps from ideal lattices. In T. Johansson and P. Q. Nguyen editors EUROCRYPT 2013 volume 7881 of LNCS pages 1--17. Springer May 2013.","DOI":"10.1007\/978-3-642-38348-9_1"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_55"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"O.\n      Goldreich H.\n      Krawczyk and \n      M.\n      Luby\n  . \n  On the existence of pseudorandom generators\n  . In S. Goldwasser editor CRYPTO'88 volume \n  403\n   of \n  LNCS pages \n  146\n  --\n  162\n  . \n  Springer Aug. \n  1988\n  .   O. Goldreich H. Krawczyk and M. Luby. On the existence of pseudorandom generators. In S. Goldwasser editor CRYPTO'88 volume 403 of LNCS pages 146--162. Springer Aug. 1988.","DOI":"10.1007\/0-387-34799-2_12"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28420"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_3_2_1_35_1","series-title":"Cryptology and Information Security Series","first-page":"222","volume-title":"Secure Multi-Party Computation","author":"Ishai Y.","year":"2012","unstructured":"Y. Ishai . Randomization techniques for secure computation . In M. Prabhakaran and A. Sahai, editors, Secure Multi-Party Computation , volume 10 of Cryptology and Information Security Series , pages 222 -- 248 . IOS press , Amsterdam , 2012 . Y. Ishai. Randomization techniques for secure computation. In M. Prabhakaran and A. Sahai, editors, Secure Multi-Party Computation, volume 10 of Cryptology and Information Security Series, pages 222--248. IOS press, Amsterdam, 2012."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796556"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_34"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_32"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_18"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"E.\n      Kiltz K.\n      Pietrzak D.\n      Cash A.\n      Jain and \n      D.\n      Venturi\n  . \n  Efficient authentication from hard learning problems\n  . In K. G. Paterson editor EUROCRYPT \n  2011 volume \n  6632\n   of \n  LNCS pages \n  7\n  --\n  26\n  . \n  Springer May 2011.   E. Kiltz K. Pietrzak D. Cash A. Jain and D. Venturi. Efficient authentication from hard learning problems. In K. G. Paterson editor EUROCRYPT 2011 volume 6632 of LNCS pages 7--26. Springer May 2011.","DOI":"10.1007\/978-3-642-20465-4_3"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/11586821_1"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"U. M.\n      Maurer\n     and \n      S.\n      Wolf\n  . \n  Lower bounds on generic algorithms in groups\n  . In K. Nyberg editor EUROCRYPT'98 volume \n  1403\n   of \n  LNCS pages \n  72\n  --\n  84\n  . \n  Springer May \/ June \n  1998\n  .  U. M. Maurer and S. Wolf. Lower bounds on generic algorithms in groups. In K. Nyberg editor EUROCRYPT'98 volume 1403 of LNCS pages 72--84. Springer May \/ June 1998.","DOI":"10.1007\/BFb0054118"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301312"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27660-6_9"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195134"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_3_2_1_48_1","series-title":"LNCS","first-page":"256","volume-title":"EUROCRYPT'97","author":"Shoup V.","year":"1997","unstructured":"V. Shoup . Lower bounds for discrete logarithms and related problems. In W. Fumy, editor, EUROCRYPT'97 , volume 1233 of LNCS , pages 256 -- 266 . Springer , May 1997 . V. Shoup. Lower bounds for discrete logarithms and related problems. In W. Fumy, editor, EUROCRYPT'97, volume 1233 of LNCS, pages 256--266. Springer, May 1997."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.95"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.25"}],"event":{"name":"ITCS'15: Innovations in Theoretical Computer Science","location":"Rehovot Israel","acronym":"ITCS'15","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2688073.2688114","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2688073.2688114","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:04Z","timestamp":1750227184000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2688073.2688114"}},"subtitle":["Extended Abstract"],"short-title":[],"issued":{"date-parts":[[2015,1,11]]},"references-count":50,"alternative-id":["10.1145\/2688073.2688114","10.1145\/2688073"],"URL":"https:\/\/doi.org\/10.1145\/2688073.2688114","relation":{},"subject":[],"published":{"date-parts":[[2015,1,11]]},"assertion":[{"value":"2015-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}