NDLI: Is privacy compatible with truthfulness?

Please wait, while we are loading the content...

Massive online teaching to bounded learners

Can theories be tested?: a cryptographic treatment of forecast testing

Is privacy compatible with truthfulness?

On the possibilities and limitations of pseudodeterministic algorithms

Towards an optimal query efficient PCP?

Approaching utopia: strong truthfulness and externality-resistant mechanisms

Reachability in graph timelines

A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games

An equational approach to secure multi-party computation

Time hierarchies for sampling distributions

Catch them if you can: how to serve impatient users

New affine-invariant codes from lifting

Learning mixtures of spherical gaussians: moment methods and spectral decompositions

Multiplicative updates in coordination games and the theory of evolution

Differentially private data analysis of social networks via restricted sensitivity

Evasiveness through a circuit lens

A characterization of approximation resistance for even k-partite CSPs

Parametric digital auctions

Runtime guarantees for regression problems

Adversary lower bound for the k-sum problem

Publicly verifiable proofs of sequential work

Properties and applications of boolean function composition

Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints

H-wise independence

Low-weight halfspaces for sparse boolean vectors

Making evolution rigorous: the error threshold

Characterizing the sample complexity of private learners

The garden-hose model

On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction

Learning and incentives in user-generated content: multi-armed bandits with endogenous arms

An energy complexity model for algorithms

Stronger methods of making quantum interactive proofs perfectly complete

On the power of nonuniformity in proofs of security

Pseudo-partitions, transversality and locality: a combinatorial characterization for the space measure in algebraic proof systems

Robust optimization in the presence of uncertainty

Sparse extractor families for all the entropy

Learnability of DNF with representation-specific queries

On the convergence of the Hegselmann-Krause system

Barriers in cryptography with weak, correlated and leaky sources

Space-bounded communication complexity

On the power of many one-bit provers

Welfare maximization and the supermodular degree

Streaming computations with a loquacious prover

Active self-assembly of algorithmic shapes and patterns in polylogarithmic time

Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract

Competing provers protocols for circuit evaluation

Sorting noisy data with partial information

On the power of conditional samples in distribution testing

Resource-based corruptions and the combinatorics of hidden diversity

Is privacy compatible with truthfulness?

Content Provider	ACM Digital Library
Author	Xiao, David
Abstract	In the area of privacy-preserving data mining, a differentially private mechanism intuitively encourages people to share their data because they are at little risk of revealing their own information. However, we argue that this interpretation is incomplete because external incentives are necessary for people to participate in databases, and so data release mechanisms should not only be differentially private but also compatible with incentives, otherwise the data collected may be false. We apply the notion of truthfulness from game theory to this problem. In certain settings, it turns out that existing differentially private mechanisms do not encourage participants to report their information truthfully. On the positive side, we exhibit a transformation that takes truthful mechanisms and transforms them into differentially private mechanisms that remain truthful. Our transformation applies to games where the type space is small and the goal is to optimize an insensitive quantity such as social welfare. Our transformation incurs only a small additive loss in optimality, and it is computationally efficient. Combined with the VCG mechanism, our transformation implies that there exists a differentially private, truthful, and approximately efficient mechanism for any social welfare game with small type space. We also study a model where an explicit numerical cost is assigned to the information leaked by a mechanism. We show that in this case, even differential privacy may not be strong enough of a notion to motivate people to participate truthfully. We show that mechanisms that release a perturbed histogram of the database may reveal too much information. We also show that, in general, any mechanism that outputs a synopsis that resembles the original database (such as the mechanism of Blum et al. (STOC '08)) may reveal too much information.
Starting Page	67
Ending Page	86
Page Count	20
File Format	PDF
ISBN	9781450318594
DOI	10.1145/2422436.2422448
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-01-09
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Differential privacy Mechanism design
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in