Algorithms for Constructing Anonymizing Arrays

Erin Lanus; Charles J. Colbourn

doi:10.1007/978-3-030-48966-3_29

Algorithms for Constructing Anonymizing Arrays

Erin Lanus, Charles J. Colbourn

Engineering, Ira A. Fulton Schools of (IAFSE)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 than¹ 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 language	English (US)
Title of host publication	Combinatorial Algorithms - 31st International Workshop, IWOCA 2020, Proceedings
Editors	Leszek Gasieniec, Leszek Gasieniec, Ralf Klasing, Tomasz Radzik
Publisher	Springer
Pages	382-394
Number of pages	13
ISBN (Print)	9783030489656
DOIs	https://doi.org/10.1007/978-3-030-48966-3_29
State	Published - 2020
Event	31st International Workshop on Combinatorial Algorithms, IWOCA 2020 - Bordeaux, France Duration: Jun 8 2020 → Jun 10 2020

Publication series

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

Conference

Conference	31st International Workshop on Combinatorial Algorithms, IWOCA 2020
Country/Territory	France
City	Bordeaux
Period	6/8/20 → 6/10/20

Keywords

Anonymous authorization
Attribute-based methods
Combinatorial array
Construction algorithms

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-48966-3_29

Cite this

Lanus, E., & Colbourn, C. J. (2020). Algorithms for Constructing Anonymizing Arrays. In L. Gasieniec, L. Gasieniec, R. Klasing, & T. Radzik (Eds.), Combinatorial Algorithms - 31st International Workshop, IWOCA 2020, Proceedings (pp. 382-394). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12126 LNCS). Springer. https://doi.org/10.1007/978-3-030-48966-3_29

Algorithms for Constructing Anonymizing Arrays. / Lanus, Erin; Colbourn, Charles J.
Combinatorial Algorithms - 31st International Workshop, IWOCA 2020, Proceedings. ed. / Leszek Gasieniec; Leszek Gasieniec; Ralf Klasing; Tomasz Radzik. Springer, 2020. p. 382-394 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12126 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Lanus, E & Colbourn, CJ 2020, Algorithms for Constructing Anonymizing Arrays. in L Gasieniec, L Gasieniec, R Klasing & T Radzik (eds), Combinatorial Algorithms - 31st International Workshop, IWOCA 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12126 LNCS, Springer, pp. 382-394, 31st International Workshop on Combinatorial Algorithms, IWOCA 2020, Bordeaux, France, 6/8/20. https://doi.org/10.1007/978-3-030-48966-3_29

Lanus E, Colbourn CJ. Algorithms for Constructing Anonymizing Arrays. In Gasieniec L, Gasieniec L, Klasing R, Radzik T, editors, Combinatorial Algorithms - 31st International Workshop, IWOCA 2020, Proceedings. Springer. 2020. p. 382-394. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-48966-3_29

Lanus, Erin ; Colbourn, Charles J. / Algorithms for Constructing Anonymizing Arrays. Combinatorial Algorithms - 31st International Workshop, IWOCA 2020, Proceedings. editor / Leszek Gasieniec ; Leszek Gasieniec ; Ralf Klasing ; Tomasz Radzik. Springer, 2020. pp. 382-394 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{21c0f23a37f540a4af1c600092c3cbba,

title = "Algorithms for Constructing Anonymizing Arrays",

abstract = "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.",

keywords = "Anonymous authorization, Attribute-based methods, Combinatorial array, Construction algorithms",

author = "Erin Lanus and Colbourn, {Charles J.}",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020.; 31st International Workshop on Combinatorial Algorithms, IWOCA 2020 ; Conference date: 08-06-2020 Through 10-06-2020",

year = "2020",

doi = "10.1007/978-3-030-48966-3_29",

language = "English (US)",

isbn = "9783030489656",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "382--394",

editor = "Leszek Gasieniec and Leszek Gasieniec and Ralf Klasing and Tomasz Radzik",

booktitle = "Combinatorial Algorithms - 31st International Workshop, IWOCA 2020, Proceedings",

}

TY - GEN

T1 - Algorithms for Constructing Anonymizing Arrays

AU - Lanus, Erin

AU - Colbourn, Charles J.

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020.

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Anonymous authorization

KW - Attribute-based methods

KW - Combinatorial array

KW - Construction algorithms

UR - http://www.scopus.com/inward/record.url?scp=85086260158&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85086260158&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-48966-3_29

DO - 10.1007/978-3-030-48966-3_29

M3 - Conference contribution

AN - SCOPUS:85086260158

SN - 9783030489656

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 382

EP - 394

BT - Combinatorial Algorithms - 31st International Workshop, IWOCA 2020, Proceedings

A2 - Gasieniec, Leszek

A2 - Klasing, Ralf

A2 - Radzik, Tomasz

PB - Springer

T2 - 31st International Workshop on Combinatorial Algorithms, IWOCA 2020

Y2 - 8 June 2020 through 10 June 2020

ER -

Algorithms for Constructing Anonymizing Arrays

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this