Protecting data privacy through hard-to-reverse negative databases View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2007-07-24

AUTHORS

Fernando Esponda, Elena S. Ackley, Paul Helman, Haixia Jia, Stephanie Forrest

ABSTRACT

A set DB of data elements can be represented in terms of its complement set, known as a negative database. That is, all of the elements not in DB are represented, and DB itself is not explicitly stored. This method of representing data has certain properties that are relevant for privacy enhancing applications. The paper reviews the negative database (NDB) representation scheme for storing a negative image compactly, and proposes using a collection of NDBs to represent a single DB, that is, one NDB is assigned for each record in DB. This method has the advantage of producing negative databases that are hard to reverse in practice, i.e., from which it is hard to obtain DB. This result is obtained by adapting a technique for generating hard-to-solve 3-SAT formulas. Finally we suggest potential avenues of application. More... »

PAGES

403-415

References to SciGraph publications

  • 2005-01-01. Private Matching in COMPUTER SECURITY IN THE 21ST CENTURY
  • 2004. Efficient Consistency Proofs for Generalized Queries on a Committed Database in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2002-09-13. Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials in ADVANCES IN CRYPTOLOGY — CRYPTO 2002
  • 1985. An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information in ADVANCES IN CRYPTOLOGY
  • 2004. Online Negative Databases in ARTIFICIAL IMMUNE SYSTEMS
  • 1994. One-Way Accumulators: A Decentralized Alternative to Digital Signatures in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’93
  • 1980. Cryptocomplexity and NP-completeness in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2004. Efficient Private Matching and Set Intersection in ADVANCES IN CRYPTOLOGY - EUROCRYPT 2004
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10207-007-0030-1

    DOI

    http://dx.doi.org/10.1007/s10207-007-0030-1

    DIMENSIONS

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


    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/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, Yale University, 06520-8285, New Haven, CT, USA", 
              "id": "http://www.grid.ac/institutes/grid.47100.32", 
              "name": [
                "Department of Computer Science, Yale University, 06520-8285, New Haven, CT, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Esponda", 
            "givenName": "Fernando", 
            "id": "sg:person.0720117634.32", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0720117634.32"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA", 
              "id": "http://www.grid.ac/institutes/grid.266832.b", 
              "name": [
                "Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ackley", 
            "givenName": "Elena S.", 
            "id": "sg:person.01124410703.95", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01124410703.95"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA", 
              "id": "http://www.grid.ac/institutes/grid.266832.b", 
              "name": [
                "Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Helman", 
            "givenName": "Paul", 
            "id": "sg:person.01034346234.77", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01034346234.77"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA", 
              "id": "http://www.grid.ac/institutes/grid.266832.b", 
              "name": [
                "Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Jia", 
            "givenName": "Haixia", 
            "id": "sg:person.010116576621.94", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010116576621.94"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA", 
              "id": "http://www.grid.ac/institutes/grid.266832.b", 
              "name": [
                "Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Forrest", 
            "givenName": "Stephanie", 
            "id": "sg:person.0712103012.64", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0712103012.64"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-45708-9_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037806224", 
              "https://doi.org/10.1007/3-540-45708-9_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27836-8_87", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014928758", 
              "https://doi.org/10.1007/978-3-540-27836-8_87"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-39568-7_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047006426", 
              "https://doi.org/10.1007/3-540-39568-7_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/0-387-24006-3_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029631805", 
              "https://doi.org/10.1007/0-387-24006-3_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30220-9_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018554980", 
              "https://doi.org/10.1007/978-3-540-30220-9_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48285-7_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004089232", 
              "https://doi.org/10.1007/3-540-48285-7_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-10003-2_71", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002294388", 
              "https://doi.org/10.1007/3-540-10003-2_71"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24676-3_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038434154", 
              "https://doi.org/10.1007/978-3-540-24676-3_1"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007-07-24", 
        "datePublishedReg": "2007-07-24", 
        "description": "A set DB of data elements can be represented in terms of its complement set, known as a negative database. That is, all of the elements not in DB are represented, and DB itself is not explicitly stored. This method of representing data has certain properties that are relevant for privacy enhancing applications. The paper reviews the negative database (NDB) representation scheme for storing a negative image compactly, and proposes using a collection of NDBs to represent a single DB, that is, one NDB is assigned for each record in DB. This method has the advantage of producing negative databases that are hard to reverse in practice, i.e., from which it is hard to obtain DB. This result is obtained by adapting a technique for generating hard-to-solve 3-SAT formulas. Finally we suggest potential avenues of application.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10207-007-0030-1", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1136826", 
            "issn": [
              "1615-5262", 
              "1615-5270"
            ], 
            "name": "International Journal of Information Security", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "6", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "6"
          }
        ], 
        "keywords": [
          "negative database", 
          "data privacy", 
          "enhancing applications", 
          "representation scheme", 
          "data elements", 
          "single DB", 
          "complement set", 
          "database", 
          "privacy", 
          "applications", 
          "certain properties", 
          "images", 
          "scheme", 
          "set", 
          "method", 
          "collection", 
          "NDB", 
          "advantages", 
          "technique", 
          "data", 
          "elements", 
          "terms", 
          "negative image", 
          "dB", 
          "records", 
          "results", 
          "practice", 
          "potential avenues", 
          "avenues", 
          "formula", 
          "properties", 
          "paper"
        ], 
        "name": "Protecting data privacy through hard-to-reverse negative databases", 
        "pagination": "403-415", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1027221555"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10207-007-0030-1"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10207-007-0030-1", 
          "https://app.dimensions.ai/details/publication/pub.1027221555"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:24", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_445.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10207-007-0030-1"
      }
    ]
     

    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/s10207-007-0030-1'

    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/s10207-007-0030-1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10207-007-0030-1'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10207-007-0030-1'


     

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

    153 TRIPLES      22 PREDICATES      65 URIs      49 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10207-007-0030-1 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N002ab2c6f669442686214123fc062cd8
    4 schema:citation sg:pub.10.1007/0-387-24006-3_3
    5 sg:pub.10.1007/3-540-10003-2_71
    6 sg:pub.10.1007/3-540-39568-7_23
    7 sg:pub.10.1007/3-540-45708-9_5
    8 sg:pub.10.1007/3-540-48285-7_24
    9 sg:pub.10.1007/978-3-540-24676-3_1
    10 sg:pub.10.1007/978-3-540-27836-8_87
    11 sg:pub.10.1007/978-3-540-30220-9_14
    12 schema:datePublished 2007-07-24
    13 schema:datePublishedReg 2007-07-24
    14 schema:description A set DB of data elements can be represented in terms of its complement set, known as a negative database. That is, all of the elements not in DB are represented, and DB itself is not explicitly stored. This method of representing data has certain properties that are relevant for privacy enhancing applications. The paper reviews the negative database (NDB) representation scheme for storing a negative image compactly, and proposes using a collection of NDBs to represent a single DB, that is, one NDB is assigned for each record in DB. This method has the advantage of producing negative databases that are hard to reverse in practice, i.e., from which it is hard to obtain DB. This result is obtained by adapting a technique for generating hard-to-solve 3-SAT formulas. Finally we suggest potential avenues of application.
    15 schema:genre article
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N8b63332fd20546f3bc79a8b425680f8e
    19 Nc247d57e81d6440296e6ed5929fa112c
    20 sg:journal.1136826
    21 schema:keywords NDB
    22 advantages
    23 applications
    24 avenues
    25 certain properties
    26 collection
    27 complement set
    28 dB
    29 data
    30 data elements
    31 data privacy
    32 database
    33 elements
    34 enhancing applications
    35 formula
    36 images
    37 method
    38 negative database
    39 negative image
    40 paper
    41 potential avenues
    42 practice
    43 privacy
    44 properties
    45 records
    46 representation scheme
    47 results
    48 scheme
    49 set
    50 single DB
    51 technique
    52 terms
    53 schema:name Protecting data privacy through hard-to-reverse negative databases
    54 schema:pagination 403-415
    55 schema:productId Nd450b9d93e8d4d9a9ef2ce8e44d1f1fa
    56 Nd4ee263dae714c5f97705500d3739f8f
    57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027221555
    58 https://doi.org/10.1007/s10207-007-0030-1
    59 schema:sdDatePublished 2022-05-20T07:24
    60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    61 schema:sdPublisher N6e94f9077d8a4df58a347e20fa37697f
    62 schema:url https://doi.org/10.1007/s10207-007-0030-1
    63 sgo:license sg:explorer/license/
    64 sgo:sdDataset articles
    65 rdf:type schema:ScholarlyArticle
    66 N002ab2c6f669442686214123fc062cd8 rdf:first sg:person.0720117634.32
    67 rdf:rest Ne59936abab714e18baaf22d0f9c34fb4
    68 N076980fb710044abaedbd6727b143e94 rdf:first sg:person.01034346234.77
    69 rdf:rest N290294d4e2c640f6bfae4e3ba33d544f
    70 N290294d4e2c640f6bfae4e3ba33d544f rdf:first sg:person.010116576621.94
    71 rdf:rest N832b72403a684e01a390191592f3b940
    72 N6e94f9077d8a4df58a347e20fa37697f schema:name Springer Nature - SN SciGraph project
    73 rdf:type schema:Organization
    74 N832b72403a684e01a390191592f3b940 rdf:first sg:person.0712103012.64
    75 rdf:rest rdf:nil
    76 N8b63332fd20546f3bc79a8b425680f8e schema:issueNumber 6
    77 rdf:type schema:PublicationIssue
    78 Nc247d57e81d6440296e6ed5929fa112c schema:volumeNumber 6
    79 rdf:type schema:PublicationVolume
    80 Nd450b9d93e8d4d9a9ef2ce8e44d1f1fa schema:name dimensions_id
    81 schema:value pub.1027221555
    82 rdf:type schema:PropertyValue
    83 Nd4ee263dae714c5f97705500d3739f8f schema:name doi
    84 schema:value 10.1007/s10207-007-0030-1
    85 rdf:type schema:PropertyValue
    86 Ne59936abab714e18baaf22d0f9c34fb4 rdf:first sg:person.01124410703.95
    87 rdf:rest N076980fb710044abaedbd6727b143e94
    88 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Information and Computing Sciences
    90 rdf:type schema:DefinedTerm
    91 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Information Systems
    93 rdf:type schema:DefinedTerm
    94 sg:journal.1136826 schema:issn 1615-5262
    95 1615-5270
    96 schema:name International Journal of Information Security
    97 schema:publisher Springer Nature
    98 rdf:type schema:Periodical
    99 sg:person.010116576621.94 schema:affiliation grid-institutes:grid.266832.b
    100 schema:familyName Jia
    101 schema:givenName Haixia
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010116576621.94
    103 rdf:type schema:Person
    104 sg:person.01034346234.77 schema:affiliation grid-institutes:grid.266832.b
    105 schema:familyName Helman
    106 schema:givenName Paul
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01034346234.77
    108 rdf:type schema:Person
    109 sg:person.01124410703.95 schema:affiliation grid-institutes:grid.266832.b
    110 schema:familyName Ackley
    111 schema:givenName Elena S.
    112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01124410703.95
    113 rdf:type schema:Person
    114 sg:person.0712103012.64 schema:affiliation grid-institutes:grid.266832.b
    115 schema:familyName Forrest
    116 schema:givenName Stephanie
    117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0712103012.64
    118 rdf:type schema:Person
    119 sg:person.0720117634.32 schema:affiliation grid-institutes:grid.47100.32
    120 schema:familyName Esponda
    121 schema:givenName Fernando
    122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0720117634.32
    123 rdf:type schema:Person
    124 sg:pub.10.1007/0-387-24006-3_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029631805
    125 https://doi.org/10.1007/0-387-24006-3_3
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/3-540-10003-2_71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002294388
    128 https://doi.org/10.1007/3-540-10003-2_71
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/3-540-39568-7_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047006426
    131 https://doi.org/10.1007/3-540-39568-7_23
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/3-540-45708-9_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037806224
    134 https://doi.org/10.1007/3-540-45708-9_5
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/3-540-48285-7_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004089232
    137 https://doi.org/10.1007/3-540-48285-7_24
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/978-3-540-24676-3_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038434154
    140 https://doi.org/10.1007/978-3-540-24676-3_1
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/978-3-540-27836-8_87 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014928758
    143 https://doi.org/10.1007/978-3-540-27836-8_87
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/978-3-540-30220-9_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018554980
    146 https://doi.org/10.1007/978-3-540-30220-9_14
    147 rdf:type schema:CreativeWork
    148 grid-institutes:grid.266832.b schema:alternateName Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA
    149 schema:name Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA
    150 rdf:type schema:Organization
    151 grid-institutes:grid.47100.32 schema:alternateName Department of Computer Science, Yale University, 06520-8285, New Haven, CT, USA
    152 schema:name Department of Computer Science, Yale University, 06520-8285, New Haven, CT, USA
    153 rdf:type schema:Organization
     




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


    ...