{"id":164197,"date":"2013-05-30T00:00:00","date_gmt":"2013-05-30T00:00:00","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/quadratic-span-programs-and-succinct-nizks-without-pcps\/"},"modified":"2018-10-16T20:10:20","modified_gmt":"2018-10-17T03:10:20","slug":"quadratic-span-programs-and-succinct-nizks-without-pcps","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/quadratic-span-programs-and-succinct-nizks-without-pcps\/","title":{"rendered":"Quadratic Span Programs and Succinct NIZKs without PCPs"},"content":{"rendered":"<div class=\"asset-content\">\n<p>We introduce a new characterization of the NP complexity class, called Quadratic Span Programs (QSPs), which is a natural extension of span programs defined by Karchmer and Wigderson. Our main motivation is the quick construction of succinct, easily verified arguments for NP statements.<\/p>\n<p>To achieve this goal, QSPs use a new approach to the well-known technique of arithmetization of Boolean circuits. Our new approach yields dramatic performance improvements. Using QSPs, we construct a NIZK argument \u2013 in the CRS model \u2013 for Circuit-SAT consisting of just 7 group elements. The CRS size and prover computation are quasi-linear, making our scheme seemingly quite practical, a result supported by our implementation. Indeed, our NIZK argument attains the shortest proof, most efficient prover, and most efficient verifier of any known technique. We also present a variant of QSPs, called Quadratic Arithmetic Programs (QAPs), that &#8220;naturally&#8221; compute arithmetic circuits over large fields, along with succinct NIZK constructions that use QAPs.<\/p>\n<p>Finally, we show how QSPs and QAPs can be used to efficiently and publicly verify outsourced computations, where a client asks a server to compute F(x) for a given function F and must verify the result provided by the server in considerably less time than it would take to compute F from scratch. The resulting schemes are the most efficient, general-purpose publicly verifiable computation schemes.<\/p>\n<p>Originally published as Cryptology ePrint Archive, Report 2012\/215<\/p>\n<p>Full version available at: http:\/\/eprint.iacr.org\/2012\/215<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>We introduce a new characterization of the NP complexity class, called Quadratic Span Programs (QSPs), which is a natural extension of span programs defined by Karchmer and Wigderson. Our main motivation is the quick construction of succinct, easily verified arguments for NP statements. To achieve this goal, QSPs use a new approach to the well-known [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[13558],"msr-publication-type":[193716],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-164197","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-security-privacy-cryptography","msr-locale-en_us"],"msr_publishername":"International Association for Cryptologic Research","msr_edition":"Proceedings of the IACR Eurocrypt Conference","msr_affiliation":"","msr_published_date":"2013-05-30","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"Proceedings of the IACR Eurocrypt Conference","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"205433","msr_publicationurl":"http:\/\/eprint.iacr.org\/2012\/215","msr_doi":"","msr_publication_uploader":[{"type":"file","title":"QSP.pdf","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/QSP.pdf","id":205433,"label_id":0},{"type":"url","title":"http:\/\/eprint.iacr.org\/2012\/215","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_attachments":[{"id":0,"url":"http:\/\/eprint.iacr.org\/2012\/215"},{"id":205433,"url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/QSP.pdf"}],"msr-author-ordering":[{"type":"text","value":"Rosario Gennaro","user_id":0,"rest_url":false},{"type":"text","value":"Craig Gentry","user_id":0,"rest_url":false},{"type":"user_nicename","value":"parno","user_id":33193,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=parno"},{"type":"text","value":"Mariana Raykova","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[170789],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","related_content":{"projects":[{"ID":170789,"post_title":"Verifiable Computing","post_name":"verifiable-computing","post_type":"msr-project","post_date":"2011-08-24 08:05:35","post_modified":"2019-08-19 15:14:19","post_status":"publish","permalink":"https:\/\/www.microsoft.com\/en-us\/research\/project\/verifiable-computing\/","post_excerpt":"Verifiable computation schemes enable a client to outsource the computation of a function F on various inputs to an untrusted worker, and then verify the correctness of the returned results. Critically, the outsourcing and verification procedures must be more efficient than performing the computation itself. In more detail, we introduce and formalize the notion of Verifiable Computation, which enables a computationally weak client to \"outsource\" the computation of an arbitrary function F on various dynamically-chosen&hellip;","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/170789"}]}}]},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/164197"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/164197\/revisions"}],"predecessor-version":[{"id":523680,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/164197\/revisions\/523680"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=164197"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=164197"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=164197"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=164197"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=164197"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=164197"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=164197"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=164197"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=164197"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=164197"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=164197"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=164197"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=164197"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=164197"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=164197"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=164197"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}