Proceedings of International Conference
on Mechanical, Electrical and Medical Intelligent System 2017

Extensions of -diversity to reduce the risk of revealing patient
severe health conditions
Osamu Takaki1, a, Takayuki Asao2,b and Yoichi Seki3,c1

Faculty of Social and Information Science, Gunma University, 4-2 Aramaki-machi, Maebashi, 3718510, Japan

2

Big Data Center for Integrative Analysis, Gunma University, 3-39-22 Showa-machi, Maebashi, 3718511, Japan3

School of Science and Technology, Gunma University, 1-5-1 Tenjin-cho, Kiryu, 376-8515, Japanatakaki@gunma-u.ac.jp, basao@gunma-u.ac.jp, cseki@cs.gunma-u.ac.jp

Keywords: k-anonymity, l-diversity, anonymization, medical data, ontology

Abstract. In this paper, -diversity is extended to reduce the risk of an attacker inferring a patient’s
severe health conditions based on medical data. The extended versions of -diversity are defined inaccordance with a proposed ontology model by which the severity of a patient’s health information isquantified. It is herein shown that the extended -diversities satisfy the monotonicity property.
Additionally, an outline of a process is presented to anonymize medical data. Accordingly, the datasatisfy the extended -diversities and retain the data usability to the greatest extent possible.
1. Introduction
Medical data contain sensitive patient information. Therefore, in many hospitals, when data
administrators are requested to provide medical data to users from medical databases for secondary
applications, such as data-based research, the administrators should carefully determine the scope anddetail level of the provided medical data based on the given purpose and authority of the user.
Moreover, at that time, data administrators must decide the anonymization level of the medical data.
However, a trade-off exists between the anonymization level of medical data and their usability. It isthus desirable to anonymize the medical data to ensure that it satisfies hospital guidelines and maintains
usability of the data to the greatest extent possible.
-anonymity [1] and -diversity [2] have been proposed as useful properties in determining the data
anonymization level, whereand denote natural numbers. In what follows, let us consider data to
be tables in a relational database, and let
denote a table. A set of attributes inthat can be linked
with other tables to identify individuals is called a quasi-identifier in . On the other hand, an attributein , the value of which adversaries should be prevented from discovering for individuals in , iscalled a sensitive attribute. For example, Table 1 contains a quasi-identifier, which consists of “age,”“zip code,” and “occupation,” as well as a sensitive attribute, “disease.”is said to satisfy anonymity if every record in
is indistinguishable from at least
records with respect to every
quasi-identifier in . For example, Table 1, which has five records, satisfies 2-anonymity. (For_______
Table 1. Example table with a quasi-identifier consisting of “age”, “zip code” and“occupation” as well as with a sensitive attribute “disease”
ID (Dummy)
101
102
103
104
105

Age
50
50
25
25
25

Zip code
371-8510
371-8510376-8515376-8515376-8515

Occupation
Professor
Professor
Nurse
Nurse
Nurse

DiseaseParkinson's disease
Parkinson's disease
Bronchitis
Gastric ulcer
FluProceedings of International Conference
on Mechanical, Electrical and Medical Intelligent System 2017
simplicity, every sensitive attribute is considered not contained in a quasi-identifier.) -anonymity ofensures that adversaries are prevented from uniquely linking an individual to a record inwith aquasi-identifier.
However, for an adversary
and a target individual , even if
cannot uniquely linkto anyrecord,might link
to a value of a sensitive attribute in T. For example, in Table 1, even if
cannot distinguish the records with ID 101 or 102,
will realize thathas Parkinson’s disease if
can link
to the two above records. We call this problem a homogeneity attack [2].
To avoid a homogeneity attack, -diversity has been proposed. Tableis said to satisfy diversity if every set of records that shares the same values of attributes in a quasi-identifier has at leastdifferent values of every sensitive attribute. For example, Table 1 will satisfy 2-diversity if the value“Parkinson’s disease” of the sensitive attribute “disease” in the record with ID 101 is replaced by“myasthenia gravis.” However, in the case of medical data where the range of severities of theinformation described by a sensitive attribute is very broad, a homogeneity attack may not becompletely avoided by the use of only -diversity. For example, from Table 1, in which “Parkinson’s
disease” in the record with ID 101 is replaced by “myasthenia gravis,” attacker A may conclude that,
although A could not uniquely identify the disease of B from Table 1, A realizes that B requires atremendous expense to fully return to society.
The main purpose of this study was to extend -diversity to reduce the risk of attackers inferring apatient’s severe medical problems based on medical data in the example above. The extended diversities are defined based on our proposed ontology model—the Risk-Impact Ontology for Patients’Sensitive Information (RIOPSI)—which enables quantification of the severities of a patient’s healthinformation. In this paper, it is shown that the extended -diversities satisfy the monotonicity property.
In addition, an outline of a process is presented to anonymize medical data. Accordingly, the datasatisfy the extended -diversities and maintain the usability of the data to the greatest extent possible
by using the monotonicity property of the extended -diversities.
2. Modeling of Patient Medical Condition Severity
This section explains concepts in RIOPSI to define the severity of a patient’s health condition. An
approach to quantifying the severity of the information based on RIOPSI is also described.
2.1 Risk-Impact Ontology for Patients' Sensitive Information
RIOPSI is described byand mainly consists of (i) an attacker’s objectives and (ii) a patient’s
health conditions and severity criteria. Severity criteria are represented as sets of especially severe
patient conditions that are classified by types of patient medical conditions. The main concepts inare outlined below.
According to psychological studies on cyber attacks [3, 4] and insider threats [5, 6], attacker
motivations are classified into the following types: (1) Emotional motivation: (1.1) Pleasure, (1.2)
curiosity, (1.3) revenge, (1.4) revelation, and (1.5) destruction. (2) Commercial motivation: (2.1) Data
sales, (2.2) business operations, and (2.3) intimidation. Let us apply the motivations above to the caseof a homogeneity attack. Then, the adversary’s main objectives in accessing patient conditions areclassified into the following problems.
I. Problems that directly inflict major damage on patients only by being known by others.
II. Problems that patients are eager to solve, even if the cost is immense.
We divide these two problem types into several categories and consider the relevant attributes in thetables, which are stored in most hospital databases. Moreover, we consider the severity criteria of thecategorized conditions by defining sets of especially severe information as values of the related
attributes. The results are given in Table 2.

Proceedings of International Conference
on Mechanical, Electrical and Medical Intelligent System 2017
Table 2. Classification of Sensitive Information, Related Attributes, and Their Special
Values
Large Classof Sensitive
information
1.

Middle Class of Sensitive

Small Class of Sensitive

Related Attributes (Underlined Part) and Sets of

information

information

Special Values of the Attributes

1.1. information that inflicts

information significant damage not only 1.1.1. information aboutthat inflicts on patients but also on

diseases of genes

For the attribute "disease," we consider the set ofvalues that are assigned as diseases of genes by
the administration of health.

significant

their offsprings

damage on

1.2. information that inflicts 1.2.1. information about

For "disease," we consider the set of values that are

patients

significant disadvantages

diseases assigned as

assigned as intractable diseases by the

directly only on patients institutionallyintractable diseases

administration of health.

by being

1.3. information that inflicts 1.3.1. information about

For "disease," we consider the set of values thatknown bysignificant damage on

significant psychiatricspecialists such as doctors of psychiatric diseases

others.

patients' human rights

disordersselect as significant psychiatric disorders.

2.1.1. information about

For "disease," we consider the set of values whose

diseases that have a major

survival rate (for example, 5-year survival rates) are

2.1. Information about
patients' life spans

impact on patients' life spans low (for example, less than 30%).
For the pair of "disease" and its "medical treatment"
2.1.2. information about

including operations, we consider the set of pairs ofpatients' outcomesvalues whose survival rates after the medical
treatments are low.
For "disease," we consider the set of values that theinstitution of expensive medical treatments can be

2.2.1 and 2.2.2. information
about financial burdens ofpatients

applied to. (In the case of Japan, one can define 2stage sets according to the criteria defined by thehealth ministry.)
For "treatment" or "medicines," we consider the setof values that are assigned as expensive medical
treatments by the administration of health.

2.
Otherwise

2.2. Information about

than thepatients' quality of life

above

(QOL)

For "disease," we consider the set of values thatspecialists select as diseases by which patients
have difficulty to get back into society.
For "disease," we consider the set of values that
2.2.3, 2.2.4 and 2.2.5.

specialists select as diseases by which patients

information about degrees of have difficulty to have their daily life.
disability to patients' social

For attributes about durations of hospital stays, we

and/or personal life

consider the set of (tuples of) values that indicatethat the patients are hospitalized for long periods.
(For example, one can define 3-stage sets by morethan 60 days-, more than 120 days- and more than
180 days-hospitalization.)

2.3. information that inflict

2.3.1. information by which

For "disease," we consider the set of values that

others might have prejudicespecialists select as diseases by which others

damage on patients' human toward patients' life styles

might have prejudice toward patients' life styles.

rights (other than the

2.3.2. information by which

For "disease," we consider the set of values that

middle class 1.3)

others might have prejudicespecialists select as diseases by which others

toward patients' appearances might have prejudice toward patients' appearances.

Proceedings of International Conference
on Mechanical, Electrical and Medical Intelligent System 2017
Each set of special values that is defined in the right-most column of Table 2 is called a special
values set.
Remark 1. A survival rate, such as a five-year survival rate, is determined based on not only thedisease, but also the disease degree of progression. However, for simplicity, we regard a value of theattribute “disease” as a disease with its degree of progression.
Remark 2. In what follows, we regard every pair (and every tuple) of sensitive attributes in thesmall class (2.1.2) (and (2.2.5), respectively) as a single sensitive attribute. Moreover, for a pair ( , )of a disease, , and a medical treatment, , which is defined in the small class (2.1.2), ifiscontained in a special values set , then we regard ( , ) as contained in .
2.2 Quantification of Patient Condition Severity Based on
In this section, we quantify the severities of values and records in medical database tables fromadversaries’ viewpoints. In Definition 1, we define a “severity number” s( ) of a value, , by which
we describe the severity of , so that it satisfies the following principles.
i.
For values
and , ifis contained in a special values set in the first large class of sensitive
information, but
is not, then s( ) < s( ).
ii.
For values
andin the first large class, if⫋ , then s( ) < s( ), whereandare the set of special values sets in the first large class that contains
and , respectively.
iii.
For values
andthat are not in the first large class, but are in the second large class, if
andare contained in special values sets in different middle classes, then the severities ofandare not comparable.
iv.
However, if the severities ofandabove are compared from the specified viewpoint
represented by the middle class (2.1), (2.2), or (2.3) in Table 2, and if⫋ , then s( ) <s( ), whereandare the set of special values sets in the same middle class (2.1), (2.2),or (2.3) as well as
andcontainand , respectively.
We believe that the above principles (i) and (ii) are reasonable. Note that the severity of a patient’s
information from an adversary’s viewpoint differs from the patient’s severity itself. We also consider
the principles (iii) and (iv), because it is not easy to compare the severities of patients’ informations if
they are considered from different viewpoints that are represented by the middle classes (2.1), (2.2),and (2.3) in Table 2. Therefore, we define the severity number ofaccording to not only the large
class type of, but also the middle class type.
Definition 1. (1) Let
be the number of the middle classes with item number (2. ) in Table 2,( ) of value
which we call the middle class type. Then, we define severity number
with respecttoas follows.
( ) is defined
1. If
is contained in a special values set in the first large class, thenindependently of
to be + . Here,denotes the number of special values sets in the firstlarge class that contain , anddenotes the maximum number in the set of all severity numbers
satisfying condition (2) below.
( ) = . Here,
2. If
is contained in no special values set in the first large class, thendenotes the number of special values sets in the middle class with typethat contain .
(λ)(2) For record λ in a table and middle class type , severity numberof λ with respect to( ) of all values
is the maximum number of
in λ.
3.

-Based -Diversity

In this section, we extend -diversity based on
and the severity numbers defined in Section 2.
Let
be a table, λ a record in , π a quasi-identifier in , anda tuple of values of π in λ.
Then, the set of records inthat shareas the tuple of the values of π is called the π-block of .

Proceedings of International Conference
on Mechanical, Electrical and Medical Intelligent System 2017
Definition 2. Let be a natural number andbe a middle class type. Then, a π-block Λ is said tosatisfy ( )-l-diversity if, for every sensitive attribute σ, there exists at least l values , … ,of( ), … , ( ) that differ from each other. Moreover, Λ is said
σ in Λ with severity numbers
to satisfy-l-diversity if Λ satisfies ( ) -l-diversity for all typesof middle classes.
Furthermore,is said to satisfy ( )-l-diversity (or -l-diversity) if all blocks insatisfy( )-l-diversity (or -l-diversity, respectively).
For table , ifsatisfies ( )-l-diversity for some type , then it clearly satisfies l-diversity.
Moreover, one can easily extend other l-diversity types defined in [2] by replacing the differences ofvalues by those of the severity numbers of the values.
Severity numbers of most values would be very low. Thus, the conditions of ( )-l-diversity and-l-diversity in Definition 2 may be too strict. If it is not necessary to focus on records with a low
severity number, Definition 3 would be more useful.
Definition 3. Let be a natural number anda middle class type. Then, π-block Λ is said to(λ) ≤ − ,satisfy downward- ( )-l-diversity if there exists a record, λ, in Λ that satisfies
whereis the maximum number of all severity numbers. Moreover, Λ is said to satisfy downward-l-diversity if Λ satisfies downward- ( ) -l-diversity for all typesof middle classes.
Furthermore,is said to satisfy downward- ( )-l-diversity (or downward- -l-diversity) if all
block Λ insatisfy downward- ( )-l-diversity (or downward- -l-diversity, respectively).
Note thatin Definition 3 is independently determined of table
and that the downward versionof ( )-l-diversity has no logical strength relationship with l-diversity. Actually, if
has no value
with a severity number > − , thenautomatically satisfies downward- -l-diversity.
4. Generalization of Medical Data Based on-Based -Diversity

In this section, we outline a process to anonymize medical data based on extended -diversities
defined in Definitions 2 and 3, which we call -based -diversities. To this end, we first show
monotonicity of -based -diversities. For simplicity, in what follows, for a table, , we consider
that all quasi-identifiers inare integrated and thathas only one quasi-identifier.
Letbe a table that consists of the (integrated) quasi-identifier π and a sensitive attribute σ. In
addition, λ denotes a record in , andrepresents a tuple of values of π in λ. Moreover, let
be the domain of π, and let ∗ be a set { , … , } of subsets ofthat satisfies Q =
∪ ⋯∪
∗
and
∩
= ∅ for each , ≤ with ≠ . Furthermore,denotes a table that consists of
the quasi-identifier π∗ and the sensitive attribute σ, where π∗ has ∗ as its domain. Then, ∗ iscalled a generalization ofifand ∗ share the same number of their records and if, for every
∗
∗
≤ ,
∈
and
= , whereand ∗ denote the values of π and π∗ in the -th recordsofand ∗ , respectively, andand ∗ denote the values of σ and σ∗ in the -th records ofand ∗ , respectively.
For tablesand ∗ above, let be a number with ≤ , Λ be the π-block inof , and∗∗∗∗Λ be the π -block inof . Then, for every ≤ , if the -th recordofis contained in∗∗∗Λ, then the -th record λ ofis contained in Λ and the valueof σ inis the same as the
∗
∗
∗
value
of σ in λ . Thus, by the conditions of Definitions 2 and 3, one can easily demonstrate
Proposition 1.
Proposition 1. All -based -diversities satisfy the monotonicity property. For example, if tablesatisfies ( ) -l-diversity for a type, then every generalization ∗ also satisfies ( ) -ldiversity. The same holds for other type -based -diversities.
The monotonicity property of -based -diversities implies that one can easily apply to -based-diversities the algorithm “Incognito” [7], which has been employed for data generalization to satisfy-anonymity and -diversity (see also [2]). As an application, we outline a process to generalizeProceedings of International Conference
on Mechanical, Electrical and Medical Intelligent System 2017
medical data (tables) to satisfy an -based -diversity maintaining the data usability to the greatest
possible extent by using Incognito as follows.
i.
In advance of generalization of medical data, experts of medical informatics, administrators of
medical databases, and hospital research ethics committees collaborate in formulating a
guideline for appropriate use of medical data for research purposes in the hospital.
ii.
Administrators of medical databases and users (researchers) of medical data collaborate indeciding the scope of datathat the users desire as well as the conditions and priority for
generalization of the (integrated) quasi-identifierinbased on the guideline above. Then,for domainof, a sequence ℚ = { , ∗ , ∗∗ , … , ∗…∗ } of iteration results ofgeneralizations ofis specified, which we call a strategy of generalization of .
iii.
Based on the guideline in (i) and the discussion in (ii), one of the -based -diversities ⅅ,
including parameters, is determined and Incognito is adjusted based on ⅅ.
iv.
By applying strategy ℚ to ⅅ-adjusted Incognito, the user can obtain generalized data ∗ thatsatisfy ⅅ by the minimum iterations of generalizations according to strategy ℚ.
5. Conclusion
In this paper, we proposed several extensions of -diversity to reduce the risk of attacker inferenceof severe patient medical conditions based on medical data. To this end, we defined the RIOPSI
ontology model and quantified the severities of a patient’s health information based on RIOPSI.
Moreover, we showed that our extended versions of -diversity satisfy the monotonicity property. We
hence outlined a process to generalize medical data (tables) to satisfy the extended -diversities
maintaining of data usability to the greatest extent possible by using the adjusted Incognito algorithm.
With respect to improvements, in Table 2, it would be more effective to define more refined subsetsof the several special values sets. For example, it would be better to define subsets of the special values
set defined in the small class (2.1.1) by using a one-year survival rate and/or a three-year survival rate.
An approach to creating more refined subsets remains for future work.
References[1] L. Sweeney, "k-anonymity: a model for protecting privacy", Int. J. Uncertain. Fuzziness Knowl.Based Syst. Vol. 10, No. 5, 2002, pp. 557-570.
[2] A. Machanavajjhala, D. Kifer, J. Gehrke, and M. Venkitasubramaniam, "L-diversity: Privacy
beyond k-anonymity", TKDD Vol. 1, No. 1(3), 2007, pp. 1-52.
[3] C. A. Meyers, C A, S. S. Powers, D. M. Faissol, "Taxonomies of cyber adversaries and attacks: asurvey of incidents and approaches", Technical Report in Lawrence Livermore National
Laboratory (LLNL), Livermore, CA: LLNL-TR-419041, DOI: 10.2172/967712, 2009.
[4] S. Atkinson, "Psychology and the hacker: Psychological incident handling", White Paper, SANS
Institute, 2015.
[5] D. Cappelli, A. G. Desai, A. P. Moore, T. J. Shimeall, E. A. Weaver, B. J. Willke, "Management
and education of the risk of insider threat (MERIT): system dynamics modeling of a computer
system", White Paper, Carnegie Mellon University, 2008.
[6] "Report on measure against human threats to information security", White Paper, The Nikkoso
Research Foundation for Safe Society, 2010 (in Japanese).
[7] K. LeFevre, D. J. DeWitt, and R. Ramakrishnan. "Incognito: efficient full-domain K-anonymity",
In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data
(SIGMOD '05). ACM, New York, NY, USA, 2005, pp. 49-60.