Algorithms for Constructing Anonymizing Arrays

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


Attribute-based methods are inherently identity-less as authorization decisions are made in terms of attributes possessed by the subject rather than identity. However, anonymity against the system is not guaranteed when attribute distribution allows for the composition of a policy that few subjects can satisfy. An anonymizing array ensures that any assignment of values to t attributes that appears in the array appears at least r times. When an anonymizing array is used for subjects registered to a system and policies contain conjunctions of at most t attributes, the system cannot identify the subject using the policy to to gain authorization with greater than1 probability. Anonymizing arrays r are similar to covering arrays with higher coverage and constraints, but have an additional desired property, homogeneity, due to their application domain. In this paper, we develop constructions for anonymizing arrays and propose a post-optimization mechanism to reduce homogeneity.

Original languageEnglish (US)
Title of host publicationCombinatorial Algorithms - 31st International Workshop, IWOCA 2020, Proceedings
EditorsLeszek Gasieniec, Leszek Gasieniec, Ralf Klasing, Tomasz Radzik
Number of pages13
ISBN (Print)9783030489656
StatePublished - 2020
Event31st International Workshop on Combinatorial Algorithms, IWOCA 2020 - Bordeaux, France
Duration: Jun 8 2020Jun 10 2020

Publication series

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


Conference31st International Workshop on Combinatorial Algorithms, IWOCA 2020


  • Anonymous authorization
  • Attribute-based methods
  • Combinatorial array
  • Construction algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Algorithms for Constructing Anonymizing Arrays'. Together they form a unique fingerprint.

Cite this