On Communication Protocols That Compute Almost Privately View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Marco Comi , Bhaskar DasGupta , Michael Schapira , Venkatakumar Srinivasan

ABSTRACT

A traditionally desired goal when designing auction mechanisms is incentive compatibility, i.e., ensuring that bidders fare best by truthfully reporting their preferences. A complementary goal, which has, thus far, received significantly less attention, is to preserve privacy, i.e., to ensure that bidders reveal no more information than necessary. We further investigate and generalize the approximate privacy model for two-party communication recently introduced by Feigenbaum et al. [8]. We explore the privacy properties of a natural class of communication protocols that we refer to as “dissection protocols”. Dissection protocols include, among others, the bisection auction in [9,10] and the bisection protocol for the millionaires problem in [8]. Informally, in a dissection protocol the communicating parties are restricted to answering simple questions of the form “Is your input between the values α and β (under a pre-defined order over the possible inputs)?”.We prove that for a large class of functions called tiling functions, which include the 2nd-price Vickrey auction, there always exists a dissection protocol that provides a constant average-case privacy approximation ratio for uniform or “almost uniform” probability distributions over inputs. To establish this result we present an interesting connection between the approximate privacy framework and basic concepts in computational geometry. We show that such a good privacy approximation ratio for tiling functions does not, in general, exist in the worst case. We also discuss extensions of the basic setup to more than two parties and to non-tiling functions, and provide calculations of privacy approximation ratios for two functions of interest. More... »

PAGES

44-56

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-24829-0_6

DOI

http://dx.doi.org/10.1007/978-3-642-24829-0_6

DIMENSIONS

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


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": "Department of Computer Science, University of Illinois at Chicago, 60607, IL", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 60607, IL"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Comi", 
        "givenName": "Marco", 
        "id": "sg:person.016704041233.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016704041233.25"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607, IL", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 60607, IL"
          ], 
          "type": "Organization"
        }, 
        "familyName": "DasGupta", 
        "givenName": "Bhaskar", 
        "id": "sg:person.0763403270.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Princeton University, 08540, Princeton, NJ", 
          "id": "http://www.grid.ac/institutes/grid.16750.35", 
          "name": [
            "Department of Computer Science, Princeton University, 08540, Princeton, NJ"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schapira", 
        "givenName": "Michael", 
        "id": "sg:person.015466710447.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015466710447.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607, IL", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 60607, IL"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Srinivasan", 
        "givenName": "Venkatakumar", 
        "id": "sg:person.013172533133.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013172533133.32"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "A traditionally desired goal when designing auction mechanisms is incentive compatibility, i.e., ensuring that bidders fare best by truthfully reporting their preferences. A complementary goal, which has, thus far, received significantly less attention, is to preserve privacy, i.e., to ensure that bidders reveal no more information than necessary. We further investigate and generalize the approximate privacy model for two-party communication recently introduced by Feigenbaum et al.\u00a0[8]. We explore the privacy properties of a natural class of communication protocols that we refer to as \u201cdissection protocols\u201d. Dissection protocols include, among others, the bisection auction in\u00a0[9,10] and the bisection protocol for the millionaires problem in\u00a0[8]. Informally, in a dissection protocol the communicating parties are restricted to answering simple questions of the form \u201cIs your input between the values \u03b1 and \u03b2 (under a pre-defined order over the possible inputs)?\u201d.We prove that for a large class of functions called tiling functions, which include the 2nd-price Vickrey auction, there always exists a dissection protocol that provides a constant average-case privacy approximation ratio for uniform or \u201calmost uniform\u201d probability distributions over inputs. To establish this result we present an interesting connection between the approximate privacy framework and basic concepts in computational geometry. We show that such a good privacy approximation ratio for tiling functions does not, in general, exist in the worst case. We also discuss extensions of the basic setup to more than two parties and to non-tiling functions, and provide calculations of privacy approximation ratios for two functions of interest.", 
    "editor": [
      {
        "familyName": "Persiano", 
        "givenName": "Giuseppe", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-24829-0_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-24828-3", 
        "978-3-642-24829-0"
      ], 
      "name": "Algorithmic Game Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "approximation ratio", 
      "computational geometry", 
      "Feigenbaum et al", 
      "function of interest", 
      "probability distribution", 
      "large class", 
      "interesting connection", 
      "natural class", 
      "value \u03b1", 
      "basic concepts", 
      "basic setup", 
      "worst case", 
      "Vickrey auction", 
      "class", 
      "millionaire problem", 
      "et al", 
      "auction mechanism", 
      "function", 
      "geometry", 
      "communication protocols", 
      "input", 
      "calculations", 
      "problem", 
      "auctions", 
      "extension", 
      "incentive compatibility", 
      "model", 
      "simple question", 
      "uniform", 
      "distribution", 
      "properties", 
      "more information", 
      "framework", 
      "bidders", 
      "setup", 
      "connection", 
      "complementary goals", 
      "privacy model", 
      "al", 
      "form", 
      "ratio", 
      "two-party communication", 
      "privacy framework", 
      "concept", 
      "cases", 
      "communication", 
      "goal", 
      "results", 
      "interest", 
      "privacy properties", 
      "information", 
      "protocol", 
      "less attention", 
      "compatibility", 
      "questions", 
      "attention", 
      "mechanism", 
      "privacy", 
      "preferences", 
      "parties", 
      "dissection", 
      "dissection protocol"
    ], 
    "name": "On Communication Protocols That Compute Almost Privately", 
    "pagination": "44-56", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038836899"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-24829-0_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-24829-0_6", 
      "https://app.dimensions.ai/details/publication/pub.1038836899"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:42", 
    "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/chapter/chapter_171.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-24829-0_6"
  }
]
 

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/978-3-642-24829-0_6'

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/978-3-642-24829-0_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-24829-0_6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-24829-0_6'


 

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

146 TRIPLES      23 PREDICATES      88 URIs      81 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-24829-0_6 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nad86a6458b2c471e9f6f32caf934e268
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description A traditionally desired goal when designing auction mechanisms is incentive compatibility, i.e., ensuring that bidders fare best by truthfully reporting their preferences. A complementary goal, which has, thus far, received significantly less attention, is to preserve privacy, i.e., to ensure that bidders reveal no more information than necessary. We further investigate and generalize the approximate privacy model for two-party communication recently introduced by Feigenbaum et al. [8]. We explore the privacy properties of a natural class of communication protocols that we refer to as “dissection protocols”. Dissection protocols include, among others, the bisection auction in [9,10] and the bisection protocol for the millionaires problem in [8]. Informally, in a dissection protocol the communicating parties are restricted to answering simple questions of the form “Is your input between the values α and β (under a pre-defined order over the possible inputs)?”.We prove that for a large class of functions called tiling functions, which include the 2nd-price Vickrey auction, there always exists a dissection protocol that provides a constant average-case privacy approximation ratio for uniform or “almost uniform” probability distributions over inputs. To establish this result we present an interesting connection between the approximate privacy framework and basic concepts in computational geometry. We show that such a good privacy approximation ratio for tiling functions does not, in general, exist in the worst case. We also discuss extensions of the basic setup to more than two parties and to non-tiling functions, and provide calculations of privacy approximation ratios for two functions of interest.
7 schema:editor N4acb46495a544167a5e382918efc35c7
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nf88dfcc60fa24f22ae004f64120ddab4
12 schema:keywords Feigenbaum et al
13 Vickrey auction
14 al
15 approximation ratio
16 attention
17 auction mechanism
18 auctions
19 basic concepts
20 basic setup
21 bidders
22 calculations
23 cases
24 class
25 communication
26 communication protocols
27 compatibility
28 complementary goals
29 computational geometry
30 concept
31 connection
32 dissection
33 dissection protocol
34 distribution
35 et al
36 extension
37 form
38 framework
39 function
40 function of interest
41 geometry
42 goal
43 incentive compatibility
44 information
45 input
46 interest
47 interesting connection
48 large class
49 less attention
50 mechanism
51 millionaire problem
52 model
53 more information
54 natural class
55 parties
56 preferences
57 privacy
58 privacy framework
59 privacy model
60 privacy properties
61 probability distribution
62 problem
63 properties
64 protocol
65 questions
66 ratio
67 results
68 setup
69 simple question
70 two-party communication
71 uniform
72 value α
73 worst case
74 schema:name On Communication Protocols That Compute Almost Privately
75 schema:pagination 44-56
76 schema:productId N85b51585366c461d8ad02ab92f660227
77 Ne63b57f385ab4535a7f05fb3cd6dba0b
78 schema:publisher N262312833c194a5b87866aa7f6069ca2
79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038836899
80 https://doi.org/10.1007/978-3-642-24829-0_6
81 schema:sdDatePublished 2022-05-20T07:42
82 schema:sdLicense https://scigraph.springernature.com/explorer/license/
83 schema:sdPublisher N619c5b5827f7486ca865c24d1fcc8a7c
84 schema:url https://doi.org/10.1007/978-3-642-24829-0_6
85 sgo:license sg:explorer/license/
86 sgo:sdDataset chapters
87 rdf:type schema:Chapter
88 N262312833c194a5b87866aa7f6069ca2 schema:name Springer Nature
89 rdf:type schema:Organisation
90 N3ce1d13adfe84aa58c868ff5722db410 rdf:first sg:person.013172533133.32
91 rdf:rest rdf:nil
92 N4acb46495a544167a5e382918efc35c7 rdf:first N87bb9ddd1584499f984583cac242e7f9
93 rdf:rest rdf:nil
94 N619c5b5827f7486ca865c24d1fcc8a7c schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 N79fb1d64a3db44b1a9602eabd4006e5f rdf:first sg:person.0763403270.10
97 rdf:rest Nfc1953479a784a82987094c04d223ba3
98 N85b51585366c461d8ad02ab92f660227 schema:name dimensions_id
99 schema:value pub.1038836899
100 rdf:type schema:PropertyValue
101 N87bb9ddd1584499f984583cac242e7f9 schema:familyName Persiano
102 schema:givenName Giuseppe
103 rdf:type schema:Person
104 Nad86a6458b2c471e9f6f32caf934e268 rdf:first sg:person.016704041233.25
105 rdf:rest N79fb1d64a3db44b1a9602eabd4006e5f
106 Ne63b57f385ab4535a7f05fb3cd6dba0b schema:name doi
107 schema:value 10.1007/978-3-642-24829-0_6
108 rdf:type schema:PropertyValue
109 Nf88dfcc60fa24f22ae004f64120ddab4 schema:isbn 978-3-642-24828-3
110 978-3-642-24829-0
111 schema:name Algorithmic Game Theory
112 rdf:type schema:Book
113 Nfc1953479a784a82987094c04d223ba3 rdf:first sg:person.015466710447.45
114 rdf:rest N3ce1d13adfe84aa58c868ff5722db410
115 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
116 schema:name Information and Computing Sciences
117 rdf:type schema:DefinedTerm
118 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
119 schema:name Data Format
120 rdf:type schema:DefinedTerm
121 sg:person.013172533133.32 schema:affiliation grid-institutes:grid.185648.6
122 schema:familyName Srinivasan
123 schema:givenName Venkatakumar
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013172533133.32
125 rdf:type schema:Person
126 sg:person.015466710447.45 schema:affiliation grid-institutes:grid.16750.35
127 schema:familyName Schapira
128 schema:givenName Michael
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015466710447.45
130 rdf:type schema:Person
131 sg:person.016704041233.25 schema:affiliation grid-institutes:grid.185648.6
132 schema:familyName Comi
133 schema:givenName Marco
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016704041233.25
135 rdf:type schema:Person
136 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.185648.6
137 schema:familyName DasGupta
138 schema:givenName Bhaskar
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
140 rdf:type schema:Person
141 grid-institutes:grid.16750.35 schema:alternateName Department of Computer Science, Princeton University, 08540, Princeton, NJ
142 schema:name Department of Computer Science, Princeton University, 08540, Princeton, NJ
143 rdf:type schema:Organization
144 grid-institutes:grid.185648.6 schema:alternateName Department of Computer Science, University of Illinois at Chicago, 60607, IL
145 schema:name Department of Computer Science, University of Illinois at Chicago, 60607, IL
146 rdf:type schema:Organization
 




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


...