Cryptographic Primitives Based on Hard Learning Problems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1994

AUTHORS

Avrim Blum , Merrick Furst , Michael Kearns , Richard J. Lipton

ABSTRACT

Modern cryptography has had considerable impact on the development of computational learning theory. Virtually every intractability result in Valiant’s model [13] (which is representation-independent in the sense that it does not rely on an artificial syntactic restriction on the learning algorithm’s hypotheses) has at its heart a cryptographic construction [4, 9, 1, 10]. In this paper, we give results in the reverse direction by showing how to construct several cryptographic primitives based on certain assumptions on the difficulty of learning. In doing so, we develop further a line of thought introduced by Impagliazzo and Levin [6]. More... »

PAGES

278-291

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48329-2_24

DOI

http://dx.doi.org/10.1007/3-540-48329-2_24

DIMENSIONS

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


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": "Carnegie Mellon University, 15213, Pittsburgh, PA", 
          "id": "http://www.grid.ac/institutes/grid.147455.6", 
          "name": [
            "Carnegie Mellon University, 15213, Pittsburgh, PA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Blum", 
        "givenName": "Avrim", 
        "id": "sg:person.010510241243.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010510241243.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Carnegie Mellon University, 15213, Pittsburgh, PA", 
          "id": "http://www.grid.ac/institutes/grid.147455.6", 
          "name": [
            "Carnegie Mellon University, 15213, Pittsburgh, PA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Furst", 
        "givenName": "Merrick", 
        "id": "sg:person.0621550627.92", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621550627.92"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "AT&T Bell Labs, 07974, Murray Hill, NJ", 
          "id": "http://www.grid.ac/institutes/grid.469490.6", 
          "name": [
            "AT&T Bell Labs, 07974, Murray Hill, NJ"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kearns", 
        "givenName": "Michael", 
        "id": "sg:person.012047351500.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012047351500.33"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Princeton University, 08544, Princeton, NJ", 
          "id": "http://www.grid.ac/institutes/grid.16750.35", 
          "name": [
            "Princeton University, 08544, Princeton, NJ"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lipton", 
        "givenName": "Richard J.", 
        "id": "sg:person.010133373171.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010133373171.27"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1994", 
    "datePublishedReg": "1994-01-01", 
    "description": "Modern cryptography has had considerable impact on the development of computational learning theory. Virtually every intractability result in Valiant\u2019s model [13] (which is representation-independent in the sense that it does not rely on an artificial syntactic restriction on the learning algorithm\u2019s hypotheses) has at its heart a cryptographic construction [4, 9, 1, 10]. In this paper, we give results in the reverse direction by showing how to construct several cryptographic primitives based on certain assumptions on the difficulty of learning. In doing so, we develop further a line of thought introduced by Impagliazzo and Levin [6].", 
    "editor": [
      {
        "familyName": "Stinson", 
        "givenName": "Douglas R.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48329-2_24", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-57766-9", 
        "978-3-540-48329-8"
      ], 
      "name": "Advances in Cryptology \u2014 CRYPTO\u2019 93", 
      "type": "Book"
    }, 
    "keywords": [
      "cryptographic primitives", 
      "hard learning problems", 
      "computational learning theory", 
      "modern cryptography", 
      "cryptographic constructions", 
      "intractability results", 
      "difficulty of learning", 
      "learning problem", 
      "Valiant's model", 
      "primitives", 
      "learning theory", 
      "cryptography", 
      "learning", 
      "Impagliazzo", 
      "model", 
      "certain assumptions", 
      "line of thought", 
      "results", 
      "construction", 
      "difficulties", 
      "considerable impact", 
      "assumption", 
      "reverse direction", 
      "development", 
      "direction", 
      "theory", 
      "impact", 
      "lines", 
      "thought", 
      "Levin", 
      "heart", 
      "paper", 
      "problem"
    ], 
    "name": "Cryptographic Primitives Based on Hard Learning Problems", 
    "pagination": "278-291", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045214757"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48329-2_24"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48329-2_24", 
      "https://app.dimensions.ai/details/publication/pub.1045214757"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:36", 
    "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/chapter/chapter_68.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-48329-2_24"
  }
]
 

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/3-540-48329-2_24'

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/3-540-48329-2_24'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48329-2_24'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48329-2_24'


 

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

120 TRIPLES      23 PREDICATES      59 URIs      52 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48329-2_24 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5a58b30b011d4f14b6e1e66cc3bfebc4
4 schema:datePublished 1994
5 schema:datePublishedReg 1994-01-01
6 schema:description Modern cryptography has had considerable impact on the development of computational learning theory. Virtually every intractability result in Valiant’s model [13] (which is representation-independent in the sense that it does not rely on an artificial syntactic restriction on the learning algorithm’s hypotheses) has at its heart a cryptographic construction [4, 9, 1, 10]. In this paper, we give results in the reverse direction by showing how to construct several cryptographic primitives based on certain assumptions on the difficulty of learning. In doing so, we develop further a line of thought introduced by Impagliazzo and Levin [6].
7 schema:editor N56d704f5bb8b4908a83a4d2700e6c8f9
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N7e5b05b8359942b5a09708f783f66a64
12 schema:keywords Impagliazzo
13 Levin
14 Valiant's model
15 assumption
16 certain assumptions
17 computational learning theory
18 considerable impact
19 construction
20 cryptographic constructions
21 cryptographic primitives
22 cryptography
23 development
24 difficulties
25 difficulty of learning
26 direction
27 hard learning problems
28 heart
29 impact
30 intractability results
31 learning
32 learning problem
33 learning theory
34 line of thought
35 lines
36 model
37 modern cryptography
38 paper
39 primitives
40 problem
41 results
42 reverse direction
43 theory
44 thought
45 schema:name Cryptographic Primitives Based on Hard Learning Problems
46 schema:pagination 278-291
47 schema:productId N062fb07d085b4e9cac02ef8394217552
48 Nc3878753e34843aeb3f4c8572ad41c89
49 schema:publisher N1bd2262135904cc8bf6b9fa2ae9011ee
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045214757
51 https://doi.org/10.1007/3-540-48329-2_24
52 schema:sdDatePublished 2022-06-01T22:36
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher N6e622400555e42c6b654c04f1bdd3ad7
55 schema:url https://doi.org/10.1007/3-540-48329-2_24
56 sgo:license sg:explorer/license/
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N062fb07d085b4e9cac02ef8394217552 schema:name doi
60 schema:value 10.1007/3-540-48329-2_24
61 rdf:type schema:PropertyValue
62 N0b20c757a6344a75918cbb068404716a rdf:first sg:person.012047351500.33
63 rdf:rest N55c49e21dff241c5937c255682379721
64 N1bd2262135904cc8bf6b9fa2ae9011ee schema:name Springer Nature
65 rdf:type schema:Organisation
66 N55c49e21dff241c5937c255682379721 rdf:first sg:person.010133373171.27
67 rdf:rest rdf:nil
68 N56d704f5bb8b4908a83a4d2700e6c8f9 rdf:first N902ae02e1c554ac1a8bb5a2844905736
69 rdf:rest rdf:nil
70 N5a58b30b011d4f14b6e1e66cc3bfebc4 rdf:first sg:person.010510241243.49
71 rdf:rest Nbf6981c62aae435ca629bb438467c7f0
72 N6e622400555e42c6b654c04f1bdd3ad7 schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 N7e5b05b8359942b5a09708f783f66a64 schema:isbn 978-3-540-48329-8
75 978-3-540-57766-9
76 schema:name Advances in Cryptology — CRYPTO’ 93
77 rdf:type schema:Book
78 N902ae02e1c554ac1a8bb5a2844905736 schema:familyName Stinson
79 schema:givenName Douglas R.
80 rdf:type schema:Person
81 Nbf6981c62aae435ca629bb438467c7f0 rdf:first sg:person.0621550627.92
82 rdf:rest N0b20c757a6344a75918cbb068404716a
83 Nc3878753e34843aeb3f4c8572ad41c89 schema:name dimensions_id
84 schema:value pub.1045214757
85 rdf:type schema:PropertyValue
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
90 schema:name Computation Theory and Mathematics
91 rdf:type schema:DefinedTerm
92 sg:person.010133373171.27 schema:affiliation grid-institutes:grid.16750.35
93 schema:familyName Lipton
94 schema:givenName Richard J.
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010133373171.27
96 rdf:type schema:Person
97 sg:person.010510241243.49 schema:affiliation grid-institutes:grid.147455.6
98 schema:familyName Blum
99 schema:givenName Avrim
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010510241243.49
101 rdf:type schema:Person
102 sg:person.012047351500.33 schema:affiliation grid-institutes:grid.469490.6
103 schema:familyName Kearns
104 schema:givenName Michael
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012047351500.33
106 rdf:type schema:Person
107 sg:person.0621550627.92 schema:affiliation grid-institutes:grid.147455.6
108 schema:familyName Furst
109 schema:givenName Merrick
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621550627.92
111 rdf:type schema:Person
112 grid-institutes:grid.147455.6 schema:alternateName Carnegie Mellon University, 15213, Pittsburgh, PA
113 schema:name Carnegie Mellon University, 15213, Pittsburgh, PA
114 rdf:type schema:Organization
115 grid-institutes:grid.16750.35 schema:alternateName Princeton University, 08544, Princeton, NJ
116 schema:name Princeton University, 08544, Princeton, NJ
117 rdf:type schema:Organization
118 grid-institutes:grid.469490.6 schema:alternateName AT&T Bell Labs, 07974, Murray Hill, NJ
119 schema:name AT&T Bell Labs, 07974, Murray Hill, NJ
120 rdf:type schema:Organization
 




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


...