On the complexity of aggregating information for authentication and profiling

Christian A. Duncan, Vir V. Phoha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Motivated by applications in online privacy, user authentication and profiling, we discuss the complexity of various problems generalized from the classic 0-1 knapsack problem. In our scenarios, we assume the existence of a scoring function that evaluates the confidence in the personal online profile or authenticity of an individual based on a subset of acquired credentials and facts about an individual and show how the specific properties of that function affect the computational complexity of the problem, providing both NP-completeness proofs under certain conditions as well as pseudo-polynomial- time solutions under others.

Original languageEnglish (US)
Title of host publicationData Privacy Management and Autonomous Spontaneous Security - 6th International Workshop, DPM 2011, and 4th International Workshop, SETOP 2011, Revised Selected Papers
PublisherSpringer Verlag
Pages58-71
Number of pages14
ISBN (Print)9783642288784
DOIs
StatePublished - Jan 1 2012
Externally publishedYes
Event6th International Workshop on Data Privacy Management, DPM 2011 and 4th SETOP International Workshop on Autonomous and Spontaneous Security, SETOP 2011 - Leuven, Belgium
Duration: Sep 15 2011Sep 16 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7122 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th International Workshop on Data Privacy Management, DPM 2011 and 4th SETOP International Workshop on Autonomous and Spontaneous Security, SETOP 2011
CountryBelgium
CityLeuven
Period9/15/119/16/11

Keywords

  • Computational complexity
  • User profiling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the complexity of aggregating information for authentication and profiling'. Together they form a unique fingerprint.

Cite this