Polylogarithmic Private Approximations and Efficient Matching View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2006

AUTHORS

Piotr Indyk , David Woodruff

ABSTRACT

In [12] a private approximation of a function f is defined to be another function F that approximates f in the usual sense, but does not reveal any information about x other than what can be deduced from f(x). We give the first two-party private approximation of the l2 distance with polylogarithmic communication. This, in particular, resolves the main open question of [12].We then look at the private near neighbor problem in which Alice has a query point in {0,1}d and Bob a set of n points in {0,1}d, and Alice should privately learn the point closest to her query. We improve upon existing protocols, resolving open questions of [13,10]. Then, we relax the problem by defining the private approximate near neighbor problem, which requires introducing a notion of secure computation of approximations for functions that return sets of points rather than values. For this problem we give several protocols with sublinear communication. More... »

PAGES

245-264

Book

TITLE

Theory of Cryptography

ISBN

978-3-540-32731-8
978-3-540-32732-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11681878_13

DOI

http://dx.doi.org/10.1007/11681878_13

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "MIT CSAIL, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT CSAIL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Indyk", 
        "givenName": "Piotr", 
        "id": "sg:person.013046250651.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013046250651.69"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Tsinghua University, China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "MIT CSAIL, USA", 
            "Tsinghua University, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Woodruff", 
        "givenName": "David", 
        "id": "sg:person.012727410605.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "In [12] a private approximation of a function f is defined to be another function F that approximates f in the usual sense, but does not reveal any information about x other than what can be deduced from f(x). We give the first two-party private approximation of the l2 distance with polylogarithmic communication. This, in particular, resolves the main open question of [12].We then look at the private near neighbor problem in which Alice has a query point in {0,1}d and Bob a set of n points in {0,1}d, and Alice should privately learn the point closest to her query. We improve upon existing protocols, resolving open questions of [13,10]. Then, we relax the problem by defining the private approximate near neighbor problem, which requires introducing a notion of secure computation of approximations for functions that return sets of points rather than values. For this problem we give several protocols with sublinear communication.", 
    "editor": [
      {
        "familyName": "Halevi", 
        "givenName": "Shai", 
        "type": "Person"
      }, 
      {
        "familyName": "Rabin", 
        "givenName": "Tal", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11681878_13", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-32731-8", 
        "978-3-540-32732-5"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "private approximation", 
      "neighbor problem", 
      "secure computation", 
      "query point", 
      "polylogarithmic communication", 
      "sublinear communication", 
      "efficient matching", 
      "L2 distance", 
      "set of points", 
      "main open questions", 
      "communication", 
      "queries", 
      "n points", 
      "open question", 
      "set", 
      "protocol", 
      "Alice", 
      "computation", 
      "matching", 
      "information", 
      "point", 
      "Bob", 
      "function f", 
      "approximates", 
      "approximation", 
      "notion", 
      "distance", 
      "questions", 
      "sense", 
      "usual sense", 
      "function", 
      "values", 
      "problem"
    ], 
    "name": "Polylogarithmic Private Approximations and Efficient Matching", 
    "pagination": "245-264", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024168936"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11681878_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11681878_13", 
      "https://app.dimensions.ai/details/publication/pub.1024168936"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:13", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_201.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11681878_13"
  }
]
 

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/11681878_13'

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/11681878_13'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11681878_13'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11681878_13'


 

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

108 TRIPLES      22 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11681878_13 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N9f8007c044d8454b84735dc856558b39
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description In [12] a private approximation of a function f is defined to be another function F that approximates f in the usual sense, but does not reveal any information about x other than what can be deduced from f(x). We give the first two-party private approximation of the l2 distance with polylogarithmic communication. This, in particular, resolves the main open question of [12].We then look at the private near neighbor problem in which Alice has a query point in {0,1}d and Bob a set of n points in {0,1}d, and Alice should privately learn the point closest to her query. We improve upon existing protocols, resolving open questions of [13,10]. Then, we relax the problem by defining the private approximate near neighbor problem, which requires introducing a notion of secure computation of approximations for functions that return sets of points rather than values. For this problem we give several protocols with sublinear communication.
7 schema:editor N720967bcf84842699e22466f2fd02634
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N612d88efaa894d76bcc5f3355afd3cfe
11 schema:keywords Alice
12 Bob
13 L2 distance
14 approximates
15 approximation
16 communication
17 computation
18 distance
19 efficient matching
20 function
21 function f
22 information
23 main open questions
24 matching
25 n points
26 neighbor problem
27 notion
28 open question
29 point
30 polylogarithmic communication
31 private approximation
32 problem
33 protocol
34 queries
35 query point
36 questions
37 secure computation
38 sense
39 set
40 set of points
41 sublinear communication
42 usual sense
43 values
44 schema:name Polylogarithmic Private Approximations and Efficient Matching
45 schema:pagination 245-264
46 schema:productId N6a4b0b19260c4bc283c850e3132e31d4
47 N9ffc7f0f286f444385393f1c1a38ced8
48 schema:publisher Ne2ae8b6dd8694c30913c5d01b9670522
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024168936
50 https://doi.org/10.1007/11681878_13
51 schema:sdDatePublished 2022-11-24T21:13
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N8b74c81dbd804c98bae9336d70ce3a23
54 schema:url https://doi.org/10.1007/11681878_13
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N5f8df626a3d34111990a930e2bd568ce schema:familyName Rabin
59 schema:givenName Tal
60 rdf:type schema:Person
61 N612d88efaa894d76bcc5f3355afd3cfe schema:isbn 978-3-540-32731-8
62 978-3-540-32732-5
63 schema:name Theory of Cryptography
64 rdf:type schema:Book
65 N626a3c7fc4b040c6b748e7490d118321 rdf:first sg:person.012727410605.86
66 rdf:rest rdf:nil
67 N6a4b0b19260c4bc283c850e3132e31d4 schema:name doi
68 schema:value 10.1007/11681878_13
69 rdf:type schema:PropertyValue
70 N720967bcf84842699e22466f2fd02634 rdf:first N88425dfc9f814618bd18ae728389eb7b
71 rdf:rest Nda3173b010694605917241b0f9726902
72 N88425dfc9f814618bd18ae728389eb7b schema:familyName Halevi
73 schema:givenName Shai
74 rdf:type schema:Person
75 N8b74c81dbd804c98bae9336d70ce3a23 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 N9f8007c044d8454b84735dc856558b39 rdf:first sg:person.013046250651.69
78 rdf:rest N626a3c7fc4b040c6b748e7490d118321
79 N9ffc7f0f286f444385393f1c1a38ced8 schema:name dimensions_id
80 schema:value pub.1024168936
81 rdf:type schema:PropertyValue
82 Nda3173b010694605917241b0f9726902 rdf:first N5f8df626a3d34111990a930e2bd568ce
83 rdf:rest rdf:nil
84 Ne2ae8b6dd8694c30913c5d01b9670522 schema:name Springer Nature
85 rdf:type schema:Organisation
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
90 schema:name Data Format
91 rdf:type schema:DefinedTerm
92 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.12527.33
93 schema:familyName Woodruff
94 schema:givenName David
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
96 rdf:type schema:Person
97 sg:person.013046250651.69 schema:affiliation grid-institutes:grid.116068.8
98 schema:familyName Indyk
99 schema:givenName Piotr
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013046250651.69
101 rdf:type schema:Person
102 grid-institutes:grid.116068.8 schema:alternateName MIT CSAIL, USA
103 schema:name MIT CSAIL, USA
104 rdf:type schema:Organization
105 grid-institutes:grid.12527.33 schema:alternateName Tsinghua University, China
106 schema:name MIT CSAIL, USA
107 Tsinghua University, China
108 rdf:type schema:Organization
 




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


...