Con en s lis s a ailable a ScienceDi ec
Compu e s & Secu i y
jou nal homepage: www.else ie .com/loca e/cose
Full leng h a icle
P i acy p o ec ion agains use p o iling h ough op imal da a gene aliza ion
Césa Gil, Ja ie Pa a-A nau∗, Jo di Fo né
Depa men o Telema ics Enginee ing, Uni e si a Poli ècnica de Ca alunya, Ba celona, Spain
ARTICLE INFO
Keywo ds:
Da a p i acy
Use p o iling
Pe sonalized in o ma ion sys ems
Da a gene aliza ion
Da a-pe u ba i e mechanisms
ABSTRACT
Pe sonalized in o ma ion sys ems a e in o ma ion- il e ing sys ems ha endea o o ailo in o ma ion-
exchange unc ionali y o he speci ic in e es s o hei use s. The abili y o hese sys ems o p o ile use s based
on hei sea ch que ies a Google, disclosed loca ions a Twi e o a ed mo ies a Ne lix, is on he one hand
wha enables such in elligen unc ionali y, bu on he o he , he sou ce o se ious p i acy conce ns. Le e aging
on he p inciple o da a minimiza ion, we p opose a da a-gene aliza ion mechanism ha aims o p o ec use s’
p i acy agains non- ully us ed pe sonalized in o ma ion sys ems. In ou app oach, a use may like o disclose
pe sonal da a o such sys ems when hey eel com o able. Bu when hey do no , hey may wish o eplace
speci ic and sensi i e da a wi h mo e gene al and hus less sensi i e da a, be o e sha ing his in o ma ion wi h
he pe sonalized sys em in ques ion. Gene aliza ion he e o e may p o ec use p i acy o a ce ain ex en , bu
clea ly a he cos o some in o ma ion loss. In his wo k, we model ma hema ically an op imized e sion o
his mechanism and in es iga e heo e ically some key p ope ies o he p i acy-u ili y ade-o posed by his
mechanism. Expe imen al esul s on wo eal-wo ld da ase s demons a e how ou app oach may con ibu e
o p i acy p o ec ion and show i can ou pe o m s a e-o - he-a pe u ba ion echniques like da a o ge y
and supp ession by p o iding highe u ili y o a same p i acy le el. On a p ac ical le el, he implica ions o
ou wo k a e di e se in he ield o pe sonalized online se ices. We emphasize ha ou mechanism allows
each use indi idually o ake cha ge o hei own p i acy, wi hou he need o go o hi d pa ies o sha e
esou ces wi h o he use s. And on he o he hand, i p o ides p i acy designe s/enginee s wi h a new da a-
pe u ba i e mechanism wi h which o e alua e hei sys ems in he p esence o da a ha is likely o be
gene alizable acco ding o a ce ain hie a chy, highligh ing spa ial gene aliza ion, wi h p ac ical applica ion
in popula loca ion based se ices. O e all, a da a-pe u ba ion mechanism o p i acy p o ec ion agains use
p o iling, which is op imal, de e minis ic, and local, based on a un us ed model owa ds hi d pa ies.
1. In oduc ion
An es ima ed 4.1 billion people used he In e ne in 2019 and,
oday, almos he en i e wo ld popula ion s ays connec ed o a mobile
phone ne wo k (Union,2020). The digi al uni e se is also es ima ed o
each a capaci y o 44 ze aby es (1 ZB = 1021 by es) his yea . Phe-
nomena such as in o ma ion o e load,da a ica ion o o e lapped eal and
digi al li es accompany he ascina ing and a he same ime dizzying
de elopmen o he In e ne . New high impac echnologies as he Big
Da a, IoT, 5G o Blockchain sha e scene wi h p essing global p oblems
as he clima e change, employmen o ecen pandemic.
A he same ime, Schwab (2015) highligh ed in 2015 he u u e o
he In e ne as one o he en mos ele an issues acing he wo ld. And
om he social poin o iew, one o he mos ele an challenges o his
new indus y a e p i acy conce ns. In his sense, Schwab p edic ed ha
deba es abou undamen al issues such as he impac on ou inne li es o
he loss o con ol o e ou da a will only in ensi y in he yea s ahead.
∗Co esponding au ho .
E-mail add esses: [email p o ec ed] (C. Gil), [email p o ec ed] (J. Pa a-A nau), [email p o ec ed] (J. Fo né).
1We shall in e changeably use he e ms u ili y and pe sonaliza ion.
In his con ex , pe sonalized in o ma ion sys ems (PISs) a e a clea
example o he ise o he In e ne and i s isks o use p i acy.
Amazon, YouTube o Ne lix a e exponen s o hese sys ems, which
ha e adically changed he way o accessing in o ma ion wi h a high
impac on ou economy. PISs ypically collec pe sonal, beha io al da a
o hei use s o e ime o p o ile hem and hus in e hei in e es s o
p e e ences and classi y hem. I is in his p o iling p ocess (de ined
by U.S. NIST Boeckl e al.,2019 as an ope a ion o se o ope a ions
pe o med upon pe sonally iden i iable in o ma ion (PII) ha can include,
bu is no limi ed o, he collec ion, e en ion, logging, gene a ion, ans o -
ma ion, use, disclosu e, ans e , and disposal o PII) whe e use p i acy
is comp omised. Howe e , because p o iling is in ac wha enables
pe sonaliza ion, use s o hose sys ems a e aced wi h a dilemma o
g ea p ac ical ele ance: how o balance he ade-o be ween and
p i acy and pe sonaliza ion.1
h ps://doi.o g/10.1016/j.cose.2024.104178
Recei ed 17 Oc obe 2022; Recei ed in e ised o m 22 May 2024; Accep ed 22 Oc obe 2024
Compu e s & Secu i y 148 (2025) 104178
A ailable online 5 No embe 2024
0167-4048/© 2024 The Au ho s. Published by Else ie L d. This is an open access a icle unde he CC BY license (
h p://c ea i ecommons.o g/licenses/by/4.0/ ).
C. Gil e al.
In he con ex o PISs, balancing his ade-o has been sca cely
s udied o local p o ile p o ec ion (Kaaniche e al.,2020), ha is, when
he p o ec ion mechanism is pu in place on he use side and he aim
is coun e ing he p o iling ca ied ou by hose sys ems. This ype o
local p o ec ion is con en ionally e e ed o as ha d p i acy, which,
unlike so p i acy (Danezis,2007;Deng e al.,2011), assumes use s
need no us he se ice p o ide no e en he ne wo k ope a o , and
hence, because hey jus us hemsel es, i is hei own esponsibili y
o p o ec hei p i acy. Undoub edly, ha d p i acy is aligned wi h
he p inciple o da a minimiza ion, by which one would minimize he
amoun o da a hey would sha e wi h an in o ma ion sys em wi hou
signi ican ly deg ading he expec ed unc ionali y.
Howe e , he li e a u e o local mechanisms o p o ile p o ec ion
can be classi ied essen ially in o wo da a-pe u ba ion app oaches:
o ge y, i.e., submi ing alse da a; supp ession, i.e., e aining om
disclosing eal, ue da a; and a combina ion o he wo. In his wo k,
we p opose a no el ca ego y o da a pe u ba ion o p o ile-p i acy
enhancemen , da a gene aliza ion, which consis s in eplacing speci ic
and sensi i e da a (e.g., a sea ch que y on AIDS ea men o a loca ion
a a hospi al) wi h mo e gene al and hus less sensi i e da a, be o e
sending hem o he se ice p o ide in ques ion.
We has en o s ess, howe e , ha he idea o da a gene aliza ion is
by no means new. As a ma e o ac , gene aliza ion is an old acquain-
ance o he ield o s a is ical disclosu e con ol (SDC) (Hundepool
e al.,2003). In SDC, gene aliza ion as well as o ge y and supp ession
a e applied o eco ds o a da abase wi h he same a o emen ioned p in-
ciple. None heless, unlike SDC, ou wo k in es iga es he applica ion o
gene aliza ion o p o ec adi e en da a s uc u e, namely, a use p o-
ile, which, like Xu e al. (2007a), Toubiana e al. (2010a,b), F ed ikson
and Li shi s (2011), Rebollo-Monede o and Fo né (2010), Pa a-A nau
e al. (2010,2011,2012b,a,2014c,b), Rod iguez-Ca ion e al. (2015),
Es ada-Jimenez e al. (2019), Pa a-A nau (2017,2018) and Pa a-
A nau e al. (2014a), we assume i is modeled ma hema ically as a
p obabili y mass unc ion (PMF).
1.1. Con ibu ion and plan o his pape
In his pape , we in es iga e da a gene aliza ion as a ha d-p i acy
mechanism ha aims o p o ec PMF-based p o iles agains non- ully
us ed PISs. Ou mechanism assumes use s a e willing o gene alize
ce ain pieces o pe sonal in o ma ion while in e ac ing wi h a PISs, in
o de o a oid being accu a ely p o iled by his o , in gene al, by any
p i acy a acke capable o collec ing such in o ma ion. Following his
simple p inciple, ou app oach may p o ec use p i acy o a ce ain
deg ee, wi hou ha ing o us he sys em p o ide no he ne wo k
ope a o , bu a he cos a loss in u ili y, a deg ada ion o he quali y
o he pe sonalized se ice.
Ou i s con ibu ion is an a chi ec u e ha implemen s his idea
o a speci ic PISs, esou ce agging, al hough i can be s aigh o -
wa dly applied o any pe sonalized se ice p o ide . The heo e ical
analysis o he ade-o be ween p i acy and u ili y is ou second
con ibu ion. We ackle his analysis in a sys ema ic ashion, d aw-
ing upon he me hodology o mul iobjec i e op imiza ion. We adop
a quan i iable measu e o use p i acy — he Shannon’s en opy o
he p obabili y dis ibu ion o he use ’s da a —, and o mula e an
op imiza ion p oblem modeling he ade-o be ween p i acy on he
one hand, and on he o he gene aliza ion a e as u ili y me ic. Ou
heo e ical analysis inds a closed- o m exp ession o he c i ical gene -
aliza ion a e, i.e., he a e beyond which maximum p i acy is a ained.
Ou app oach is hen expe imen ally e alua ed in a eal-wo ld applica-
ion. Namely, we apply op imal da a gene aliza ion o Fou squa e and
B ig hki e, wo popula da ase s om loca ion-based social ne wo ks
(LBSNs), and show, in a se ies o expe imen s, how ou app oach
enables i s use s o enhance hei p i acy.
Sec ion 2explo es some ele an app oaches ela ed o p i acy
and da a-pe u ba i e mechanisms in PISs. Sec ion 3desc ibes ou
p i acy-enhancing mechanism, some conside a ions abou he use p o-
ile model and he ad e sa y capabili ies, and ul ima ely a o mula ion
o he ade-o be ween p i acy and gene aliza ion. Sec ion 4p esen s
in de ail a possible p ac ical implemen a ion o ou gene aliza ion
mechanism, including some assump ions o ou app oach on a use
p o ile. Sec ion 5p esen s a heo e ical analysis o he op imiza ion
p oblem cha ac e izing he p i acy-gene aliza ion ade-o . In addi-
ion, his sec ion shows a simples bu insigh ul example ha illus a es
he o mula ion and heo e ical analysis a gued in he p e ious sec-
ions. Sec ion 6p esen s an expe imen al e alua ion o ou echnique
in Fou squa e and B ighki e da ase s, including a discussion abou i .
Conclusions and u u e wo k a e d awn in Sec ion 7.
1.2. P ac ical implica ions and scope
Resea ch in p i acy p o ec ion agains use p o iling encompasses
a wide ange o me hods and applica ion scena ios. No able exam-
ples include dynamic op imiza ion in online mobile ad e ising o
p e en acking ia empo a y applica ion usage (Ullah and Bin-
busayyis,2022), ad e sa ial app oaches o coun e p o ile acking
h ough mouse cu so mo emen s (Lei a e al.,2021), and me hods
o sa egua d da a secu i y h ough biome ic senso s in use au hen i-
ca ion (He nández-Ál a ez e al.,2020). Addi ionally, s udies in ol e
analyzing online beha io al models (Mamun e al.,2021) and explo ing
ad anced de ense mechanisms in social ne wo ks and he In e ne
o Things (IoT). These mechanisms add ess con empo a y challenges
such as p o ec ing use loca ions, especially o mino s, and comba ing
cybe bullying (Shakil e al.,2021).
Fo he gene aliza ion o da a in he con ex o PISs, we p opose wo
applica ions ha could be o g ea impac , gi en he la ge numbe o
po en ial use s ha hey would in ol e. Fi s ly, we conside he u ban
mobili y scena io, whe e use s demand se ices in exchange o sha ing
hei loca ion and/o hei assessmen s o he unc ioning o public
se ices, o example. We include in his scena io applica ions om a
heal h poin o iew wi h an eye on he ecen COVID-19 epidemic,
as a as mobili y and p i acy a e conce ned. And secondly, we also
con empla e he con ex o a ia ion, whe e a ele s can be p o iled,
o example, based on hei na iga ion pa h o e any o he wo ld’s
ai po s, o any o he in o ma ion o in e es and use ulness o o e a
pe sonalized online se ice. We wan o highligh ha ou expe imen s
include gene aliza ion o spa ial da a, ha is, on loca ion coo dina es
(la i ude and longi ude), undamen al da a on which he p oli ic ield
o loca ion p i acy and he popula loca ion-based se ices a e based.
Finally, we would like o no e ha no less no able is he e sa ili y
o he scope o p i acy-enhancing echnologies (PETs) based on da a
pe u ba ion, as is he case o he mechanism he e p oposed. We belie e
ha ou con ibu ions can signi ican ly aid in p o ec ing p i acy agains
use p o iling om wo pe spec i es. Fi s ly, hey a e designed o
p i acy designe s/enginee s, aiming o equip hem wi h a new ool
o e alua ing hei sys ems’ balance be ween use p i acy and da a
u ili y o pe sonaliza ion. Secondly, hese con ibu ions empowe use s
hemsel es. They enable use s o p o ec hei p i acy independen ly,
wi hou elying on hi d pa ies o sha ing esou ces wi h o he s.
Addi ionally, hey assis use s in de e mining he op imal amoun o
da a pe u ba ion needed o minimize he impac on he quali y o pe -
sonalized se ices hey ecei e. In gene al, we wan o emphasize he
local and de e minis ic na u e o ou p oposal ega ding he applica ion
scena io, assuming a un us ed model owa ds hi d pa ies, as well as
he op imized solu ion we p o ide.
2. S a e o he a
In he b oad con ex o PISs, he e a e coun less p i acy-enhancing
echnologies (PETs) ha allow he ex ac ion and sha ing o in o ma-
ion while gua an eeing use p i acy. Acco ding o Pa a-A nau e al.
(2015), we can classi y hese echnologies in o i e g oups, namely,
Compu e s & Secu i y 148 (2025) 104178
2
C. Gil e al.
(a) basic an i- acking echnologies, (b) TTP-based app oaches, (c) col-
labo a i e mechanisms, (d) c yp og aphy-based me hods om p i a e
in o ma ion e ie al (PIR) and (e) da a-pe u ba ion echniques. The
mechanisms ha we in es iga e belong o his las class.
Focusing on his las g oup, da a-pe u ba ion echniques ope a e by
ob usca ing he in o ma ion use s explici ly o implici ly e eal when
communica ing wi h a PIS. They a e a commonly used app oach o
p e en p i acy a acke s om a emp ing o accu a ely p o ile use s.
An illus a i e example o his echnique is sending alse da a, along
wi h he use ’s genuine da a. I is impo an o no e ha PETs a e
cha ac e ized by he le el o us ha use s place in he en i ies
wi h which hey communica e, and ha , speci ically, da a-pe u ba ion
echniques usually adop he un us ed model, assuming ha any hi d
pa y is a po en ial p i acy a acke . O wha is he same, he da a
pe u ba ion occu s on he use side, al hough his is no an obs acle
o hem o be combined wi h o he mo e collabo a i e mechanisms.
I we ake in o accoun ha pe sonaliza ion is he main objec i e
o PISs and use p o iling ep esen s i s main p i acy isk, da a pe u -
ba ion poses a signi ican challenge: balancing he cos o unc ionali y
in he sys em and he u ili y o he da a on he one hand, and on he
o he he p i acy o use s.
In his sec ion, we examine hose wo ks ha aim o p o ec use
p o iles in PISs, and p oceed depending on he ype o pe u ba ion
echnique applied: de e minis ic o ge y, supp ession, a combina ion o
bo h, and andom pe u ba ion. We would like o emphasize, hough,
ha all such echniques ( oge he wi h he one p oposed in his wo k
based on gene aliza ion) can also be ound in he ield o SDC. Howe e ,
he objec o p o ec ion o he wo ks analyzed in his sec ion is a use
p o ile, ypically modeled as a PMF, whe eas in SDC, hose echniques
aim o p o ec a whole da abase o eco ds.
2.1. Fo ge y
The idea behind que y o ge y is simply based on adding ake
que ies (o keywo ds) o he o iginal ones. This app oach allows use s
o ob usca e hei p o ile, p o ec ing hem om p ecise p o iling by
p i acy a acke s, and a oiding he need o us po en ially ha m ul
hi d pa ies.
The e a e di e en al e na i es based on he alsi ica ion o que ies
such as he sys em o p i a e Web b owsing called PRAW (Elo ici
e al.,2002a,b,2005,2006). This sys em p o ec s he p i acy o a g oup
o use s who access he Web h ough sha ed access. Assuming ha
use s ha e logged in o a websi e and a e he e o e iden i ied, while he
a acke s’ e o s ocus on p o iling he g oup, PRAW hides he use s’
eal p o iles by gene a ing alse na iga ion aces in o de o p ese e
hei p i acy.
Inspi ed by he same me hodology o alse que y injec ion, in Ye
e al. (2009), he au ho s p opose a gene a o o eal and alse que ies
based on complemen a y p obabili ies ha a e only a ailable on he
use side, and he e o e assumed o be unknown o he ad e sa y.
A popula web b owsing plugin ha implemen s que y o ge y using
di e en s a egies is T ackMeNo (Howe and Nissenbaum,2009). An
in eg a ed keywo d dic iona y, which is ed wi h dispa a e sou ces o
in o ma ion, is he sou ce used o gene a e he alse que ies ha a e
o wa ded o he se e . Communica ion can be simula ed in bu s s,
as i i we e human web sea ches, o in ime in e als. Howe e , he
ulne abili y o T ackMeNo o ce ain a acks based on seman ics o
he ime be ween alse que ies o dis inguish hem om he eal one is
a gued in Chow and Golle (2009).
Ano he p oposal o p o ile ob usca ion in so wa e o m is GooPi
(Domingo-Fe e e al.,2009). I s ope a ion is based on mixing genuine
que y keywo ds wi h alse keys ha p o e simila use ( equency). The
esul is sen in ba ches o keywo ds o he web sea ch engine, so ha
a ack a emp s on he use ’s que y p o iles a e hinde ed a he p ecise
momen . Howe e , Balsa e al. (2012) p esen s a c i icism o GooPi in
he sense ha i s s a egy does no p e en an a acke om being able
o calcula e co ela ions be ween keywo ds om di e en ba ches and
inally in e he use ’s eal in e es .
Las ly, in any case i is essen ial o ake in o accoun he implici
handicap o adding alse que ies, which is clea ly he a ic o e load.
This ci cums ance implies conside ing a ade-o be ween p i acy and
added a ic. P ecisely, in Rebollo-Monede o and Fo né (2010) he
au ho s in es iga e heo e ically his balance in he ield o in o ma ion
e ie al wi h a ma hema ical model wi h he aim o op imizing he
pe cen age o alsi ied que ies and he p i acy o use s.
2.2. Supp ession
Supp ession is he opposi e al e na i e o in oducing ( alse) ac i i y
in o a use p o ile and is a pe ec ly iable pe u ba i e echnique.
This is demons a ed by he au ho s in Pa a-A nau e al. (2010) on
he scene o he seman ic Web. The emo al o labels, a p ocess wi h
associa ed cos s in e ms o esou ces, allows he use o imp o e hei
p i acy al hough in a limi ed way, in comp omise wi h he seman ic
deg ada ion o he da a. The Shannon en opy o he pe u bed p o ile
and he pe cen age o labels ha he use is willing o dele e a e,
espec i ely, he p i acy and u ili y me ics on which he au ho s s udy
hei op imal balance h ough con ex op imiza ion in Pa a-A nau
e al. (2012b). Along his line, Pa a-A nau e al. (2012a) p esen s an
in e es ing applica ion o label supp ession in he con ex o esou ce
ecommenda ion and pa en al con ol. In his case, he impac o he
pe u ba ion is e alua ed bo h in e ms o cos s associa ed wi h da a
deg ada ion and in he p ecision o he assignmen o one o ano he
p ede ined pa en al con ol policies.
2.3. Combined o ge y and supp ession
Combining o ge y and supp ession is a s a egy used in he scena io
o pe sonalized ecommende sys ems, such as Mo ielens.2In p ac ical
e ms, coupling bo h echniques allows use s o send alse a ings
and/o no a e elemen s ha a e o in e es o hem. In his sub ield
o PISs, he ade-o be ween p i acy p o ec ion and u ili y o use
p o iles has been he subjec o esea ch in Pa a-A nau e al. (2011).
Mo e speci ically, in Pa a-A nau e al. (2014c), he au ho s con ibu e
a closed solu ion o he p oblem o op imal and simul aneous o ge y
and supp ession o a ings, which hey e alua e on he eal-wo ld
Mo ielens da ase .
2.4. Local di e en ial p i acy o use -p o ile p o ec ion
Di e en ial p i acy (DP) (Dwo k,2006) was o iginally p oposed
as a p i acy model in an in e ac i e se ing o p o ec he ou comes
o que ies o a da abase. In his se ing, he assump ion is ha an
anonymiza ion mechanism si s be ween a use submi ing que ies and
acen al, us ed da abase cu a o answe ing hem. A a high le el, DP
p omises ha he pa icipa ion o any single indi idual in a da ase
will no no iceably al e he esul s o an analysis o he da ase . The
DP gua an ee holds e en i an ad e sa y is equipped wi h a bi a y
auxilia y in o ma ion abou he pa icipan s in a da ase .
Soon a e i s incep ion, he local mode o DP (Kasi iswana han
e al.,2011) was p oposed wi h he a ac i e ea u e ha da a subjec s
need no us he da abase cu a o . In his se ing, da a subjec s ha e
hei local iew o he da ase ( ypically, hey only know hei own
da a poin ) and each one independen ly ob usca es hei da a locally
h ough an ins ance o a DP algo i hm. Local DP (LDP), as i is known,
p o ides s onge p i acy gua an ees compa ed o he cen al model
bu a a highe cos in e ms o da a u ili y.
The pa icula i ies o LDP lead us o conside i sui able o ou sce-
na io o PISs, speci ically in he con ex o da a-pe u ba ion echniques
2h ps://mo ielens.o g/.
Compu e s & Secu i y 148 (2025) 104178
3
C. Gil e al.
agains use p o iling. This is especially ele an as LDP complemen s
he de e minis ic na u e o ou p oposal and all app oaches discussed
in his sec ion.
While nume ous p oposals and applica ions o LDP ha e been ex-
ensi ely epo ed in Xiong e al. (2020), Wang e al. (2020) and Yang
e al. (2023), e en in he ealm o PETs in PISs, which include majo
p ac ical implemen a ions by Google, Apple, and Mic oso (Kaaniche
e al.,2020), and no able wo ks ha p o ec use ajec o ies (Mi anda-
Pascual e al.,2023) o loca ions (Wang e al.,2022) in he con ex o
loca ion-based se ices (LBS), he e is a no able gap in he p o ec ion
o use p o iles based on p obabili y mass unc ions (PMFs). I is wo h
no ing ha adding noise in di e en ial p i acy (and consequen ly in
LDP) o e he simplex uni can be a non- i ial ask (Goha i e al.,
2021).
3. P i acy p o ec ion ia da a gene aliza ion
Based on he ha d p i acy assump ions (Deng e al.,2011), he op-
imal gene aliza ion is a p i acy mechanism ha is in ended o p e en
p i acy a acke s om p o iling use s on he basis o he da a hey sha e
wi h he sys em. Concep ually, ou app oach p o ec s use p i acy
o a ce ain ex en , gene alizing hose da a ha make a use p o ile
show a bias owa ds ce ain ca ego ies o in e es . F om a p ac ical
pe spec i e, ou p o iling gene aliza ion echnique is concei ed o be
deployed as a so wa e applica ion ha uns on use s’ local machines.
The so wa e implemen a ion is hen esponsible, on he one hand, o
wa ning he use when hei p i acy is being comp omised and, on he
o he , o helping hem decide which da a should and should no be
gene alized. Consequen ly, ou app oach ensu es use p i acy o some
ex en wi hou ha ing o ely on an ex e nal en i y, bu a he cos o
some local p ocessing expenses and, mo e impo an ly, he in o ma ion
loss incu ed by he gene aliza ion o da a.
In his sec ion, we i s p opose a use -p o ile model, examine
wha he specialized li e a u e unde s ands by p o iling, and hen nex
desc ibe ou assump ions abou he ad e sa y capabili ies. A e wa ds,
we jus i y a quan i a i e measu e o he p i acy o his p o ile. These
conside a ions lead us o o mula e he p oblem o choosing an op imal
gene aliza ion s a egy as a mul i-objec i e op imiza ion p oblem ha
akes in o accoun bo h p i acy and gene aliza ion a e.
3.1. Use p o ile model
In ou scena io o PISs, we assume he e is a compu e ized sys em
ha builds p o iles om he ac i i y da a he sys em collec s o e a ime
pe iod. Howe e , in he cons uc ion o hose p o iles, use s di ec ly
egula e hei p i acy and, he e o e, he da a hey inally sha e wi h
he sys em. Fo his eason, he use mus make a decision: sha e some
da a wi hou manipula ing/al e ing hem, o ansmi ing a pe u bed
and mo e gene al e sion o hose da a. Clea ly, depending on he le el
o gene aliza ion applied o each collec ed da a, he p o ile eco ded
in he se e will esemble, o a g ea e o lesse ex en , he genuine,
accu a e p o ile o an indi idual. In his wo k, we shall e e o hese
wo p o iles as he ac ual indi idual p o ile and he appa en indi idual
p o ile, and deno e hem by 𝑞and 𝑡, espec i ely.
Acco dingly, de ine 𝑞as he p obabili y mass unc ion (PMF) o he
au hen ic da a o a pa icula indi idual, and 𝑝as a a ge dis ibu ion
ha is conside ed p i acy insensi i e. Tha is, i an indi idual’s dis i-
bu ion, buil om his/he eco ded da a, was obse ed o be 𝑝by he
se ice p o ide , hen he indi idual would accep he e is no p i acy
isk in he p o iling o his/he ac i i y.
3.2. P o iling
P o iling is a me hod ha iden i ies and cha ac e izes indi iduals
by cons uc ing and applying p o iles. In he echnical li e a u e on
Table 1
Acco ding o he axonomy p o ided in Anon (0000), p i acy models can be classi ied
in o unce ain y-based and indis inguishabili y-based, among o he ypes. In he o me
g oup, a my iad o in o ma ion- heo e ic quan i ies all in o (including Shannon’s
en opy, he one u ilized he e), whe eas in he o me g oup, DP is he mos p ominen
example. Fu he mo e, Shannon’s en opy and Kullback–Leible di e gence ha e been
widely used o quan i y he p i acy o use p o iles o indi idua ion and classi ica ion
ad e sa ies (Xu e al.,2007a;Toubiana e al.,2010a,b;F ed ikson and Li shi s,2011;
Rebollo-Monede o and Fo né,2010;Pa a-A nau e al.,2010,2011,2012b,a,2014c,b;
Rod iguez-Ca ion e al.,2015;Es ada-Jimenez e al.,2019;Pa a-A nau,2017,2018;
Pa a-A nau e al.,2014a).
P o ec ion agains P i acy me ics Da a-pe u ba ion echniques
- Indi idua ion
- Classi ica ion
Shannon’s en opy,
Kullback–Leible
di e gence
- Fo ge y
- Sup ession
- Combina ion o bo h
- Gene aliza ion (ou p oposal)
- O he objec i es
(i.e. Indis inguishabili y)
𝜖-DP, 𝜖-LDP - (Local) Di e en ial p i acy
p o iling (Hildeb and e al.,2005;Hildeb and and Gu wi h,2008),
he e m iden i y has wo dis inc meanings:
•I e e s o unco e ing he unique a ibu es o a pe son, known
as indi idua ion;
•I also means ca ego izing a pe son as a membe o a pa icula
g oup.
Thus, p o iling in ol es dis inguishing one indi idual om all o he s,
as well as iden i ying an indi idual as pa o a speci ic g oup. The
dual applica ion o p o iles — ei he o di e en ia e an indi idual o
o ca ego ize hem — leads o he concep s o indi idual and g oup
p o iling.
In he con ex o in o ma ion sys ems, indi idual p o iling is com-
monly employed o ailo se ices o he unique in e es s and p e e -
ences o use s, aiming o disco e wha se s a pa icula use apa om
he b oade use base. Con e sely, echnologies ha use g oup p o iling
le e age he ac ha a use ’s p o ile may ma ch wi h p o iles de i ed
om he da a o many o he indi iduals. This o m o p o iling applies
p o iles o people whose da a did no con ibu e o he c ea ion o hose
p o iles.
3.3. Ad e sa y model
In his wo k, we conside a passi e a acke ha s i es o indi idu-
a e use s, ha is o say, he ad e sa y wishes o a ge use s who de ia e
om he a e age p o ile o in e es s.
Ou echnique is buil on he p inciple o gene aliza ion da a. Unde
his p inciple, a use may wish o gene alize some pieces o in o ma ion
o enable he esul ing use p o ile 𝑡, as obse ed om he ou side, o
app oach he uni o m p o ile, (which we deno e by 𝑢), he eby hiding a
use ’s pa icula bias owa ds ce ain ca ego ies o in e es .
Bea ing in mind he a acke ’s goal and he use -p o ile model
desc ibed in Sec ion 3.1, we disca d he LDP model and eso o
es ablished p i acy me ics based on di e gence and he unce ain y
o he obse ed p o ile compa ed o a e e ence p o ile (i.e., uni o m,
popula ion-based, e c.) o g oup p o ile, such as Shannon en opy o
Kullback–Leible di e gence. Table 1p o ides a classi ica ion (Anon,
0000) o p i acy models and me ics depending on he a acke ’s goal
behind p o iling.
Las bu no leas , we also assume ha he p i acy a acke is unable
o disce n whe he a pa icula use is adhe ed o he p oposed p i acy
s a egy, and he e o e canno es ima e hei gene aliza ion a e.
3.4. Gene aliza ion model
We shall adop he same no a ion o ec o s used in Boyd e al.
(2004). Speci ically, we delimi ec o s and ma ices wi h squa e b ack-
e s, wi h he componen s sepa a ed by space, and use pa en heses o
cons uc column ec o s om comma sepa a ed lis s.
Compu e s & Secu i y 148 (2025) 104178
4
C. Gil e al.
Fig. 1. Example o 1-le el hie a chy.
We model indi idual p i a e da a (e.g., loca ion ags, music as es,
GPS coo dina es, a ings and bookma ks) as a sequence o andom
a iables ( . .’s) aking on alues in a common ini e alphabe o
ca ego ies, in pa icula he se X= {1,…, 𝑛} o some in ege 𝑛⩾2.
In ou ma hema ical model, we assume hese . .’s a e independen
and iden ically dis ibu ed. This assump ion pe mi s us o ep esen
he p o ile o an indi idual by means o he p obabili y mass unc ion
(PMF) acco ding o which such . .’s a e dis ibu ed, a model ha is
widely accep ed in he p i acy and secu i y li e a u e (Xu e al.,2007b;
Toubiana e al.,2010a;Rebollo-Monede o and Fo né,2010;F ed ikson
and Li shi s,2010;Pa a-A nau e al.,2017). Concep ually, we may
in e p e a p o ile as a his og am o ela i e equencies o indi idual
da a wi hin a p ede ined se o ca ego ies o in e es .
In insic o da a gene aliza ion is he exis ence o a hie a chy o
concep s o axonomy. In his wo k, we shall deno e by 𝑑 he numbe
o hie a chy le els o he han he bo om-le el, and assume ha he
highes -le el ca ego y ( oo ) can be eached om any bo om-le el
ca ego y (lea ) in exac ly 𝑑jumps.
Fo 𝑟= 1,…, 𝑑, we deno e by 𝑔𝑟= (𝑔𝑟
1,…, 𝑔𝑟
𝑛)agene aliza ion s a egy
o le el 𝑟, which is a uple speci ying he pe cen age o use da a ha is
gene alized o ha le el and eco ded as such. Acco dingly, we de ine
𝐺∈R𝑛×𝑑
+as he ma ix whose 𝑟 h column is 𝑔𝑟.
We model he way p o iles a e upda ed ia he se o ma ices
𝑈𝑟∈R𝑛×𝑛
+ o 𝑟= 1,…, 𝑑. In ui i ely, when he p oposed mechanism
(see Sec ion 4 o u he de ails) gene alizes a ce ain piece o da a
(e.g., a loca ion) in o a highe -le el ca ego y ℎ, he mechanism
i. implici ly e ains om eco ding ha da a, and
ii. upda es i s knowledge abou he indi idual’s p o ile on all bo om-
le el ca ego ies alling below ℎ.
The upda e can be made uni o mly ac oss all such bo om-le el ca e-
go ies, o p opo ionally, acco ding o some dis ibu ion. Fo simplici y,
we shall assume he o me case.
Fo a 1-le el hie a chy, we model he p o ile ha esul s om
op imal gene aliza ion (i.e., he appa en p o ile) as
𝑡=𝑞−𝑔1+𝑈1𝑔1.(1)
We immedia ely no e ha gene aliza ion can be ega ded as a combi-
na ion o supp ession and pa ial o ge y. In he case o he hie a chy
depic ed in Fig. 1, whe e 𝑛= 10 and 𝑑= 1, he ma ix 𝑈1 akes his
o m:
𝑈1=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1
∕21
∕20 0 0 0 0 0 0 0
1
∕21
∕20 0 0 0 0 0 0 0
0 01
∕31
∕31
∕30 0 0 0 0
0 01
∕31
∕31
∕30 0 0 0 0
0 01
∕31
∕31
∕30 0 0 0 0
0 0 0 0 01
∕21
∕20 0 0
0 0 0 0 01
∕21
∕20 0 0
0 0 0 0 0 0 01
∕31
∕31
∕3
0 0 0 0 0 0 01
∕31
∕31
∕3
0 0 0 0 0 0 01
∕31
∕31
∕3
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
Le
𝑉𝑟=𝑈𝑟−𝐼𝑛,
whe e 𝐼𝑛is he iden i y ma ix o size 𝑛×𝑛. I is in e es ing o no e ha
𝑉𝑟ma ices a e inally diagonal block ma ices o med by he di ec
sum o nega i e cen e ing ma ices. Acco dingly, in he gene al case
when 𝑑⩾1, he appa en p o ile is modeled as
𝑡=𝑞+
𝑑
∑
𝑟=1
𝑉𝑟𝑔𝑟.(2)
No e om exp essions (1) and (2) ha we a e dealing wi h a
combina ion o supp ession and p opo ional o ge y on he ac ual
p o ile, equi alen o a ansla ion and cen e ing in e ms o ma ix
algeb a.
In his wo k, we shall assume all he da a an indi idual gene a es
can be classi ied in o a bo om-le el ca ego y o ha axonomy. In
o he wo ds, we conside ha he da a collec ed by bo h ou p oposed
p i acy mechanism and he pe sonalized se ice p o ide always e e s
o speci ic in o ma ion abou an indi idual; he aim o he p oposed
mechanism is p ecisely gene alizing hose indi idual da a.
The p oposed gene aliza ion mechanism cap u es he u ili y loss
incu ed by gene alizing indi idual da a h ough a cos ma ix o
dimension 𝑛×𝑑
𝐶=
⎡
⎢
⎢
⎢
⎢
⎣
𝑐11 …𝑐1𝑑
𝑐21 …𝑐2𝑑
⋮ ⋮
𝑐𝑛1…𝑐𝑛𝑑
⎤
⎥
⎥
⎥
⎥
⎦
,
whe e he en y 𝑐𝑖𝑟 ⩾0 e lec s he impac on u ili y due o gene al-
izing a p i a e da a (e.g., a loca ion) ha belongs o he bo om-le el
subca ego y 𝑖, in o a ca ego y o he 𝑟 h le el o he hie a chy.
Fo a single indi idual, we quan i y he e ec i eness o he p o-
ec ion mechanism in gene alizing use da a, h ough he accumula ed
o al cos
𝑑
∑
𝑟=1
𝑐T
⋅,𝑟 𝑔𝑟,
which each indi idual o use would like o uppe bound. Fo simplic-
i y, we shall assume he same bound is applied o all indi iduals wi hin
he popula ion, and deno e i by 𝛾.
3.5. T ade-o be ween p i acy and gene aliza ion a e
We quan i y an indi idual’s p i acy isk gene ically as
=𝑓(𝑡, 𝑝),
whe e 𝑓(𝑡, 𝑝)is ap i acy unc ion ha measu es he ex en o which he
indi idual is discon en when he appa en p o ile is 𝑡and he a ge
p o ile hey would like o look like is 𝑝. As a i s app oxima ion, we
may conside he a ge p o ile o be he uni o m dis ibu ion 𝑢, and he
p i acy unc ion o be he Shannon’s en opy o he appa en p o ile,
= H(𝑡),
and e e o i consis en ly as p i acy gain, a he han p i acy isk. We
use Shannon’s en opy o e lec he in ui ion ha an a acke will be
able o comp omise use p i acy as long as he appa en use p o ile
di e ges om he uni o m p o ile. Recall Co e (1999) ha he en opy
o a PMF 𝑡is de ined as
H(𝑡) = −∑
𝑖=1
𝑡𝑖𝑙 𝑜𝑔𝑏(𝑡𝑖),
whe e 𝑏is he base o he loga i hm used. Common alues o 𝑏a e
2, 𝑒and 10. In hose cases, he uni s o en opy a e bi ,na and di ,
espec i ely. Fo simplici y, we shall use na u al loga i hms h oughou
he pape and e e o log𝑒as ln, pa icula ly because all bases p oduce
equi alen op imiza ion objec i es.
Consis en ly wi h his p i acy en opic measu e, now we de ine he
p i acy gene aliza ion unc ion, o equi alen ly, he op imal p i acy-
u ili y ade-o be ween p i acy and gene aliza ion o an indi idual
(𝛾) = max
𝐺 ≽0
𝐺𝟏≼𝑞 ,
∑𝑑
𝑟=1 𝑐T
⋅,𝑟 𝑔𝑟=𝛾
H(𝑡),(3)
Compu e s & Secu i y 148 (2025) 104178
5
C. Gil e al.
Fig. 2. Block diag am o he p oposed a chi ec u e gi en a hie a chical axonomy wi h labels a anged in o a ee s uc u e.
which o mally exp esses he in ui i e easoning behind da a gene -
aliza ion: he highe he da a gene aliza ion a e 𝛾, he highe he
unce ain y in e ms o he en opy o he appa en dis ibu ion, and
he highe use p i acy.
4. Use -side a chi ec u e
We dedica e his sec ion o desc ibing, adap ing a basic high-le el
a chi ec u e p oposed in A nau (2014), an e en ual and p ac ical im-
plemen a ion o ou op imal da a gene aliza ion mechanism. We know
ha he main pu pose o ou solu ion is o use s o consciously p o ec
hei p i acy agains iden i ica ion a emp s by any a acke . And o do
his, we assis hem in deciding wha p opo ion o da a hey should
gene alize a he cos o losing he minimum unc ionali y in he se ice
hey ecei e. F om his poin o iew, we wan o highligh ha we also
concei e ou p oposal as adecision suppo sys em.
Ou app oach is designed o be in eg a ed in o an applica ion ha
he use al eady has ins alled on hei compu e , o example, a web
b owse plug-in. Inspi ed by he p inciples o ha d p i acy, he a chi-
ec u e we p esen is based on he un us ed model, elimina ing he
need o use s o us hi d pa ies o p o ec hei da a, beyond he
so wa e ins alled on hei own machine. I is o his eason ha we
call i use -side a chi ec u e.
The ope a ion ha he applica ion mus ca y ou is s aigh o wa d.
When he use ’s p i acy is a isk, he sys em launches an ala m and
hen ecommends hem wha da a should be gene alized o deal wi h
he h ea . Hence, i is he use who has he las wo d.
Howe e , be o e de ailing he main unc ional componen s o ou
design, we mus speci y how a use ’s p o ile could be ob ained locally
in an applica ion ha implemen s ou echnique. To do his, we base
ou sel es on h ee assump ions abou said p o ile.
1. Common knowledge. Fi s , We assume ha bo h ins ances, he
so wa e applica ion and he e en ual p i acy a acke s, ope a e
on an iden ical p ede ined axonomy o ca ego ies o in e es
and he e o e ob ain, based on hei ca ego iza ion algo i hms,
he same use p o ile. This assump ion is conside ed alid o he
ex en ha we a e dealing wi h se s o s anda d and gene alized
ca ego ies.
2. P o ile ini ializa ion. Second, we assume ha o decide whe he
o gene alize a pa icula ca ego y o no , ou app oach needs an
ini ial use p o ile. This ci cums ance can be aken in o accoun
h ough a aining pe iod p io o he implemen a ion o he
a chi ec u e we p opose. Exclusi ely du ing his p e ious phase,
he use will explain he in e es s since unde his assump ion,
an a acke could know he eal p o ile.
3. Long- e m p o ile. And addi ionally, we assume ha he use ’s
p o ile is no subjec o equen changes, in line wi h he so-
called long- e m p o iles (Gauch e al.,2007). The p o ile ac-
qui es s abili y a e he ini ializa ion phase p e iously no ed,
when he use has sha ed a signi ican numbe o elemen s.
S ill, we mus ecognize ha , in p ac ice, use in e es s can a y
signi ican ly o e ime and, he e o e, ou solu ion mus ake his
in o accoun .
Fig. 2desc ibes, h ough a block diag am, he so wa e a chi ec u e
ha we p opose as an applica ion. I is made up o a se ies o modules
ha in e ac locally and/o wi h he sys em, so ha each o hem pe -
o ms a speci ic unc ion based on he pa ame e s i ecei es. Al hough
ou solu ion can wo k wi h any ype o gene alizable da a, he igu e
shows he case o esou ce agging on he Web, ha is, when use s’
p i a e da a a e ags.
F om a gene al pe spec i e, he igu e shows a use in e ac ing wi h
a single, simple PIS, and mo e speci ically, wi h an hie a chical agging
sys em. I is an en i y ha , in exchange o pe sonalized in o ma ion
o in e es , s o es and p o ides use s wi h elemen s o in o ma ion ( o
example, music, ideos and web pages, poin s o in e es o geog aph-
ical coo dina es) and hei co esponding associa ed ags, which can
o m pa o a hie a chical axonomy. Below we p o ide a unc ional
desc ip ion o he modules ha make up his a chi ec u e.
Web b owse . Unlike he es o he modules, we assume ha
he web b owse can be p e iously ins alled on he use ’s compu e .
This is an ex e nal elemen o ou gene aliza ion applica ion, which we
unde s and as a complemen o he i s . The b owse is esponsible o
he use ’s communica ion wi h he PIS, en i ies ha eed each o he
in o ma ion. Thus, a use downloads h ough his o he b owse ha
con en (e.g. images, web pages, e c.) ha will be agged acco ding o
his o he in e es s, including he ags ha o he use s ha e published
Compu e s & Secu i y 148 (2025) 104178
6
C. Gil e al.
in he agging sys em. And in he same way, he b owse sends he
labels p oposed by he use o he PIS. Meanwhile, all da a e ie ed by
he b owse (e.g. me ada a) is passed o he con ex analyze module o
p ocess he in o ma ion.
Con ex analyze . The pu pose o his module is o assis he ca e-
go y ex ac o module in deciding which use p o ile ca ego y should
be upda ed (gene alized). This p ocess could be ca ied ou using
he ec o space model (Sal on e al.,1975), as is no mally done in
he ield o in o ma ion e ie al, o ep esen Web pages as uples
con aining hei mos ep esen a i e e ms. Fo example, e m in e se
documen equency (TF-IDF) could be applied o calcula e he weigh s
o each e m ha appea s on he web page ha includes he i em o
be ca ego ized. Subsequen ly, aking some o he mos weigh ed e ms
om he uple, i would send hem o he ca ego y ex ac o module.
Ca ego y ex ac o . This elemen plays a c ucial ole in classi ying
he ags ha he use submi s o he PIS wi hin a p ede ined se o
ca ego ies. In ce ain cases, hese ca ego ies a e p o ided by he label-
ing sys em, as seen on pla o ms such as Amazon, bu hey can also be
acqui ed h ough specialized da abases, such as he Cu lie Di ec o y.3
Du ing his p ocess, he label sugges ed by he use and he con ex ual
in o ma ion p o ided by he con ex analyze module a e in eg a ed.
The esul , p esen ed in he o m o ca ego ies, is ansmi ed o he
use p o ile cons uc o and p i acy ala m gene a o modules.
Use p o ile cons uc o . This module gene a es he use p o ile.
In speci ic e ms, i ecei es he ca ego ies associa ed wi h he ags
sen by he use and, acco dingly, es ima es and/o upda es hei
p o ile. As men ioned abo e, ou p oposed a chi ec u e assumes ha ,
when es ima ing he his og am, he ela i e equencies o ac i i y a e
su icien ly s able once he use has gene a ed a signi ican numbe o
labels. A c ucial aspec ha a p ac ical implemen a ion o his module
mus ake in o accoun is p o ile ini ializa ion. One op ion could be o
s a his p o ile a ze o (Viejo e al.,2012). On he o he hand, an
app oach based on he p inciple o maximum en opy would choose o
use he uni o m dis ibu ion. Impo an ly, his module emains ac i e
e en when he use explici ly decla es he p o ile. Since he p o ile
indica ed by he use may no accu a ely e lec hei online beha io ,
ou a chi ec u e may decide, a e he aining phase, o eplace i wi h
he p o ile implici ly in e ed om hei in e ac ion ac i i y ( agging)
wi h he sys em.
Gene aliza ion s a egy gene a o . This module is esponsible o
he use ’s p i acy and he e o e we conside i he cen al elemen o
he a chi ec u e we p opose. Equipped wi h he implemen a ion o ou
op imal gene aliza ion mechanism, and based on wo inpu pa ame e s,
he eal use p o ile 𝑞, he numbe o hie a chy le els o he han he
bo om-le el 𝑑and he gene aliza ion a e 𝛾, which ep esen s he
pe cen age o da a o be gene alized, he esul o i s calcula ions is
he op imal uple o gene alized da a 𝑔∗. Fo example, he componen
𝑔∗
𝑖 e e s o he pe cen age o da a ha is sugges ed o be ca ego ized
in o he op-le el ca ego y 𝑖. In Sec ion 3.5, we p o ide mo e de ailed
speci ica ion o his module.
P i acy ala m gene a o . The ask o his module is o ale he
use abou possible iola ions o hei p i acy. Whene e he use
sha es hei pe sonal in o ma ion h ough ags, his module wai s o
he ca ego y ex ac o module o send he ca ego y co esponding o
said ag, ep esen ed by he index 𝑖. And when i ecei es he uple, i
execu es he ollowing ac ions. A p i acy wa ning wi h p obabili y 𝑔𝑖
is gene a ed, no i ying he use . I is he use ’s esponsibili y o decide
whe he o no o gene alize he da a in case o ala m ac i a ion. And
o he wise, ou applica ion will no iden i y any p i acy h ea s and will
ansmi he in o ma ion o he web b owse .
3h ps://cu lie.o g/.
Table 2
Desc ip ion o he a iables used in ou no a ion.
Symbol Desc ip ion
𝑛Numbe o in e es ca ego ies
𝑑Numbe o hie a chy le els
𝑚Numbe o op-le el ca ego ies
𝑛𝑘Numbe o bo om-le el ca ego ies by each op-le el ca ego y
𝑔𝑟Agene aliza ion s a egy is an 𝑛- uple wi h he pe cen age o
obse ed da a ha is gene alized a le el 𝑟
𝑞The ac ual use p o ile is he genuine p o ile o in e es s
𝑡The appa en use p o ile is he pe u bed p o ile, as obse ed om
he ou side, esul ing om he gene aliza ion o ce ain pe cen age
o obse ed da a
𝑢Uni o m p o ile ac oss he 𝑛ca ego ies
𝑉𝑟The gene aliza ion ma ix a le el 𝑟
𝐶The cos ma ix on which he p oposed gene aliza ion mechanism
cap u es he u ili y loss incu ed by gene alizing indi idual da a
H(𝑡)Use p i acy is measu ed as he Shannon’s en opy o he appa en
use p o ile
𝛾The gene aliza ion a e is he pe cen age o obse ed da a ha he
use is willing o gene alize
(𝛾)Func ion modeling he p i acy–gene aliza ion ade-o
𝛾𝑐 𝑟𝑖𝑡 The c i ical gene aliza ion is he gene aliza ion a e beyond which
he p i acy–gene aliza ion unc ion a ains i s maximum alue o
c i ical p i acy
5. Theo e ical analysis
In his sec ion, we shall analyze one o he main and undamen al
p ope ies o he p i acy-gene aliza ion unc ion (3) de ined in he
p e ious sec ion. Ou heo e ical analysis only conside s he case when
all gi en p obabili ies a e s ic ly posi i e:
𝑞𝑖>0 o all 𝑖= 1,…, 𝑛. (4)
This assump ion will be p ope ly jus i ied in Sec ion 5.1. We shall
suppose u he , now wi hou loss o gene ali y, ha
𝑞𝑖≤⋯≤𝑞𝑛 o all 𝑖= 1,…, 𝑛. (5)
Be o e p oceeding wi h he ma hema ical analysis, i is immedia e
om he de ini ion o he p i acy-gene aliza ion unc ion ha i s ini ial
alue is (0) = H(𝑞). The no a ion used h oughou his sec ion is
summa ized in Table 2.
5.1. C i ical gene aliza ion
The ollowing heo e ical p ope y con i ms he in ui ion ha he e
mus exis a gene aliza ion a e beyond which c i ical p i acy is achie -
able, in he sense ha he p i acy–gene aliza ion unc ion a ains i s
maximum heo e ical alue by g oups o op-le el ca ego ies, ha is,
(𝛾) =𝜙≤ln(𝑛).4This c i ical gene aliza ion is
𝛾𝑐 𝑟𝑖𝑡 = 1 −
𝑚𝑑
∑
𝑘=1
𝑛𝑘𝑞1𝑘,(6)
whe e 𝑚𝑑is he numbe o ca ego y se s a op-le el o he hie a chy
and acco ding o he labeling assump ion (5). Ou pu pose is o o mu-
la e and p o e a heo em ha cap u es his p ope y. I is impo an o
no e ha his p ope y also p o ides an uppe bound on he alue o
(𝛾).
Theo em 1(C i ical Gene aliza ion).Fo all 𝛾∈ [0,1), i 𝛾≥𝛾𝑐 𝑟𝑖𝑡, hen
(𝛾) =∑𝑚
𝑘=1 𝑛𝑘H( 𝑞𝑘). Con e sely, i 𝛾 < 𝛾𝑐 𝑟𝑖𝑡, hen (𝛾)<∑𝑚
𝑘=1 𝑛𝑘H( 𝑞𝑘).
P oo . Fi s , suppose ha a he maximum alue o (𝛾) he appa en
p o ile 𝑡is cons an (uni o m) o g oups o op-le el ca ego ies. In he
4No e ha wi h only one se o op-le el ca ego ies (𝑚= 1), i ollows ha
𝑡=𝑢= 1∕𝑛and (𝛾) =𝑙 𝑛(𝑛).
Compu e s & Secu i y 148 (2025) 104178
7
C. Gil e al.
case o a single hie a chy le el (𝑑= 1), by algeb aic manipula ion o
Eq. (1) we can exp ess he esou ces 𝑔in he o m 𝑔𝑖𝑘 =𝑔1𝑘+𝑞𝑖𝑘 −
𝑞1𝑘∀𝑖 >1, 𝑘. Adding all he e ms we a i e a an exp ession o he
gene aliza ion a e, ha is, 𝛾= 1 +∑𝑚
𝑘=1 𝑛𝑘𝑔1𝑘−∑𝑚
𝑘=1 𝑛𝑘𝑞1𝑘. Fo 𝛾 o
each i s highes alue wi hin he in e al [0,1), he i s componen
o he esou ces o each g oup o high-le el ca ego ies will necessa ily
ha e o be ze o, ha is, 𝑔1𝑘= 0,𝑘= 1,…, 𝑚, hus ob aining he desi ed
Eq. (6).
Fu he mo e, in all cases we can exp ess he op imal esou ce
s a egy o he c i ical gene aliza ion a io in he o m 𝑔𝑖𝑘 =𝑞𝑖𝑘 −𝑞1𝑘
o all 𝑖 >1and 𝑘. In his way, he appa en p o ile 𝑡will ha e a
uni o m alue o each g oup o op-le el ca ego ies, ha is, 𝑡𝑖𝑘 =𝑞𝑘,
𝑘= 1,…, 𝑚, unde s anding 𝑞𝑘as he a e age o ac ual use p o ile a
he 𝑘 h g oup o ca ego ies. Then, he c i ical alue o he p i acy–
gene aliza ion unc ion is (𝛾) =∑𝑚
𝑘=1 𝑛𝑘H( 𝑞𝑘). Following he same
easoning, he pa icula case (𝑑= 1) is ex ensible o he gene al
case. ■
Co olla y 2(P i acy Bound).The c i ical p i acy (𝛾) =∑𝑚
𝑘=1 𝑛𝑘H( 𝑞𝑘)is
uppe bounded by ln(𝑛).
P oo . F om Gibbs’ inequali y we know ha H𝑛a ains i s max-
imum alue when all p obabili ies a e equal, i.e., H𝑛(𝑞1,…, 𝑞𝑛)≤
H𝑛(1∕𝑛, …,1∕𝑛). In ha case, H𝑛(1∕𝑛, …,1∕𝑛) = ln(𝑛). In u n, acco ding
o he s uc u e o ou p oblem we ha e −∑𝑚
𝑘=1 ∑𝑛𝑘
𝑖=1 1∕𝑛ln(1∕𝑛) =
∑𝑚
𝑘=1 𝑛𝑘H(1∕𝑛) =𝑙 𝑛(𝑛). I ollows hen ha (𝛾) =∑𝑚
𝑘=1 𝑛𝑘H( 𝑞𝑘)≤
∑𝑚
𝑘=1 𝑛𝑘H(1∕𝑛) = ln(𝑛).■
Compa ison wi h o ge y and supp ession. The analy ical cha ac e -
iza ion o he c i ical gene aliza ion a e is a undamen al esul : we can
analy ically de e mine he amoun o pe u ba ion needed o achie e
maximum p o ec ion, and based on his, igu e ou whe he o no a
use can achie e i mo e o less easily.
Al hough ob iously he c i ical a e depends on each p o ile, a
na u al ques ion one would ask is: how is his c i ical a e in ela-
ion o s a e-o - he-a pe u ba ion echniques, namely, o ge y and
supp ession. We aim o shed some ligh in o his ques ion nex .
We conduc ou i s expe imen o some conc e e use p o ile,
e alua ing he s a e-o - he-a echniques op imal o ge y (Rebollo-
Monede o and Fo né,2010) and op imal supp ession (Pa a-A nau
e al.,2012b;Rod iguez-Ca ion e al.,2015), e sus he p oposed
op imal gene aliza ion mechanism. Toge he wi h Rebollo-Monede o
and Fo né (2010), hence o h deno ed o ge y .1, we also assess a
a ia ion he eo ( o ge y .2), which models he appa en p o ile
as ollows: 𝑡= (𝑞+𝑟)∕(1 +𝜌), whe e 𝜌is he pe u ba ion a e and 𝑟a
o ge y s a egy analogous o ou 𝑔. This model is in con as wi h he
o iginal o mula ion o op imal o ge y (Rebollo-Monede o and Fo né,
2010), whe e 𝑡= (1 −𝜌)𝑞+𝜌 𝑟.
Fig. 3shows he esul s o he use p o ile
𝑞= (0.02,0.03,0.04,0.05,0.07,0.10,0.12,0.15,0.17,0.25)
and he hie a chy ‘‘3-le el oy28’’ o Fig. 5(e). In he igu e, we can
obse e ha , o his speci ic p o ile,
𝜌c i < 𝛾c i < 𝜎c i ,
which means ha o ge y can p o ide he highes le el o p o ec ion
wi h a smalle pe u ba ion a e han gene aliza ion and supp ession
would do. In he igu e, we would like o no e ha , unlike gene aliza-
ion, supp ession and o ge y ely on bo om-le el ca ego ies o pe u b
p o iles (which is deno ed wi h he label ‘‘0-le el’’ in he igu e). The
ac ha he e is no hie a chy o ca ego ies in supp ession and o ge y
implies, on accoun o Theo em 1, ha he p i acy le el a ained
by hese wo echniques will ne e be smalle han ha o e ed by
gene aliza ion.
Because he esul s epo ed in Fig. 3a e highly dependen on
he chosen p o ile, ou second expe imen con empla es 608 andom
Fig. 3. P i acy, measu ed as he Shannon’s en opy o a use ’s appa en p o ile, s.
pe u ba ion a e, o 3-le el gene aliza ion, supp ession and wo e sions o he o ge y
echnique. (Fo in e p e a ion o he e e ences o colo in his igu e legend, he eade
is e e ed o he web e sion o his a icle.)
Fig. 4. C i ical pe u ba ion a es o 608 andomly-gene a ed, 16-dimensional p o iles
s. he di e ence 𝑞16 −𝑞1, o op imal gene aliza ion, supp ession and o ge y .1. Each
da a poin e lec s a p o ile, and da ke p o iles in gene aliza ion imply la ge numbe
o high-le el ca ego ies. (Fo in e p e a ion o he e e ences o colo in his igu e
legend, he eade is e e ed o he web e sion o his a icle.)
p o iles o dimension 𝑛= 16 o e some possible high-le el hie a chies.
Mo e speci ically, o each o hese andom p o iles, we show in Fig. 4
he c i ical a es o gene aliza ion, supp ession and o ge y in he
o dina e, and he di e ence 𝑞16 −𝑞1in he abscissa. Ou choice o
he abscissa is jus i ied by he ac ha 𝜌c i = 1 − −1∕𝑛 𝑞𝑛(Rebollo-
Monede o and Fo né,2010) and 𝜎c i = 1 − −𝑛 𝑞1(Pa a-A nau e al.,
2012b), which, oge he wi h Eq. (6), imply 𝑞1and 𝑞𝑛a e he only
p o ile componen s a ec ing he h ee c i ical a es.
Hie a chy-wise, om Eq. (6) i ollows ha 𝛾c i depends jus on
he highes le el. To explo e he e ec o he numbe o high-le el
ca ego ies in gene aliza ion, da a poin s (i.e., p o iles) in Fig. 4wi h
da ke colo e lec p o iles wi h highe numbe o such ca ego ies.
Fig. 4shows he supe io i y o gene aliza ion in e ms o c i ical
a es wi h espec o he s a e-o - he-a pe u ba ion echniques. Fo
he andom p o iles gene a ed, op imal gene aliza ion la gely achie es
he maximum p i acy le el ∑𝑚
𝑘=1 𝑛𝑘H( 𝑞𝑘)a signi ican ly lowe pe -
u ba ion a es han o ge y and supp ession. In Sec ion 6we shall
examine deepe his ques ion wi h eal p o iles.
Compu e s & Secu i y 148 (2025) 104178
8
C. Gil e al.
Fig. 5. Toy examples o d-le el hie a chies.
5.2. Nume ical example
In his sec ion, we show some nume ical esul s o a simple bu
insigh ul example ha will illus a e he o mula ion p esen ed in
Sec ions 3.4 and 3.5 and he heo e ical analysis a gued in Sec ion 5.
Th oughou his subsec ion, all esul s co espond o a same a i icial
use . The expe imen al analysis o ou p i acy-enhancing mechanism
in a eal-wo ld applica ion is p esen ed la e in Sec ion 6.
In his p ac ical example, we shall conside 𝑛= 10 bo om-le el ca e-
go ies and assume ha he use dis ibu ion is again 𝑞= (0.02,0.03,0.04,
0.05,0.07,0.10,0.12,0.15,0.17,0.25), hus ul illing bo h he posi i i y
and he labeling assump ions (4) and (5). Fo simplici y, we also assume
ha he cos ma ix 𝐶is he all-ones ma ix. Fu he mo e, on he same
use p o ile, we conside i e possible gene aliza ion hie a chies wi h
le els 𝑑= 1,2and 3, which we illus a e in Fig. 5. No e ha he
examples e ol e om he lowe p ele el example, s a ing wi h he
same basic 1-le el example, namely oy2323. In Fig. 6we can obse e
he s uc u e o he gene aliza ion ma ices 𝑉1, 𝑉2and 𝑉3in o de o
o m in each case he co esponding Eq. (2) om he 1-le el oy2323,
2-le el oy253 and 3-le el oy73 examples. No ice how, a each
le el, he gene aliza ion ma ix has as many diagonal blocks as g oups
o ca ego ies ha ha e been de ined o ha le el. Fu he mo e, he
dimension o each squa e block co esponds o he numbe o lowes
le el ca ego ies ha he g oup o ca ego ies con ains.
To sol e nume ically he op imiza ion p oblem (3) we used CVX, a
package o speci ying and sol ing con ex p og ams (G an and Boyd,
2014a,b) and MOSEK (ApS,2019). Bo h ha e been un on Ma lab
so wa e (Ma lab R2021 9.10.0.1602886 64-bi win64) wi h an In el
Co eTM i3-2370 2.4 GHz CPU, 4 Gb RAM in a Windows 10 64-bi
ope a ing sys em.
F om he poin o iew o he use p o iles, in Fig. 7we ep e-
sen he appa en p o ile o he use om he 3-le el oy73 exam-
ple, o di e en alues o he gene aliza ion a e 𝛾. When 𝛾= 0,
no pe u ba ion akes place and he appa en p o ile 𝑡 ep esen ed
in Fig. 7(a) ac ually co esponds o he genuine use p o ile 𝑞. Ac-
co ding o he easoning behind he op imal gene aliza ion s a egies
p e iously desc ibed, he highe 𝛾, he mo e uni o m is he esul ing
appa en p o ile. As illus a ed in Fig. 7(d), he maximum le el o
p i acy is a ained p ecisely o 𝛾=𝛾𝑐 𝑟𝑖𝑡 = 0.41, when he appa en
p o ile is comple ely uni o m by he wo op-le el ca ego ies and
he e o e, ollowing he exp essions ob ained in he Theo em 1,𝑡∗≃
(0.06,0.06,0.06,0.06,0.06,0.06,0.06,0.19,0.19,0.19) and H(𝑡∗) ≃ 2.1463.
All his in o ma ion is also cap u ed in Fig. 8, whe e we plo he
p i acy-gene aliza ion unc ion (3), ha is, he unc ion modeling he
op imal ade-o be ween p i acy and u ili y, he la e being measu ed
as he pe cen age o da a gene alized by he use . Howe e , in he
igu e we collec he in o ma ion o he i e hie a chy examples ha
we use on he same use .
F om his poin o iew, he i s hing we obse e is ha in all
cases, he unc ion (𝛾)beha es non-dec easing and quasciconca e, as
we poin ed ou a he end o ou heo e ical analysis. S a ing om a
common ini ial alue, namely (0) = H(𝑞) = 2.0652, and depending on
he a e o gene aliza ion 𝛾, he op imal ade-o g ows wi h di e en
in ensi ies un il i eaches c i ical alue o he a e, namely 𝛾c i , and
ollowing he calcula ions o (6), a which p i acy g ow h s alls. In his
sense, he bes inc ease o 7% is ob ained when he use ca ego izes
hei in e es s unde he 3-le el oy28, so ha H(𝑡∗) = ≃2.2086
al hough a he cos o a c i ical a e 𝛾c i = 0.64.
A inal ema k is he in luence o he hie a chy le el 𝑑on use
p i acy. We obse e ha he highe he hie a chy le el, he g ea e he
p i acy.
6. Expe imen al analysis
In his sec ion, we will discuss he ex en o which ou echnique
enables use s o enhance hei p i acy in a pe sonalized eal-wo ld
sys em. Ou analysis also looks a he impac ha da a gene aliza ion
has on in o ma ion loss using a measu e o u ili y ha we call he
gene aliza ion a e, namely 𝛾.
6.1. Da ase s
We applied he p oposed echnique o Fou squa e (Yang e al.,
2014) and B igh ki e (Cho e al.,2011), wo eal-wo ld da ase s col-
lec ed om loca ion-based social ne wo ks (LBSNs) which a e well-
know by he scien i ic communi y o da a mining asks in he ield.
Compu e s & Secu i y 148 (2025) 104178
9
C. Gil e al.
Schwab, K., 2015. The ou h indus ial e olu ion: wha i means, how o espond.
Fo eign A . 12, 2015–2017.
Shakil, A i , M., Sohail, S.S., Alam, M.T., Ubaid, S., Na is, M.T., Wang, G., 2021.
Towa ds a wo- ie a chi ec u e o p i acy-enabled ecommende sys ems (PeRS).
In: Ine na ional Con e ence on Ubiqui ous Secu i y. Sp inge , pp. 268–278.
Toubiana, V., Na ayanan, A., Boneh, D., Nissenbaum, H., Ba ocas, S., 2010a. Adnos ic:
P i acy p ese ing a ge ed ad e ising. In: P oceedings Ne wo k and Dis ibu ed
Sys em Symposium.
Toubiana, V., Na ayanan, A., Boneh, D., Nissenbaum, H., Ba ocas, S., 2010b. Adnos ic:
P i acy p ese ing a ge ed ad e ising. In: P oc. Symp. Ne w. Dis ib. Sys . Secu ..
SNDSS, pp. 1–21.
Ullah, I., Binbusayyis, A., 2022. Join op imiza ion o p i acy and cos o in-app mobile
use p o iling and a ge ed ads. IEEE Access 10, 38664–38683.
Union, I.T., 2020. Measu ing digi al de elopmen : Fac s and igu es 2020.
Viejo, A., Sánchez, D., Cas ella-Roca, J., 2012. Using p o iling echniques o p o ec
he use ’s p i acy in Twi e . In: In e na ional Con e ence on Modeling Decisions
o A i icial In elligence. Sp inge , pp. 161–172.
Wang, H., Hong, H., Xiong, L., Qin, Z., Hong, Y., 2022. L-s : Local di e en ial p i acy
o loca ion-based se ices wi h s ai case andomized esponse. In: P oceedings o
he 2022 ACM SIGSAC Con e ence on Compu e and Communica ions Secu i y. pp.
2809–2823.
Wang, T., Zhang, X., Feng, J., Yang, X., 2020. A comp ehensi e su ey on local
di e en ial p i acy owa d da a s a is ics and analysis. Senso s 20 (24), 7030.
Xiong, X., Liu, S., Li, D., Cai, Z., Niu, X., 2020. A comp ehensi e su ey on local
di e en ial p i acy. Secu . Commun. Ne w. 2020, 1–29.
Xu, Y., Wang, K., Zhang, B., Chen, Z., 2007a. P i acy-enhancing pe sonalized web
sea ch. In: P oc. In . WWW Con .. ACM, pp. 591–600.
Xu, Y., Wang, K., Zhang, B., Chen, Z., 2007b. P i acy-enhancing pe sonalized web
sea ch. In: P oceedings o he 16 h In e na ional Con e ence on Wo ld Wide Web.
pp. 591–600.
Yang, M., Guo, T., Zhu, T., Tjuawina a, I., Zhao, J., Lam, K.-Y., 2023. Local di e en ial
p i acy and i s applica ions: A comp ehensi e su ey. Compu . S and. In e aces
103827.
Yang, D., Zhang, D., Zheng, V.W., Yu, Z., 2014. Modeling use ac i i y p e e ence by
le e aging use spa ial empo al cha ac e is ics in LBSNs. IEEE T ans. Sys . Man
Cybe n. 45 (1), 129–142.
Ye, S., Wu, F., Pandey, R., Chen, H., 2009. Noise injec ion o sea ch p i acy p o ec ion.
In: 2009 In e na ional Con e ence on Compu a ional Science and Enginee ing. Vol.
3, IEEE, pp. 1–8.
Compu e s & Secu i y 148 (2025) 104178
16
