Automated Analysis of Cryptographic Assumptions in Generic Group Models View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-04

AUTHORS

Gilles Barthe, Edvard Fagerholm, Dario Fiore, John Mitchell, Andre Scedrov, Benedikt Schmidt

ABSTRACT

We initiate the study of principled, automated methods for analyzing hardness assumptions in generic group models, following the approach of symbolic cryptography. We start by defining a broad class of generic and symbolic group models for different settings—symmetric or asymmetric (leveled) k-linear groups—and by proving “computational soundness” theorems for the symbolic models. Based on this result, we formulate a very general master theorem that formally relates the hardness of a (possibly interactive) assumption in these models to solving problems in polynomial algebra. Then, we systematically analyze these problems. We identify different classes of assumptions and obtain decidability and undecidability results. Next, we develop and implement automated procedures for verifying the conditions of master theorems, and thus the validity of hardness assumptions in generic group models. The concrete outcome of this work is an automated tool which takes as input the statement of an assumption and outputs either a proof of its generic hardness or shows an algebraic attack against the assumption. More... »

PAGES

324-360

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00145-018-9302-3

DOI

http://dx.doi.org/10.1007/s00145-018-9302-3

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "IMDEA Software", 
          "id": "https://www.grid.ac/institutes/grid.482873.2", 
          "name": [
            "IMDEA Software Institute, Madrid, Spain"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Barthe", 
        "givenName": "Gilles", 
        "id": "sg:person.07405413654.89", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07405413654.89"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Nvidia (United States)", 
          "id": "https://www.grid.ac/institutes/grid.451133.1", 
          "name": [
            "IMDEA Software Institute, Madrid, Spain", 
            "University of Pennsylvania, Philadelphia, USA", 
            "NVIDIA, Santa Clara, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fagerholm", 
        "givenName": "Edvard", 
        "id": "sg:person.016067403444.70", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016067403444.70"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IMDEA Software", 
          "id": "https://www.grid.ac/institutes/grid.482873.2", 
          "name": [
            "IMDEA Software Institute, Madrid, Spain"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fiore", 
        "givenName": "Dario", 
        "id": "sg:person.015244547231.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015244547231.96"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Stanford University", 
          "id": "https://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Stanford University, Stanford, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mitchell", 
        "givenName": "John", 
        "id": "sg:person.016213414603.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016213414603.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Research University Higher School of Economics", 
          "id": "https://www.grid.ac/institutes/grid.410682.9", 
          "name": [
            "University of Pennsylvania, Philadelphia, USA", 
            "National Research University Higher School of Economics, Moscow, Russian Federation"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Scedrov", 
        "givenName": "Andre", 
        "id": "sg:person.014020623506.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014020623506.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Google (United States)", 
          "id": "https://www.grid.ac/institutes/grid.420451.6", 
          "name": [
            "IMDEA Software Institute, Madrid, Spain", 
            "Google, Mountain View, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schmidt", 
        "givenName": "Benedikt", 
        "id": "sg:person.010661720437.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010661720437.55"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/11586821_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045378480", 
          "https://doi.org/10.1007/11586821_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11586821_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045378480", 
          "https://doi.org/10.1007/11586821_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/322217.322225", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049137427"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00145-007-0203-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052635680", 
          "https://doi.org/10.1007/s00145-007-0203-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02113297", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1054501133", 
          "https://doi.org/10.1007/bf02113297"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02113297", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1054501133", 
          "https://doi.org/10.1007/bf02113297"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4064/fm-47-2-179-204", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091702675"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-04", 
    "datePublishedReg": "2019-04-01", 
    "description": "We initiate the study of principled, automated methods for analyzing hardness assumptions in generic group models, following the approach of symbolic cryptography. We start by defining a broad class of generic and symbolic group models for different settings\u2014symmetric or asymmetric (leveled) k-linear groups\u2014and by proving \u201ccomputational soundness\u201d theorems for the symbolic models. Based on this result, we formulate a very general master theorem that formally relates the hardness of a (possibly interactive) assumption in these models to solving problems in polynomial algebra. Then, we systematically analyze these problems. We identify different classes of assumptions and obtain decidability and undecidability results. Next, we develop and implement automated procedures for verifying the conditions of master theorems, and thus the validity of hardness assumptions in generic group models. The concrete outcome of this work is an automated tool which takes as input the statement of an assumption and outputs either a proof of its generic hardness or shows an algebraic attack against the assumption.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00145-018-9302-3", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3092819", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3092780", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3799310", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1136278", 
        "issn": [
          "0933-2790", 
          "1432-1378"
        ], 
        "name": "Journal of Cryptology", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "32"
      }
    ], 
    "name": "Automated Analysis of Cryptographic Assumptions in Generic Group Models", 
    "pagination": "324-360", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ce1b88cb455f56435bf285fcf87cd0184ecca20f0aaa29e4b3418a7039e2f390"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00145-018-9302-3"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1110755784"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00145-018-9302-3", 
      "https://app.dimensions.ai/details/publication/pub.1110755784"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T12:53", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000364_0000000364/records_72839_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00145-018-9302-3"
  }
]
 

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-018-9302-3'

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-018-9302-3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00145-018-9302-3'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00145-018-9302-3'


 

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

136 TRIPLES      21 PREDICATES      32 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00145-018-9302-3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N7636c6d61144436ca408f223c4c1d315
4 schema:citation sg:pub.10.1007/11586821_1
5 sg:pub.10.1007/bf02113297
6 sg:pub.10.1007/s00145-007-0203-0
7 https://doi.org/10.1145/322217.322225
8 https://doi.org/10.4064/fm-47-2-179-204
9 schema:datePublished 2019-04
10 schema:datePublishedReg 2019-04-01
11 schema:description We initiate the study of principled, automated methods for analyzing hardness assumptions in generic group models, following the approach of symbolic cryptography. We start by defining a broad class of generic and symbolic group models for different settings—symmetric or asymmetric (leveled) k-linear groups—and by proving “computational soundness” theorems for the symbolic models. Based on this result, we formulate a very general master theorem that formally relates the hardness of a (possibly interactive) assumption in these models to solving problems in polynomial algebra. Then, we systematically analyze these problems. We identify different classes of assumptions and obtain decidability and undecidability results. Next, we develop and implement automated procedures for verifying the conditions of master theorems, and thus the validity of hardness assumptions in generic group models. The concrete outcome of this work is an automated tool which takes as input the statement of an assumption and outputs either a proof of its generic hardness or shows an algebraic attack against the assumption.
12 schema:genre research_article
13 schema:inLanguage en
14 schema:isAccessibleForFree false
15 schema:isPartOf Nd54620d7ec4a4b7d88f612c2ba64ec66
16 Nf8dbc365039443bdaff95bf9e47086ac
17 sg:journal.1136278
18 schema:name Automated Analysis of Cryptographic Assumptions in Generic Group Models
19 schema:pagination 324-360
20 schema:productId Ncdda39b8254b44328a8de8fd46372687
21 Nd55b9f18ad44495495613867acc056b3
22 Nea4180912f1147a0a7ae13618462b1e5
23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110755784
24 https://doi.org/10.1007/s00145-018-9302-3
25 schema:sdDatePublished 2019-04-11T12:53
26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
27 schema:sdPublisher N2571c38aeea14f818c571c52f27cc27f
28 schema:url https://link.springer.com/10.1007%2Fs00145-018-9302-3
29 sgo:license sg:explorer/license/
30 sgo:sdDataset articles
31 rdf:type schema:ScholarlyArticle
32 N2571c38aeea14f818c571c52f27cc27f schema:name Springer Nature - SN SciGraph project
33 rdf:type schema:Organization
34 N2eb2794614e2484ea36b2683bdccd7fe rdf:first sg:person.015244547231.96
35 rdf:rest Na07a8d076e2d4205965a133c192a277a
36 N48d5654dccd9481ea5beb0ec7fb48324 rdf:first sg:person.016067403444.70
37 rdf:rest N2eb2794614e2484ea36b2683bdccd7fe
38 N5821398efc0c48c4966dc81f6bd01326 rdf:first sg:person.014020623506.63
39 rdf:rest N798f5621521e40f8b1433c246167b057
40 N7636c6d61144436ca408f223c4c1d315 rdf:first sg:person.07405413654.89
41 rdf:rest N48d5654dccd9481ea5beb0ec7fb48324
42 N798f5621521e40f8b1433c246167b057 rdf:first sg:person.010661720437.55
43 rdf:rest rdf:nil
44 Na07a8d076e2d4205965a133c192a277a rdf:first sg:person.016213414603.79
45 rdf:rest N5821398efc0c48c4966dc81f6bd01326
46 Ncdda39b8254b44328a8de8fd46372687 schema:name readcube_id
47 schema:value ce1b88cb455f56435bf285fcf87cd0184ecca20f0aaa29e4b3418a7039e2f390
48 rdf:type schema:PropertyValue
49 Nd54620d7ec4a4b7d88f612c2ba64ec66 schema:issueNumber 2
50 rdf:type schema:PublicationIssue
51 Nd55b9f18ad44495495613867acc056b3 schema:name doi
52 schema:value 10.1007/s00145-018-9302-3
53 rdf:type schema:PropertyValue
54 Nea4180912f1147a0a7ae13618462b1e5 schema:name dimensions_id
55 schema:value pub.1110755784
56 rdf:type schema:PropertyValue
57 Nf8dbc365039443bdaff95bf9e47086ac schema:volumeNumber 32
58 rdf:type schema:PublicationVolume
59 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
60 schema:name Information and Computing Sciences
61 rdf:type schema:DefinedTerm
62 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
63 schema:name Computation Theory and Mathematics
64 rdf:type schema:DefinedTerm
65 sg:grant.3092780 http://pending.schema.org/fundedItem sg:pub.10.1007/s00145-018-9302-3
66 rdf:type schema:MonetaryGrant
67 sg:grant.3092819 http://pending.schema.org/fundedItem sg:pub.10.1007/s00145-018-9302-3
68 rdf:type schema:MonetaryGrant
69 sg:grant.3799310 http://pending.schema.org/fundedItem sg:pub.10.1007/s00145-018-9302-3
70 rdf:type schema:MonetaryGrant
71 sg:journal.1136278 schema:issn 0933-2790
72 1432-1378
73 schema:name Journal of Cryptology
74 rdf:type schema:Periodical
75 sg:person.010661720437.55 schema:affiliation https://www.grid.ac/institutes/grid.420451.6
76 schema:familyName Schmidt
77 schema:givenName Benedikt
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010661720437.55
79 rdf:type schema:Person
80 sg:person.014020623506.63 schema:affiliation https://www.grid.ac/institutes/grid.410682.9
81 schema:familyName Scedrov
82 schema:givenName Andre
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014020623506.63
84 rdf:type schema:Person
85 sg:person.015244547231.96 schema:affiliation https://www.grid.ac/institutes/grid.482873.2
86 schema:familyName Fiore
87 schema:givenName Dario
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015244547231.96
89 rdf:type schema:Person
90 sg:person.016067403444.70 schema:affiliation https://www.grid.ac/institutes/grid.451133.1
91 schema:familyName Fagerholm
92 schema:givenName Edvard
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016067403444.70
94 rdf:type schema:Person
95 sg:person.016213414603.79 schema:affiliation https://www.grid.ac/institutes/grid.168010.e
96 schema:familyName Mitchell
97 schema:givenName John
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016213414603.79
99 rdf:type schema:Person
100 sg:person.07405413654.89 schema:affiliation https://www.grid.ac/institutes/grid.482873.2
101 schema:familyName Barthe
102 schema:givenName Gilles
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07405413654.89
104 rdf:type schema:Person
105 sg:pub.10.1007/11586821_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045378480
106 https://doi.org/10.1007/11586821_1
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/bf02113297 schema:sameAs https://app.dimensions.ai/details/publication/pub.1054501133
109 https://doi.org/10.1007/bf02113297
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/s00145-007-0203-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052635680
112 https://doi.org/10.1007/s00145-007-0203-0
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1145/322217.322225 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049137427
115 rdf:type schema:CreativeWork
116 https://doi.org/10.4064/fm-47-2-179-204 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091702675
117 rdf:type schema:CreativeWork
118 https://www.grid.ac/institutes/grid.168010.e schema:alternateName Stanford University
119 schema:name Stanford University, Stanford, USA
120 rdf:type schema:Organization
121 https://www.grid.ac/institutes/grid.410682.9 schema:alternateName National Research University Higher School of Economics
122 schema:name National Research University Higher School of Economics, Moscow, Russian Federation
123 University of Pennsylvania, Philadelphia, USA
124 rdf:type schema:Organization
125 https://www.grid.ac/institutes/grid.420451.6 schema:alternateName Google (United States)
126 schema:name Google, Mountain View, USA
127 IMDEA Software Institute, Madrid, Spain
128 rdf:type schema:Organization
129 https://www.grid.ac/institutes/grid.451133.1 schema:alternateName Nvidia (United States)
130 schema:name IMDEA Software Institute, Madrid, Spain
131 NVIDIA, Santa Clara, USA
132 University of Pennsylvania, Philadelphia, USA
133 rdf:type schema:Organization
134 https://www.grid.ac/institutes/grid.482873.2 schema:alternateName IMDEA Software
135 schema:name IMDEA Software Institute, Madrid, Spain
136 rdf:type schema:Organization
 




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


...