Negative representations of information View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2009-04-14

AUTHORS

Fernando Esponda, Stephanie Forrest, Paul Helman

ABSTRACT

In a negative representation, a set of elements (the positive representation) is depicted by its complement set. That is, the elements in the positive representation are not explicitly stored, and those in the negative representation are. The concept, feasibility, and properties of negative representations are explored in the paper; in particular, its potential to address privacy concerns. It is shown that a positive representation consisting of n l-bit strings can be represented negatively using only O(ln) strings, through the use of an additional symbol. It is also shown that membership queries for the positive representation can be processed against the negative representation in time no worse than linear in its size, while reconstructing the original positive set from its negative representation is an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{NP}}$$\end{document} -hard problem. The paper introduces algorithms for constructing negative representations as well as operations for updating and maintaining them. More... »

PAGES

331-345

References to SciGraph publications

  • 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
  • 2007-01-01. Efficient Negative Databases from Cryptographic Hash Functions in INFORMATION SECURITY
  • 2008. Hiding a Needle in a Haystack Using Negative Databases in INFORMATION HIDING
  • 2006. Secure Set Membership Using 3Sat in INFORMATION AND COMMUNICATIONS SECURITY
  • 2007-07-24. Protecting data privacy through hard-to-reverse negative databases in INTERNATIONAL JOURNAL OF INFORMATION SECURITY
  • 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-009-0078-1

    DOI

    http://dx.doi.org/10.1007/s10207-009-0078-1

    DIMENSIONS

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


    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/15", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Commerce, Management, Tourism and Services", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, Instituto Tecnol\u00f3gico Aut\u00f3nomo de M\u00e9xico, Mexico, D.F., Mexico", 
              "id": "http://www.grid.ac/institutes/grid.454349.b", 
              "name": [
                "Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA", 
                "Department of Computer Science, Instituto Tecnol\u00f3gico Aut\u00f3nomo de M\u00e9xico, Mexico, D.F., Mexico"
              ], 
              "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": "Santa Fe Institute, 1399 Hyde Park Road, 87501, Santa Fe, NM, USA", 
              "id": "http://www.grid.ac/institutes/grid.209665.e", 
              "name": [
                "Santa Fe Institute, 1399 Hyde Park Road, 87501, Santa Fe, 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"
          }, 
          {
            "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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s10207-007-0030-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027221555", 
              "https://doi.org/10.1007/s10207-007-0030-1"
            ], 
            "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/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/978-3-540-75496-1_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036958248", 
              "https://doi.org/10.1007/978-3-540-75496-1_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-88961-8_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024671221", 
              "https://doi.org/10.1007/978-3-540-88961-8_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11935308_32", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047621097", 
              "https://doi.org/10.1007/11935308_32"
            ], 
            "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"
          }, 
          {
            "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/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"
          }
        ], 
        "datePublished": "2009-04-14", 
        "datePublishedReg": "2009-04-14", 
        "description": "In a negative representation, a set of elements (the positive representation) is depicted by its complement set. That is, the elements in the positive representation are not explicitly stored, and those in the negative representation are. The concept, feasibility, and properties of negative representations are explored in the paper; in particular, its potential to address privacy concerns. It is shown that a positive representation consisting of n l-bit strings can be represented negatively using only O(ln) strings, through the use of an additional symbol. It is also shown that membership queries for the positive representation can be processed against the negative representation in time no worse than linear in its size, while reconstructing the original positive set from its negative representation is an \\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}$${\\mathcal{NP}}$$\\end{document} -hard problem. The paper introduces algorithms for constructing negative representations as well as operations for updating and maintaining them.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10207-009-0078-1", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136826", 
            "issn": [
              "1615-5262", 
              "1615-5270"
            ], 
            "name": "International Journal of Information Security", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "5", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "8"
          }
        ], 
        "keywords": [
          "privacy concerns", 
          "membership queries", 
          "bit strings", 
          "set of elements", 
          "complement set", 
          "representation", 
          "additional symbols", 
          "set", 
          "queries", 
          "algorithm", 
          "strings", 
          "positive set", 
          "information", 
          "operation", 
          "symbols", 
          "feasibility", 
          "concept", 
          "elements", 
          "time", 
          "use", 
          "concern", 
          "negative representations", 
          "size", 
          "potential", 
          "properties", 
          "positive representations", 
          "problem", 
          "paper", 
          "original positive set"
        ], 
        "name": "Negative representations of information", 
        "pagination": "331-345", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1001498892"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10207-009-0078-1"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10207-009-0078-1", 
          "https://app.dimensions.ai/details/publication/pub.1001498892"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:21", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_493.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10207-009-0078-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-009-0078-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-009-0078-1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10207-009-0078-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-009-0078-1'


     

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

    144 TRIPLES      22 PREDICATES      63 URIs      46 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10207-009-0078-1 schema:about anzsrc-for:08
    2 anzsrc-for:15
    3 schema:author N615a49e08eca44a28c7388efb4558afd
    4 schema:citation sg:pub.10.1007/11935308_32
    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/978-3-540-24676-3_1
    9 sg:pub.10.1007/978-3-540-27836-8_87
    10 sg:pub.10.1007/978-3-540-75496-1_28
    11 sg:pub.10.1007/978-3-540-88961-8_2
    12 sg:pub.10.1007/s10207-007-0030-1
    13 schema:datePublished 2009-04-14
    14 schema:datePublishedReg 2009-04-14
    15 schema:description In a negative representation, a set of elements (the positive representation) is depicted by its complement set. That is, the elements in the positive representation are not explicitly stored, and those in the negative representation are. The concept, feasibility, and properties of negative representations are explored in the paper; in particular, its potential to address privacy concerns. It is shown that a positive representation consisting of n l-bit strings can be represented negatively using only O(ln) strings, through the use of an additional symbol. It is also shown that membership queries for the positive representation can be processed against the negative representation in time no worse than linear in its size, while reconstructing the original positive set from its negative representation is an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{NP}}$$\end{document} -hard problem. The paper introduces algorithms for constructing negative representations as well as operations for updating and maintaining them.
    16 schema:genre article
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf N9aaa1427526c47c583f7b2981427b693
    20 Nab3ce982839f400cb70e10bb1ba97d24
    21 sg:journal.1136826
    22 schema:keywords additional symbols
    23 algorithm
    24 bit strings
    25 complement set
    26 concept
    27 concern
    28 elements
    29 feasibility
    30 information
    31 membership queries
    32 negative representations
    33 operation
    34 original positive set
    35 paper
    36 positive representations
    37 positive set
    38 potential
    39 privacy concerns
    40 problem
    41 properties
    42 queries
    43 representation
    44 set
    45 set of elements
    46 size
    47 strings
    48 symbols
    49 time
    50 use
    51 schema:name Negative representations of information
    52 schema:pagination 331-345
    53 schema:productId N584e1f1b6bd047088ef2ed72243c9f1b
    54 N5de1ce1d7df4452292d27c435fb8b4e2
    55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001498892
    56 https://doi.org/10.1007/s10207-009-0078-1
    57 schema:sdDatePublished 2021-12-01T19:21
    58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    59 schema:sdPublisher N40fc593093214ed384a4d418c99fc457
    60 schema:url https://doi.org/10.1007/s10207-009-0078-1
    61 sgo:license sg:explorer/license/
    62 sgo:sdDataset articles
    63 rdf:type schema:ScholarlyArticle
    64 N11a80432c220440196eb12faac2880e0 rdf:first sg:person.01034346234.77
    65 rdf:rest rdf:nil
    66 N40fc593093214ed384a4d418c99fc457 schema:name Springer Nature - SN SciGraph project
    67 rdf:type schema:Organization
    68 N584e1f1b6bd047088ef2ed72243c9f1b schema:name doi
    69 schema:value 10.1007/s10207-009-0078-1
    70 rdf:type schema:PropertyValue
    71 N5de1ce1d7df4452292d27c435fb8b4e2 schema:name dimensions_id
    72 schema:value pub.1001498892
    73 rdf:type schema:PropertyValue
    74 N615a49e08eca44a28c7388efb4558afd rdf:first sg:person.0720117634.32
    75 rdf:rest Na9f4d58c628149c5b50e01471d057721
    76 N9aaa1427526c47c583f7b2981427b693 schema:volumeNumber 8
    77 rdf:type schema:PublicationVolume
    78 Na9f4d58c628149c5b50e01471d057721 rdf:first sg:person.0712103012.64
    79 rdf:rest N11a80432c220440196eb12faac2880e0
    80 Nab3ce982839f400cb70e10bb1ba97d24 schema:issueNumber 5
    81 rdf:type schema:PublicationIssue
    82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    83 schema:name Information and Computing Sciences
    84 rdf:type schema:DefinedTerm
    85 anzsrc-for:15 schema:inDefinedTermSet anzsrc-for:
    86 schema:name Commerce, Management, Tourism and Services
    87 rdf:type schema:DefinedTerm
    88 sg:journal.1136826 schema:issn 1615-5262
    89 1615-5270
    90 schema:name International Journal of Information Security
    91 schema:publisher Springer Nature
    92 rdf:type schema:Periodical
    93 sg:person.01034346234.77 schema:affiliation grid-institutes:grid.266832.b
    94 schema:familyName Helman
    95 schema:givenName Paul
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01034346234.77
    97 rdf:type schema:Person
    98 sg:person.0712103012.64 schema:affiliation grid-institutes:grid.209665.e
    99 schema:familyName Forrest
    100 schema:givenName Stephanie
    101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0712103012.64
    102 rdf:type schema:Person
    103 sg:person.0720117634.32 schema:affiliation grid-institutes:grid.454349.b
    104 schema:familyName Esponda
    105 schema:givenName Fernando
    106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0720117634.32
    107 rdf:type schema:Person
    108 sg:pub.10.1007/11935308_32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047621097
    109 https://doi.org/10.1007/11935308_32
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/3-540-10003-2_71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002294388
    112 https://doi.org/10.1007/3-540-10003-2_71
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/3-540-39568-7_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047006426
    115 https://doi.org/10.1007/3-540-39568-7_23
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/3-540-45708-9_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037806224
    118 https://doi.org/10.1007/3-540-45708-9_5
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/978-3-540-24676-3_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038434154
    121 https://doi.org/10.1007/978-3-540-24676-3_1
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/978-3-540-27836-8_87 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014928758
    124 https://doi.org/10.1007/978-3-540-27836-8_87
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/978-3-540-75496-1_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036958248
    127 https://doi.org/10.1007/978-3-540-75496-1_28
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/978-3-540-88961-8_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024671221
    130 https://doi.org/10.1007/978-3-540-88961-8_2
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/s10207-007-0030-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027221555
    133 https://doi.org/10.1007/s10207-007-0030-1
    134 rdf:type schema:CreativeWork
    135 grid-institutes:grid.209665.e schema:alternateName Santa Fe Institute, 1399 Hyde Park Road, 87501, Santa Fe, NM, USA
    136 schema:name Santa Fe Institute, 1399 Hyde Park Road, 87501, Santa Fe, NM, USA
    137 rdf:type schema:Organization
    138 grid-institutes:grid.266832.b schema:alternateName Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA
    139 schema:name Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA
    140 rdf:type schema:Organization
    141 grid-institutes:grid.454349.b schema:alternateName Department of Computer Science, Instituto Tecnológico Autónomo de México, Mexico, D.F., Mexico
    142 schema:name Department of Computer Science, Instituto Tecnológico Autónomo de México, Mexico, D.F., Mexico
    143 Department of Computer Science, University of New Mexico, 87131-1386, Albuquerque, NM, USA
    144 rdf:type schema:Organization
     




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


    ...