Succinct Non-Interactive Arguments via Linear Interactive Proofs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2022-05-02

AUTHORS

Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth

ABSTRACT

Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays, researchers have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation. A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O(1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have “escaped the hegemony” of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments. We present a general methodology for the construction of preprocessing SNARG\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text{ SNARG } $$\end{document}s, as well as resulting new efficiency features. Our contribution is threefold: (1)We introduce and study a natural extension of the interactive proof model that considers algebraically-bounded provers; this new setting is analogous to the common study of algebraically-bounded “adversaries” in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) linear interactive proofs (LIPs) for NP. Our constructions are based on general transformations applied to both linear PCPs (LPCPs) and traditional “unstructured” PCPs.(2)We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of linear targeted malleability (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain zero-knowledge LIPs and SNARGs. Our techniques yield SNARGs of knowledge and thus can benefit from known recursive composition and bootstrapping techniques.(3)Following this methodology, we exhibit several constructions achieving new efficiency features, such as “single-ciphertext preprocessing SNARGs.” We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs. More... »

PAGES

15

References to SciGraph publications

  • 2008. Succinct NP Proofs from an Extractability Assumption in LOGIC AND THEORY OF ALGORITHMS
  • 1993. Low communication 2-prover zero-knowledge proofs for NP in ADVANCES IN CRYPTOLOGY — CRYPTO’ 92
  • 2019-08-01. Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs in ADVANCES IN CRYPTOLOGY – CRYPTO 2019
  • 2012. Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments in THEORY OF CRYPTOGRAPHY
  • 2016-10-03. The Hunting of the SNARK in JOURNAL OF CRYPTOLOGY
  • 2012. Succinct Arguments from Multi-prover Interactive Proofs and Their Efficiency Benefits in ADVANCES IN CRYPTOLOGY – CRYPTO 2012
  • 2020-08-10. On Succinct Arguments and Witness Encryption from Groups in ADVANCES IN CRYPTOLOGY – CRYPTO 2020
  • 1992. Towards Practical Public Key Systems Secure Against Chosen Ciphertext attacks in ADVANCES IN CRYPTOLOGY — CRYPTO ’91
  • 2004. Towards Plaintext-Aware Public-Key Encryption Without Random Oracles in ADVANCES IN CRYPTOLOGY - ASIACRYPT 2004
  • 2012. Two Protocols for Delegation of Computation in INFORMATION THEORETIC SECURITY
  • 2008-01-01. Interactive PCP in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1998. On the existence of 3-round zero-knowledge protocols in ADVANCES IN CRYPTOLOGY — CRYPTO '98
  • 2011. Verifiable Delegation of Computation over Large Datasets in ADVANCES IN CRYPTOLOGY – CRYPTO 2011
  • 2002-06. On interactive proofs with a laconic prover in COMPUTATIONAL COMPLEXITY
  • 2009-04-23. Extractors And Rank Extractors For Polynomial Sources in COMPUTATIONAL COMPLEXITY
  • 2003. On Cryptographic Assumptions and Challenges in ADVANCES IN CRYPTOLOGY - CRYPTO 2003
  • 1977. Graph-theoretic arguments in low-level complexity in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1977
  • 2010. On Ideal Lattices and Learning with Errors over Rings in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2010
  • 2005. On Round-Efficient Argument Systems in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2012. On Polynomial Systems Arising from a Weil Descent in ADVANCES IN CRYPTOLOGY – ASIACRYPT 2012
  • 2004. The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols in ADVANCES IN CRYPTOLOGY – CRYPTO 2004
  • 2016-04-28. On the Size of Pairing-Based Non-interactive Arguments in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2016
  • 2010. From Secrecy to Soundness: Efficient Verification via Secure Computation in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2014. Square Span Programs with Applications to Succinct NIZK Arguments in ADVANCES IN CRYPTOLOGY – ASIACRYPT 2014
  • 2013. Quadratic Span Programs and Succinct NIZKs without PCPs in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2013
  • 2000-12-01. How To Prove Yourself: Practical Solutions to Identification and Signature Problems in ADVANCES IN CRYPTOLOGY — CRYPTO’ 86
  • 2010. Short Pairing-Based Non-interactive Zero-Knowledge Arguments in ADVANCES IN CRYPTOLOGY - ASIACRYPT 2010
  • 2009. Probabilistically Checkable Arguments in ADVANCES IN CRYPTOLOGY - CRYPTO 2009
  • 2000-12. Small PCPs with low query complexity in COMPUTATIONAL COMPLEXITY
  • 2010. Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers in ADVANCES IN CRYPTOLOGY – CRYPTO 2010
  • 2006. Pairing-Friendly Elliptic Curves of Prime Order in SELECTED AREAS IN CRYPTOGRAPHY
  • 2010. Improved Delegation of Computation Using Fully Homomorphic Encryption in ADVANCES IN CRYPTOLOGY – CRYPTO 2010
  • 2000. Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1999-04-15. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’99
  • 2017-11-17. Linear-Time Zero-Knowledge Proofs for Arithmetic Circuit Satisfiability in ADVANCES IN CRYPTOLOGY – ASIACRYPT 2017
  • 2012. Secure Two-Party Computation with Low Communication in THEORY OF CRYPTOGRAPHY
  • 2011. Homomorphic Encryption: From Private-Key to Public-Key in THEORY OF CRYPTOGRAPHY
  • 2020-05-01. Transparent SNARKs from DARK Compilers in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2020
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00145-022-09424-4

    DOI

    http://dx.doi.org/10.1007/s00145-022-09424-4

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1147565220


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Tel Aviv University, Tel Aviv-Yafo, Israel", 
              "id": "http://www.grid.ac/institutes/grid.12136.37", 
              "name": [
                "Tel Aviv University, Tel Aviv-Yafo, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bitansky", 
            "givenName": "Nir", 
            "id": "sg:person.016302552357.74", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016302552357.74"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "EPFL, Lausanne, Switzerland", 
              "id": "http://www.grid.ac/institutes/grid.5333.6", 
              "name": [
                "EPFL, Lausanne, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chiesa", 
            "givenName": "Alessandro", 
            "id": "sg:person.014135776027.95", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014135776027.95"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Technion, Haifa, Israel", 
              "id": "http://www.grid.ac/institutes/grid.6451.6", 
              "name": [
                "Technion, Haifa, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ishai", 
            "givenName": "Yuval", 
            "id": "sg:person.010434442160.49", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010434442160.49"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Department of Mathematics, UCLA, Los Angeles, CA, USA", 
              "id": "http://www.grid.ac/institutes/grid.19006.3e", 
              "name": [
                "Department of Computer Science and Department of Mathematics, UCLA, Los Angeles, CA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ostrovsky", 
            "givenName": "Rafail", 
            "id": "sg:person.015474716573.95", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015474716573.95"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Tel Aviv University, Tel Aviv-Yafo, Israel", 
              "id": "http://www.grid.ac/institutes/grid.12136.37", 
              "name": [
                "Tel Aviv University, Tel Aviv-Yafo, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Paneth", 
            "givenName": "Omer", 
            "id": "sg:person.014073524511.68", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-17373-8_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010136999", 
              "https://doi.org/10.1007/978-3-642-17373-8_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14623-7_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046902420", 
              "https://doi.org/10.1007/978-3-642-14623-7_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-70583-3_44", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047985286", 
              "https://doi.org/10.1007/978-3-540-70583-3_44"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45146-4_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004899373", 
              "https://doi.org/10.1007/978-3-540-45146-4_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-70700-6_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1092726903", 
              "https://doi.org/10.1007/978-3-319-70700-6_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-22792-9_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050489782", 
              "https://doi.org/10.1007/978-3-642-22792-9_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-13190-5_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025305533", 
              "https://doi.org/10.1007/978-3-642-13190-5_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-28914-9_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003687084", 
              "https://doi.org/10.1007/978-3-642-28914-9_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48071-4_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012649421", 
              "https://doi.org/10.1007/3-540-48071-4_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28628-8_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029081667", 
              "https://doi.org/10.1007/978-3-540-28628-8_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-32009-5_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051014589", 
              "https://doi.org/10.1007/978-3-642-32009-5_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46766-1_36", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017562633", 
              "https://doi.org/10.1007/3-540-46766-1_36"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/pl00001606", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025900372", 
              "https://doi.org/10.1007/pl00001606"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30539-2_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044260446", 
              "https://doi.org/10.1007/978-3-540-30539-2_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45022-x_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040895434", 
              "https://doi.org/10.1007/3-540-45022-x_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-19571-6_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022245307", 
              "https://doi.org/10.1007/978-3-642-19571-6_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-56784-2_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1130044382", 
              "https://doi.org/10.1007/978-3-030-56784-2_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11693383_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039881626", 
              "https://doi.org/10.1007/11693383_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48910-x_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026773924", 
              "https://doi.org/10.1007/3-540-48910-x_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-38348-9_37", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041046155", 
              "https://doi.org/10.1007/978-3-642-38348-9_37"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0055744", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011447978", 
              "https://doi.org/10.1007/bfb0055744"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-69407-6_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009899255", 
              "https://doi.org/10.1007/978-3-540-69407-6_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-28914-9_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046350689", 
              "https://doi.org/10.1007/978-3-642-28914-9_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-49896-5_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015216783", 
              "https://doi.org/10.1007/978-3-662-49896-5_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00145-016-9241-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031129963", 
              "https://doi.org/10.1007/s00145-016-9241-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00037-009-0258-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041566190", 
              "https://doi.org/10.1007/s00037-009-0258-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14623-7_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021668788", 
              "https://doi.org/10.1007/978-3-642-14623-7_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-45721-1_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1127315524", 
              "https://doi.org/10.1007/978-3-030-45721-1_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03356-8_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030758919", 
              "https://doi.org/10.1007/978-3-642-03356-8_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-45611-8_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010140710", 
              "https://doi.org/10.1007/978-3-662-45611-8_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-26954-8_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1120207777", 
              "https://doi.org/10.1007/978-3-030-26954-8_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-32284-6_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030412010", 
              "https://doi.org/10.1007/978-3-642-32284-6_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11523468_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037069167", 
              "https://doi.org/10.1007/11523468_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00037-002-0169-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039183238", 
              "https://doi.org/10.1007/s00037-002-0169-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-34961-4_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038456429", 
              "https://doi.org/10.1007/978-3-642-34961-4_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-47721-7_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038535610", 
              "https://doi.org/10.1007/3-540-47721-7_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14165-2_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022822211", 
              "https://doi.org/10.1007/978-3-642-14165-2_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-08353-7_135", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025032395", 
              "https://doi.org/10.1007/3-540-08353-7_135"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-05-02", 
        "datePublishedReg": "2022-05-02", 
        "description": "Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays, researchers have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation. A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O(1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have \u201cescaped the hegemony\u201d of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments. We present a general methodology for the construction of preprocessing SNARG\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\text{ SNARG } $$\\end{document}s, as well as resulting new efficiency features. Our contribution is threefold: (1)We introduce and study a natural extension of the interactive proof model that considers algebraically-bounded provers; this new setting is analogous to the common study of algebraically-bounded \u201cadversaries\u201d in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) linear interactive proofs (LIPs) for NP. Our constructions are based on general transformations applied to both linear PCPs (LPCPs) and traditional \u201cunstructured\u201d PCPs.(2)We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of linear targeted malleability (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain zero-knowledge LIPs and SNARGs. Our techniques yield SNARGs of knowledge and thus can benefit from known recursive composition and bootstrapping techniques.(3)Following this methodology, we exhibit several constructions achieving new efficiency features, such as \u201csingle-ciphertext preprocessing SNARGs.\u201d We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00145-022-09424-4", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1136278", 
            "issn": [
              "0933-2790", 
              "1432-1378"
            ], 
            "name": "Journal of Cryptology", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "35"
          }
        ], 
        "keywords": [
          "succinct non-interactive arguments", 
          "non-interactive arguments", 
          "linear PCPs", 
          "interactive proofs", 
          "NP statements", 
          "expensive offline phase", 
          "efficiency features", 
          "proof model", 
          "verification time", 
          "offline phase", 
          "cryptographic transformations", 
          "recursive composition", 
          "succinct arguments", 
          "checkable proofs", 
          "low complexity", 
          "basic building blocks", 
          "size linear", 
          "verifier", 
          "provers", 
          "field elements", 
          "arithmetic circuits", 
          "general methodology", 
          "verification", 
          "randomness extraction", 
          "natural extension", 
          "adversary", 
          "general transformation", 
          "attractive features", 
          "security", 
          "proof", 
          "building blocks", 
          "common relaxation", 
          "methodology", 
          "new setting", 
          "features", 
          "computation", 
          "complexity", 
          "pseudorandomness", 
          "NPs", 
          "technique", 
          "construction", 
          "introduces", 
          "extraction", 
          "direct connection", 
          "researchers", 
          "recent construction", 
          "extension", 
          "transformation", 
          "new perspective", 
          "block", 
          "work", 
          "knowledge", 
          "model", 
          "statements", 
          "connection", 
          "motivation", 
          "consist", 
          "different forms", 
          "time", 
          "field", 
          "focus", 
          "perspective", 
          "elements", 
          "setting", 
          "contribution", 
          "circuit", 
          "common studies", 
          "linear", 
          "form", 
          "malleability", 
          "argument", 
          "such arguments", 
          "phase", 
          "relaxation", 
          "study", 
          "length", 
          "PCP", 
          "composition", 
          "hegemony", 
          "problem"
        ], 
        "name": "Succinct Non-Interactive Arguments via Linear Interactive Proofs", 
        "pagination": "15", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1147565220"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00145-022-09424-4"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00145-022-09424-4", 
          "https://app.dimensions.ai/details/publication/pub.1147565220"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-06-01T22:25", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/article/article_934.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00145-022-09424-4"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00145-022-09424-4'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00145-022-09424-4'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00145-022-09424-4'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00145-022-09424-4'


     

    This table displays all metadata directly associated to this object as RDF triples.

    327 TRIPLES      22 PREDICATES      143 URIs      97 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00145-022-09424-4 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nfd8e9a1dd34640a6bb9fc36cc7ddb555
    4 schema:citation sg:pub.10.1007/11523468_12
    5 sg:pub.10.1007/11693383_22
    6 sg:pub.10.1007/3-540-08353-7_135
    7 sg:pub.10.1007/3-540-45022-x_39
    8 sg:pub.10.1007/3-540-46766-1_36
    9 sg:pub.10.1007/3-540-47721-7_12
    10 sg:pub.10.1007/3-540-48071-4_15
    11 sg:pub.10.1007/3-540-48910-x_16
    12 sg:pub.10.1007/978-3-030-26954-8_3
    13 sg:pub.10.1007/978-3-030-45721-1_24
    14 sg:pub.10.1007/978-3-030-56784-2_26
    15 sg:pub.10.1007/978-3-319-70700-6_12
    16 sg:pub.10.1007/978-3-540-28628-8_17
    17 sg:pub.10.1007/978-3-540-30539-2_4
    18 sg:pub.10.1007/978-3-540-45146-4_6
    19 sg:pub.10.1007/978-3-540-69407-6_21
    20 sg:pub.10.1007/978-3-540-70583-3_44
    21 sg:pub.10.1007/978-3-642-03356-8_9
    22 sg:pub.10.1007/978-3-642-13190-5_1
    23 sg:pub.10.1007/978-3-642-14165-2_14
    24 sg:pub.10.1007/978-3-642-14623-7_25
    25 sg:pub.10.1007/978-3-642-14623-7_26
    26 sg:pub.10.1007/978-3-642-17373-8_19
    27 sg:pub.10.1007/978-3-642-19571-6_14
    28 sg:pub.10.1007/978-3-642-22792-9_7
    29 sg:pub.10.1007/978-3-642-28914-9_10
    30 sg:pub.10.1007/978-3-642-28914-9_4
    31 sg:pub.10.1007/978-3-642-32009-5_16
    32 sg:pub.10.1007/978-3-642-32284-6_3
    33 sg:pub.10.1007/978-3-642-34961-4_28
    34 sg:pub.10.1007/978-3-642-38348-9_37
    35 sg:pub.10.1007/978-3-662-45611-8_28
    36 sg:pub.10.1007/978-3-662-49896-5_11
    37 sg:pub.10.1007/bfb0055744
    38 sg:pub.10.1007/pl00001606
    39 sg:pub.10.1007/s00037-002-0169-0
    40 sg:pub.10.1007/s00037-009-0258-4
    41 sg:pub.10.1007/s00145-016-9241-9
    42 schema:datePublished 2022-05-02
    43 schema:datePublishedReg 2022-05-02
    44 schema:description Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays, researchers have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation. A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O(1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have “escaped the hegemony” of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments. We present a general methodology for the construction of preprocessing SNARG\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text{ SNARG } $$\end{document}s, as well as resulting new efficiency features. Our contribution is threefold: (1)We introduce and study a natural extension of the interactive proof model that considers algebraically-bounded provers; this new setting is analogous to the common study of algebraically-bounded “adversaries” in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) linear interactive proofs (LIPs) for NP. Our constructions are based on general transformations applied to both linear PCPs (LPCPs) and traditional “unstructured” PCPs.(2)We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of linear targeted malleability (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain zero-knowledge LIPs and SNARGs. Our techniques yield SNARGs of knowledge and thus can benefit from known recursive composition and bootstrapping techniques.(3)Following this methodology, we exhibit several constructions achieving new efficiency features, such as “single-ciphertext preprocessing SNARGs.” We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.
    45 schema:genre article
    46 schema:inLanguage en
    47 schema:isAccessibleForFree true
    48 schema:isPartOf N43a79676d1784d2f9cb15f7ab2fff5d8
    49 Ne5e85fa4531d429cab5d5d577c983954
    50 sg:journal.1136278
    51 schema:keywords NP statements
    52 NPs
    53 PCP
    54 adversary
    55 argument
    56 arithmetic circuits
    57 attractive features
    58 basic building blocks
    59 block
    60 building blocks
    61 checkable proofs
    62 circuit
    63 common relaxation
    64 common studies
    65 complexity
    66 composition
    67 computation
    68 connection
    69 consist
    70 construction
    71 contribution
    72 cryptographic transformations
    73 different forms
    74 direct connection
    75 efficiency features
    76 elements
    77 expensive offline phase
    78 extension
    79 extraction
    80 features
    81 field
    82 field elements
    83 focus
    84 form
    85 general methodology
    86 general transformation
    87 hegemony
    88 interactive proofs
    89 introduces
    90 knowledge
    91 length
    92 linear
    93 linear PCPs
    94 low complexity
    95 malleability
    96 methodology
    97 model
    98 motivation
    99 natural extension
    100 new perspective
    101 new setting
    102 non-interactive arguments
    103 offline phase
    104 perspective
    105 phase
    106 problem
    107 proof
    108 proof model
    109 provers
    110 pseudorandomness
    111 randomness extraction
    112 recent construction
    113 recursive composition
    114 relaxation
    115 researchers
    116 security
    117 setting
    118 size linear
    119 statements
    120 study
    121 succinct arguments
    122 succinct non-interactive arguments
    123 such arguments
    124 technique
    125 time
    126 transformation
    127 verification
    128 verification time
    129 verifier
    130 work
    131 schema:name Succinct Non-Interactive Arguments via Linear Interactive Proofs
    132 schema:pagination 15
    133 schema:productId N2059d514b4924d62bfa5f0f1a253fce8
    134 Nb724e20956be41ce824bf2774e7e4940
    135 schema:sameAs https://app.dimensions.ai/details/publication/pub.1147565220
    136 https://doi.org/10.1007/s00145-022-09424-4
    137 schema:sdDatePublished 2022-06-01T22:25
    138 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    139 schema:sdPublisher N76f51df9cc584643a9c5b6fd5d556cbf
    140 schema:url https://doi.org/10.1007/s00145-022-09424-4
    141 sgo:license sg:explorer/license/
    142 sgo:sdDataset articles
    143 rdf:type schema:ScholarlyArticle
    144 N05483a6700154a389408fd8a15e9fbde rdf:first sg:person.010434442160.49
    145 rdf:rest Nb82371db695c4d28a263009c21c890e7
    146 N2059d514b4924d62bfa5f0f1a253fce8 schema:name dimensions_id
    147 schema:value pub.1147565220
    148 rdf:type schema:PropertyValue
    149 N43a79676d1784d2f9cb15f7ab2fff5d8 schema:volumeNumber 35
    150 rdf:type schema:PublicationVolume
    151 N76f51df9cc584643a9c5b6fd5d556cbf schema:name Springer Nature - SN SciGraph project
    152 rdf:type schema:Organization
    153 N941ec67ce3e1438dbf9438810d604764 rdf:first sg:person.014135776027.95
    154 rdf:rest N05483a6700154a389408fd8a15e9fbde
    155 N9f8fec6978044a00898e3809bbb3d768 rdf:first sg:person.014073524511.68
    156 rdf:rest rdf:nil
    157 Nb724e20956be41ce824bf2774e7e4940 schema:name doi
    158 schema:value 10.1007/s00145-022-09424-4
    159 rdf:type schema:PropertyValue
    160 Nb82371db695c4d28a263009c21c890e7 rdf:first sg:person.015474716573.95
    161 rdf:rest N9f8fec6978044a00898e3809bbb3d768
    162 Ne5e85fa4531d429cab5d5d577c983954 schema:issueNumber 3
    163 rdf:type schema:PublicationIssue
    164 Nfd8e9a1dd34640a6bb9fc36cc7ddb555 rdf:first sg:person.016302552357.74
    165 rdf:rest N941ec67ce3e1438dbf9438810d604764
    166 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    167 schema:name Information and Computing Sciences
    168 rdf:type schema:DefinedTerm
    169 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    170 schema:name Computation Theory and Mathematics
    171 rdf:type schema:DefinedTerm
    172 sg:journal.1136278 schema:issn 0933-2790
    173 1432-1378
    174 schema:name Journal of Cryptology
    175 schema:publisher Springer Nature
    176 rdf:type schema:Periodical
    177 sg:person.010434442160.49 schema:affiliation grid-institutes:grid.6451.6
    178 schema:familyName Ishai
    179 schema:givenName Yuval
    180 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010434442160.49
    181 rdf:type schema:Person
    182 sg:person.014073524511.68 schema:affiliation grid-institutes:grid.12136.37
    183 schema:familyName Paneth
    184 schema:givenName Omer
    185 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68
    186 rdf:type schema:Person
    187 sg:person.014135776027.95 schema:affiliation grid-institutes:grid.5333.6
    188 schema:familyName Chiesa
    189 schema:givenName Alessandro
    190 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014135776027.95
    191 rdf:type schema:Person
    192 sg:person.015474716573.95 schema:affiliation grid-institutes:grid.19006.3e
    193 schema:familyName Ostrovsky
    194 schema:givenName Rafail
    195 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015474716573.95
    196 rdf:type schema:Person
    197 sg:person.016302552357.74 schema:affiliation grid-institutes:grid.12136.37
    198 schema:familyName Bitansky
    199 schema:givenName Nir
    200 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016302552357.74
    201 rdf:type schema:Person
    202 sg:pub.10.1007/11523468_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037069167
    203 https://doi.org/10.1007/11523468_12
    204 rdf:type schema:CreativeWork
    205 sg:pub.10.1007/11693383_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039881626
    206 https://doi.org/10.1007/11693383_22
    207 rdf:type schema:CreativeWork
    208 sg:pub.10.1007/3-540-08353-7_135 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025032395
    209 https://doi.org/10.1007/3-540-08353-7_135
    210 rdf:type schema:CreativeWork
    211 sg:pub.10.1007/3-540-45022-x_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040895434
    212 https://doi.org/10.1007/3-540-45022-x_39
    213 rdf:type schema:CreativeWork
    214 sg:pub.10.1007/3-540-46766-1_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017562633
    215 https://doi.org/10.1007/3-540-46766-1_36
    216 rdf:type schema:CreativeWork
    217 sg:pub.10.1007/3-540-47721-7_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038535610
    218 https://doi.org/10.1007/3-540-47721-7_12
    219 rdf:type schema:CreativeWork
    220 sg:pub.10.1007/3-540-48071-4_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012649421
    221 https://doi.org/10.1007/3-540-48071-4_15
    222 rdf:type schema:CreativeWork
    223 sg:pub.10.1007/3-540-48910-x_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026773924
    224 https://doi.org/10.1007/3-540-48910-x_16
    225 rdf:type schema:CreativeWork
    226 sg:pub.10.1007/978-3-030-26954-8_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1120207777
    227 https://doi.org/10.1007/978-3-030-26954-8_3
    228 rdf:type schema:CreativeWork
    229 sg:pub.10.1007/978-3-030-45721-1_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1127315524
    230 https://doi.org/10.1007/978-3-030-45721-1_24
    231 rdf:type schema:CreativeWork
    232 sg:pub.10.1007/978-3-030-56784-2_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1130044382
    233 https://doi.org/10.1007/978-3-030-56784-2_26
    234 rdf:type schema:CreativeWork
    235 sg:pub.10.1007/978-3-319-70700-6_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092726903
    236 https://doi.org/10.1007/978-3-319-70700-6_12
    237 rdf:type schema:CreativeWork
    238 sg:pub.10.1007/978-3-540-28628-8_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029081667
    239 https://doi.org/10.1007/978-3-540-28628-8_17
    240 rdf:type schema:CreativeWork
    241 sg:pub.10.1007/978-3-540-30539-2_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044260446
    242 https://doi.org/10.1007/978-3-540-30539-2_4
    243 rdf:type schema:CreativeWork
    244 sg:pub.10.1007/978-3-540-45146-4_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004899373
    245 https://doi.org/10.1007/978-3-540-45146-4_6
    246 rdf:type schema:CreativeWork
    247 sg:pub.10.1007/978-3-540-69407-6_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009899255
    248 https://doi.org/10.1007/978-3-540-69407-6_21
    249 rdf:type schema:CreativeWork
    250 sg:pub.10.1007/978-3-540-70583-3_44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047985286
    251 https://doi.org/10.1007/978-3-540-70583-3_44
    252 rdf:type schema:CreativeWork
    253 sg:pub.10.1007/978-3-642-03356-8_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030758919
    254 https://doi.org/10.1007/978-3-642-03356-8_9
    255 rdf:type schema:CreativeWork
    256 sg:pub.10.1007/978-3-642-13190-5_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025305533
    257 https://doi.org/10.1007/978-3-642-13190-5_1
    258 rdf:type schema:CreativeWork
    259 sg:pub.10.1007/978-3-642-14165-2_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022822211
    260 https://doi.org/10.1007/978-3-642-14165-2_14
    261 rdf:type schema:CreativeWork
    262 sg:pub.10.1007/978-3-642-14623-7_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021668788
    263 https://doi.org/10.1007/978-3-642-14623-7_25
    264 rdf:type schema:CreativeWork
    265 sg:pub.10.1007/978-3-642-14623-7_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046902420
    266 https://doi.org/10.1007/978-3-642-14623-7_26
    267 rdf:type schema:CreativeWork
    268 sg:pub.10.1007/978-3-642-17373-8_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010136999
    269 https://doi.org/10.1007/978-3-642-17373-8_19
    270 rdf:type schema:CreativeWork
    271 sg:pub.10.1007/978-3-642-19571-6_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022245307
    272 https://doi.org/10.1007/978-3-642-19571-6_14
    273 rdf:type schema:CreativeWork
    274 sg:pub.10.1007/978-3-642-22792-9_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050489782
    275 https://doi.org/10.1007/978-3-642-22792-9_7
    276 rdf:type schema:CreativeWork
    277 sg:pub.10.1007/978-3-642-28914-9_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046350689
    278 https://doi.org/10.1007/978-3-642-28914-9_10
    279 rdf:type schema:CreativeWork
    280 sg:pub.10.1007/978-3-642-28914-9_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003687084
    281 https://doi.org/10.1007/978-3-642-28914-9_4
    282 rdf:type schema:CreativeWork
    283 sg:pub.10.1007/978-3-642-32009-5_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051014589
    284 https://doi.org/10.1007/978-3-642-32009-5_16
    285 rdf:type schema:CreativeWork
    286 sg:pub.10.1007/978-3-642-32284-6_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030412010
    287 https://doi.org/10.1007/978-3-642-32284-6_3
    288 rdf:type schema:CreativeWork
    289 sg:pub.10.1007/978-3-642-34961-4_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038456429
    290 https://doi.org/10.1007/978-3-642-34961-4_28
    291 rdf:type schema:CreativeWork
    292 sg:pub.10.1007/978-3-642-38348-9_37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041046155
    293 https://doi.org/10.1007/978-3-642-38348-9_37
    294 rdf:type schema:CreativeWork
    295 sg:pub.10.1007/978-3-662-45611-8_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010140710
    296 https://doi.org/10.1007/978-3-662-45611-8_28
    297 rdf:type schema:CreativeWork
    298 sg:pub.10.1007/978-3-662-49896-5_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015216783
    299 https://doi.org/10.1007/978-3-662-49896-5_11
    300 rdf:type schema:CreativeWork
    301 sg:pub.10.1007/bfb0055744 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011447978
    302 https://doi.org/10.1007/bfb0055744
    303 rdf:type schema:CreativeWork
    304 sg:pub.10.1007/pl00001606 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025900372
    305 https://doi.org/10.1007/pl00001606
    306 rdf:type schema:CreativeWork
    307 sg:pub.10.1007/s00037-002-0169-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039183238
    308 https://doi.org/10.1007/s00037-002-0169-0
    309 rdf:type schema:CreativeWork
    310 sg:pub.10.1007/s00037-009-0258-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041566190
    311 https://doi.org/10.1007/s00037-009-0258-4
    312 rdf:type schema:CreativeWork
    313 sg:pub.10.1007/s00145-016-9241-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031129963
    314 https://doi.org/10.1007/s00145-016-9241-9
    315 rdf:type schema:CreativeWork
    316 grid-institutes:grid.12136.37 schema:alternateName Tel Aviv University, Tel Aviv-Yafo, Israel
    317 schema:name Tel Aviv University, Tel Aviv-Yafo, Israel
    318 rdf:type schema:Organization
    319 grid-institutes:grid.19006.3e schema:alternateName Department of Computer Science and Department of Mathematics, UCLA, Los Angeles, CA, USA
    320 schema:name Department of Computer Science and Department of Mathematics, UCLA, Los Angeles, CA, USA
    321 rdf:type schema:Organization
    322 grid-institutes:grid.5333.6 schema:alternateName EPFL, Lausanne, Switzerland
    323 schema:name EPFL, Lausanne, Switzerland
    324 rdf:type schema:Organization
    325 grid-institutes:grid.6451.6 schema:alternateName Technion, Haifa, Israel
    326 schema:name Technion, Haifa, Israel
    327 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...