{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,26]],"date-time":"2023-04-26T04:48:30Z","timestamp":1682484510085},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T00:00:00Z","timestamp":1679443200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T00:00:00Z","timestamp":1679443200000},"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":["J Cryptol"],"published-print":{"date-parts":[[2023,4]]},"DOI":"10.1007\/s00145-023-09448-4","type":"journal-article","created":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T00:03:26Z","timestamp":1679443406000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["No-Signaling Linear PCPs"],"prefix":"10.1007","volume":"36","author":[{"given":"Susumu","family":"Kiyoshima","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,22]]},"reference":[{"key":"9448_CR1","unstructured":"S. Arora, B. Barak. Computational Complexity: A Modern Approach (Cambridge University Press, Cambridge, UK, 2009). A draft is available at http:\/\/theory.cs.princeton.edu\/complexity\/book.pdf."},{"key":"9448_CR2","doi-asserted-by":"crossref","unstructured":"W. Aiello, S.N. Bhatt, R. Ostrovsky, S. Rajagopalan, Fast verification of any remote procedure call: Short witness-indistinguishable one-round proofs for NP, in U. Montanari, J.D.P. Rolim, E. Welzl, editors, ICALP 2000, volume 1853 of LNCS (Springer, Heidelberg, 2000), pp. 463\u2013474","DOI":"10.1007\/3-540-45022-X_39"},{"key":"9448_CR3","doi-asserted-by":"crossref","unstructured":"P. Ananth, Y.-C. Chen, K.-M. Chung, H. Lin, W.-K. Lin, Delegating RAM computations with adaptive soundness and privacy, in M. Hirt, A.D. Smith, editors, TCC\u00a02016-B, Part\u00a0II, volume 9986 of LNCS (Springer, Heidelberg, 2016), pp. 3\u201330","DOI":"10.1007\/978-3-662-53644-5_1"},{"issue":"3","key":"9448_CR4","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and the hardness of approximation problems. J. ACM, 45(3):501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"9448_CR5","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S Arora","year":"1998","unstructured":"S. Arora, S. Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70\u2013122 (1998)","journal-title":"J. ACM"},{"key":"9448_CR6","doi-asserted-by":"crossref","unstructured":"D. Boneh, X. Boyen, H. Shacham, Short group signatures, in M. Franklin, editor, CRYPTO\u00a02004, volume 3152 of LNCS (Springer, Heidelberg, 2004), pp. 41\u201355","DOI":"10.1007\/978-3-540-28628-8_3"},{"key":"9448_CR7","doi-asserted-by":"crossref","unstructured":"N. Bitansky, A. Chiesa, Succinct arguments from multi-prover interactive proofs and their efficiency benefits, in R. Safavi-Naini, R. Canetti, editors, CRYPTO\u00a02012, volume 7417 of LNCS (Springer, Heidelberg, 2012), pp. 255\u2013272","DOI":"10.1007\/978-3-642-32009-5_16"},{"key":"9448_CR8","doi-asserted-by":"crossref","unstructured":"N. Bitansky, R. Canetti, A. Chiesa, S. Goldwasser, H. Lin, A. Rubinstein, E. Tromer, The hunting of the SNARK. Journal of Cryptology, 30(4):989\u20131066 (2017)","DOI":"10.1007\/s00145-016-9241-9"},{"key":"9448_CR9","doi-asserted-by":"crossref","unstructured":"N. Bitansky, R. Canetti, A. Chiesa, E. Tromer, Recursive composition and bootstrapping for SNARKS and proof-carrying data, in D. Boneh, T. Roughgarden, J. Feigenbaum, editors, 45th ACM STOC (ACM Press, 2013), pp. 111\u2013120","DOI":"10.1145\/2488608.2488623"},{"key":"9448_CR10","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer, M. Virza, SNARKs for C: Verifying program executions succinctly and in zero knowledge, in R. Canetti, J.A. Garay, editors, CRYPTO\u00a02013, Part\u00a0II, volume 8043 of LNCS (Springer, Heidelberg, 2013), pp. 90\u2013108","DOI":"10.1007\/978-3-642-40084-1_6"},{"key":"9448_CR11","doi-asserted-by":"crossref","unstructured":"M. Bellare, D. Coppersmith, J. Hastad, M. Kiwi, M. Sudan, Linearity testing in characteristic two. IEEE Transactions on Information Theory, 42(6):1781\u20131795 (1996)","DOI":"10.1109\/18.556674"},{"key":"9448_CR12","doi-asserted-by":"crossref","unstructured":"N. Bitansky, A. Chiesa, Y. Ishai, R. Ostrovsky, O. Paneth, Succinct non-interactive arguments via linear interactive proofs, in A. Sahai, editor, TCC\u00a02013, volume 7785 of LNCS (Springer, Heidelberg, 2013), pp. 315\u2013333","DOI":"10.1007\/978-3-642-36594-2_18"},{"key":"9448_CR13","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, A. Chiesa, N. Spooner, Interactive oracle proofs, in M. Hirt, A.D. Smith, editors, TCC\u00a02016-B, Part\u00a0II, volume 9986 of LNCS (Springer, Heidelberg, 2016), pp. 31\u201360","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"9448_CR14","unstructured":"E. Ben-Sasson, A. Chiesa, E. Tromer, M. Virza, Succinct non-interactive zero knowledge for a von Neumann architecture, in Proceedings of the 23rd USENIX Security Symposium, San Diego, CA, USA, August 20\u201322, 2014. (2014), pp. 781\u2013796."},{"key":"9448_CR15","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L.A. Levin, M. Szegedy, Checking computations in polylogarithmic time, in 23rd ACM STOC (ACM Press, 1991), pp. 21\u201331","DOI":"10.1145\/103418.103428"},{"issue":"5","key":"9448_CR16","doi-asserted-by":"publisher","first-page":"1661","DOI":"10.1137\/070709244","volume":"38","author":"B Barak","year":"2009","unstructured":"B. Barak, O. Goldreich, Universal arguments and their applications. SIAM Journal on Computing, 38(5):1661\u20131694 (2009)","journal-title":"SIAM J. Comput."},{"key":"9448_CR17","doi-asserted-by":"crossref","unstructured":"N. Bitansky, S. Garg, H. Lin, R. Pass, S. Telang, Succinct randomized encodings and their applications, in R.A. Servedio, R. Rubinfeld, editors, 47th ACM STOC (ACM Press, 2015), pp. 439\u2013448","DOI":"10.1145\/2746539.2746574"},{"key":"9448_CR18","unstructured":"Z. Brakerski, J. Holmgren, Y. Kalai, Non-interactive RAM and batch NP delegation from any PIR. Cryptology ePrint Archive, Report 2016\/459, 2016. https:\/\/eprint.iacr.org\/2016\/459"},{"key":"9448_CR19","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, J. Holmgren, Y.T. Kalai, Non-interactive delegation and batch NP verification from standard computational assumptions, in H. Hatami, P. McKenzie, V. King, editors, 49th ACM STOC (ACM Press, 2017), pp. 474\u2013482.","DOI":"10.1145\/3055399.3055497"},{"key":"9448_CR20","doi-asserted-by":"crossref","unstructured":"D. Boneh, Y. Ishai, A. Sahai, D.J. Wu, Lattice-based SNARGs and their application to more efficient obfuscation, in J. Coron, J.B. Nielsen, editors, EUROCRYPT\u00a02017, Part\u00a0III, volume 10212 of LNCS (Springer, Heidelberg, 2017), pp. 247\u2013277","DOI":"10.1007\/978-3-319-56617-7_9"},{"key":"9448_CR21","doi-asserted-by":"crossref","unstructured":"S. Badrinarayanan, Y.T. Kalai, D. Khurana, A. Sahai, D. Wichs. Succinct delegation for low-space non-deterministic computation. In I. Diakonikolas, D. Kempe, M. Henzinger, editors, 50th ACM STOC (ACM Press, 2018), pp. 709\u2013721.","DOI":"10.1145\/3188745.3188924"},{"issue":"3","key":"9448_CR22","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M Blum","year":"1993","unstructured":"M. Blum, M. Luby, R. Rubinfeld, Self-testing\/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47(3):549\u2013595 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"9448_CR23","doi-asserted-by":"crossref","unstructured":"I. Biehl, B. Meyer, S. Wetzel, Ensuring the integrity of agent-based computations by short proofs, in Mobile Agents, Second International Workshop, MA\u201998, Stuttgart, Germany, September 1998, Proceedings (1998), pp. 183\u2013194","DOI":"10.1007\/BFb0057658"},{"key":"9448_CR24","doi-asserted-by":"crossref","unstructured":"Y.-C. Chen, S.S.M. Chow, K.-M. Chung, R.W.F. Lai, W.-K. Lin, H.-S. Zhou, Cryptography for parallel RAM from indistinguishability obfuscation, in M. Sudan, editor, ITCS 2016 (ACM, 2016), pp 179\u2013190","DOI":"10.1145\/2840728.2840769"},{"key":"9448_CR25","doi-asserted-by":"crossref","unstructured":"R. Canetti, Y. Chen, J. Holmgren, M. Raykova. Adaptive succinct garbled RAM or: How to delegate your database, in M. Hirt, A.D. Smith, editors, TCC\u00a02016-B, Part\u00a0II, volume 9986 of LNCS (Springer, Heidelberg, 2016), pp. 61\u201390","DOI":"10.1007\/978-3-662-53644-5_3"},{"key":"9448_CR26","doi-asserted-by":"crossref","unstructured":"R. Canetti, J. Holmgren, Fully succinct garbled RAM, in M. Sudan, editor, ITCS 2016 (ACM, 2016), pp. 169\u2013178","DOI":"10.1145\/2840728.2840765"},{"key":"9448_CR27","doi-asserted-by":"crossref","unstructured":"R. Canetti, J. Holmgren, A. Jain, V. Vaikuntanathan., Succinct garbling and indistinguishability obfuscation for RAM programs, in R.A. Servedio, R. Rubinfeld, editors, 47th ACM STOC (ACM Press, 2015), pp. 429\u2013437","DOI":"10.1145\/2746539.2746621"},{"key":"9448_CR28","doi-asserted-by":"crossref","unstructured":"K.-M. Chung, Y. Kalai, S.P. Vadhan, Improved delegation of computation using fully homomorphic encryption, in T. Rabin, editor, CRYPTO\u00a02010, volume 6223 of LNCS, (Springer, Heidelberg, 2010), pp. 483\u2013501","DOI":"10.1007\/978-3-642-14623-7_26"},{"key":"9448_CR29","unstructured":"A. Chiesa, P. Manohar, I. Shinkar, Testing linearity against non-signaling strategies, in 33rd Computational Complexity Conference (CCC 2018), 22\u201324 June 2018, San Diego, California, USA (2018), pp. 17:1\u201317:37"},{"key":"9448_CR30","unstructured":"A. Chiesa, P. Manohar, I. Shinkar, Probabilistic checking against non-signaling strategies from linearity testing, in A. Blum, editor, ITCS 2019, volume 124 (LIPIcs, 2019), pp. 25:1\u201325:17"},{"key":"9448_CR31","doi-asserted-by":"crossref","unstructured":"G. Danezis, C. Fournet, J. Groth, M. Kohlweiss, Square span programs with applications to succinct NIZK arguments, in P. Sarkar, T. Iwata, editors, ASIACRYPT\u00a02014, Part\u00a0I, volume 8873 of LNCS ( Springer, Heidelberg, 2014), pp. 532\u2013550.","DOI":"10.1007\/978-3-662-45611-8_28"},{"key":"9448_CR32","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, S. Faust, C. Hazay, Secure two-party computation with low communication, in R. Cramer, editor, TCC\u00a02012, volume 7194 of LNCS (Springer, Heidelberg, 2012), pp. 54\u201374.","DOI":"10.1007\/978-3-642-28914-9_4"},{"key":"9448_CR33","doi-asserted-by":"crossref","unstructured":"R. Gennaro, C. Gentry, and B. Parno, Non-interactive verifiable computing: Outsourcing computation to untrusted workers, in T. Rabin, editor, CRYPTO\u00a02010, volume 6223 of LNCS (Springer, Heidelberg, 2010), pp. 465\u2013482","DOI":"10.1007\/978-3-642-14623-7_25"},{"key":"9448_CR34","doi-asserted-by":"crossref","unstructured":"R. Gennaro, C. Gentry, B. Parno, M. Raykova. Quadratic span programs and succinct NIZKs without PCPs, in T. Johansson, and P.Q. Nguyen, editors, EUROCRYPT\u00a02013, volume 7881 of LNCS (Springer, Heidelberg, 2013), pp. 626\u2013645.","DOI":"10.1007\/978-3-642-38348-9_37"},{"key":"9448_CR35","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, Y.T. Kalai, G.N. Rothblum. Delegating computation: Interactive proofs for muggles. J. ACM, 62(4):27:1\u201327:64 (2015)","DOI":"10.1145\/2699436"},{"issue":"2","key":"9448_CR36","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S Goldwasser","year":"1984","unstructured":"S. Goldwasser, S. Micali, Probabilistic encryption. J. Comput. Syst. Sci. 28(2):270\u2013299 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"9448_CR37","unstructured":"O. Goldreich. Introduction to Property Testing. Cambridge University Press, Cambridge, UK, 2017. A draft is available at http:\/\/www.wisdom.weizmann.ac.il\/~oded\/PDF\/pt-v3.pdf."},{"key":"9448_CR38","doi-asserted-by":"crossref","unstructured":"J. Groth. Short pairing-based non-interactive zero-knowledge arguments, in M. Abe, editor, ASIACRYPT\u00a02010, volume 6477 of LNCS (Springer, Heidelberg, 2010), pp. 321\u2013340.","DOI":"10.1007\/978-3-642-17373-8_19"},{"key":"9448_CR39","doi-asserted-by":"crossref","unstructured":"J. Groth. On the size of pairing-based non-interactive arguments, in M. Fischlin, J.-S. Coron, editors, EUROCRYPT\u00a02016, Part\u00a0II, volume 9666 of LNCS (Springer, Heidelberg, 2016), pp. 305\u2013326","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"9448_CR40","doi-asserted-by":"crossref","unstructured":"J. Holmgren, R. Rothblum, Delegating computations with (almost) minimal time and space overhead, in M. Thorup, editor, 59th FOCS (IEEE Computer Society Press, 2018), pp. 124\u2013135","DOI":"10.1109\/FOCS.2018.00021"},{"key":"9448_CR41","unstructured":"Y. Ishai, E. Kushilevitz, R. Ostrovsky, Efficient arguments without short PCPs, in 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13\u201316 June 2007, San Diego, California, USA (2007), pp. 278\u2013291."},{"key":"9448_CR42","doi-asserted-by":"crossref","unstructured":"J. Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In 24th ACM STOC (ACM Press, 1992), pp. 723\u2013732.","DOI":"10.1145\/129712.129782"},{"key":"9448_CR43","doi-asserted-by":"crossref","unstructured":"V. Koppula, A.B. Lewko, B. Waters, Indistinguishability obfuscation for turing machines with unbounded memory, in R.A. Servedio, R, Rubinfeld, editors, 47th ACM STOC (ACM Press, 2015), pp. 419\u2013428.","DOI":"10.1145\/2746539.2746614"},{"key":"9448_CR44","doi-asserted-by":"crossref","unstructured":"Y.T. Kalai, O. Paneth, Delegating RAM computations. In M. Hirt, A.D. Smith editors, TCC\u00a02016-B, Part\u00a0II, volume 9986 of LNCS (Springer, Heidelberg, 2016), pp. 91\u2013118.","DOI":"10.1007\/978-3-662-53644-5_4"},{"key":"9448_CR45","unstructured":"Y.T. Kalai, R. Raz, R.D. Rothblum, Delegation for bounded space, in D. Boneh, T. Roughgarden, J. Feigenbaum, editors, 45th ACM STOC (ACM Press, June 2013), pp. 565\u2013574."},{"key":"9448_CR46","doi-asserted-by":"crossref","unstructured":"Y.T. Kalai, R. Raz, R.D. Rothblum, How to delegate computations: the power of no-signaling proofs, in D.B. Shmoys, editor, 46th ACM STOC (ACM Press, 2014), pp. 485\u2013494","DOI":"10.1145\/2591796.2591809"},{"key":"9448_CR47","doi-asserted-by":"crossref","unstructured":"H. Lipmaa, Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments, in R. Cramer, editor, TCC\u00a02012, volume 7194 of LNCS (Springer, Heidelberg, 2012), pp. 169\u2013189","DOI":"10.1007\/978-3-642-28914-9_10"},{"key":"9448_CR48","doi-asserted-by":"crossref","unstructured":"H. Lipmaa, Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes, in K. Sako, P. Sarkar, editors, ASIACRYPT\u00a02013, Part\u00a0I, volume 8269 of LNCS (Springer, Heidelberg, 2013), pp. 41\u201360","DOI":"10.1007\/978-3-642-42033-7_3"},{"issue":"4","key":"9448_CR49","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/S0097539795284959","volume":"30","author":"S Micali","year":"2000","unstructured":"S. Micali, Computationally sound proofs. SIAM J. Comput., 30(4), 1253\u20131298 (2000)","journal-title":"SIAM J. Comput."},{"key":"9448_CR50","doi-asserted-by":"crossref","unstructured":"O. Paneth, G.N. Rothblum. On zero-testable homomorphic encryption and publicly verifiable non-interactive arguments, in Y. Kalai, L. Reyzin, editors, TCC\u00a02017, Part\u00a0II, volume 10678 of LNCS, (Springer, Heidelberg, 2017), pp. 283\u2013315","DOI":"10.1007\/978-3-319-70503-3_9"},{"key":"9448_CR51","doi-asserted-by":"crossref","unstructured":"B. Parno, M. Raykova, V. Vaikuntanathan, How to delegate and verify in public: Verifiable computation from attribute-based encryption, in Ronald Cramer, editor, TCC\u00a02012, volume 7194 of LNCS (Springer, Heidelberg, 2012), pp. 422\u2013439","DOI":"10.1007\/978-3-642-28914-9_24"},{"key":"9448_CR52","doi-asserted-by":"crossref","unstructured":"S. Setty, B. Braun, V. Vu, A.J. Blumberg, B. Parno, M. Walfish. Resolving the conflict between generality and plausibility in verified computation, in Proceedings of the ACM European Conference on Computer Systems (EuroSys) (ACM, 2013)","DOI":"10.1145\/2465351.2465359"},{"key":"9448_CR53","unstructured":"S. Setty, A.J. Blumberg, M. Walfish. Toward practical and unconditional verification of remote computations, in Workshop on Hot Topics in Operating Systems (HotOS) (USENIX - Advanced Computing Systems Association, 2011)"},{"key":"9448_CR54","unstructured":"S.T.V. Setty, R. McPherson, A.J. Blumberg, M. Walfish. Making argument systems for outsourced computation practical (sometimes), in NDSS\u00a02012 (The Internet Society, 2012)"},{"key":"9448_CR55","unstructured":"S.T.V. Setty, V. Vu, N. Panpalia, B. Braun, A.J. Blumberg, M. Walfish. Taking proof-based verified computation a few steps closer to practicality, in Proceedings of the 21th USENIX Security Symposium, Bellevue, WA, USA, August 8-10, 2012 (2012), pp. 253\u2013268."},{"key":"9448_CR56","doi-asserted-by":"crossref","unstructured":"V. Vu, Srinath T.V. Setty, A.J. Blumberg, M. Walfish, A hybrid architecture for interactive verifiable computation, in 2013 IEEE Symposium on Security and Privacy (IEEE Computer Society Press, 2013), pp. 223\u2013237","DOI":"10.1109\/SP.2013.48"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09448-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-023-09448-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09448-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,25]],"date-time":"2023-04-25T17:08:13Z","timestamp":1682442493000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-023-09448-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,22]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["9448"],"URL":"https:\/\/doi.org\/10.1007\/s00145-023-09448-4","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,22]]},"assertion":[{"value":"17 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"9"}}