(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`(19) World Intellectual Property
`Organization
`International Bureau
`\
`(43) International Publication Date &
`WIPOl PCT
`25 June 2015 (25.06.2015)
`
`(10) International Publication Number
`
`WO 2015/090445 A1
`
`(51)
`
`International Patent Classification:
`G06F 21/60 (2013.01)
`G06F 21/62 (2013.01)
`
`(81)
`
`(21)
`
`International Application Number:
`
`PCT/EP2013/077687
`
`(22)
`
`International Filing Date:
`
`20 December 2013 (20.12.2013)
`
`(25)
`
`(26)
`
`(71)
`
`(72)
`
`Filing Language:
`
`Publication Language:
`
`English
`
`English
`
`Applicant: TELEFONAKTIEBOLAGET L M ERIC-
`SSON (PUBL) [SE/SE]; S-164 83 Stockholm (SE).
`
`Inventors: MOHAN, Saravanan; 39/1 Akbar Street, Trip-
`licane, Chennai 600005 (IN). SREEDHAR, Kumaresh;
`Door n07, plot no 10, 2nd Main Road, Nethaji Colony,
`Chennai 600042 (IN).
`
`(84)
`
`(74)
`
`Agent: EGRELIUS, Fredrik; Ericsson AB, Patent Unit
`Kista DSM, S—16480 Stockholm (SE).
`
`Designated States (unless otherwise indicated, for every
`kind ofnational protection available): AE, AG, AL, AM,
`AO, AT, AU, AZ, BA, BB, BG, BH, BN, BR, BW, BY,
`BZ, CA, CH, CL, CN, CO, CR, CU, CZ, DE, DK, DM,
`DO, DZ, EC, EE, EG, ES, FI, GB, GD, GE, GH, GM, GT,
`HN, HR, HU, ID, IL, IN, IR, IS, JP, KE, KG, KN, KP, KR,
`KZ, LA, LC, LK, LR, LS, LT, LU, LY, MA, MD, ME,
`MG, MK, MN, MW, MX, MY, MZ, NA, NG, NI, NO, NZ,
`OM, PA, PE, PG, PH, PL, PT, QA, RO, RS, RU, RW, SA,
`SC, SD, SE, SG, SK, SL, SM, ST, SV, SY, TH, TJ, TM,
`TN, TR, TT, TZ, UA, UG, US, UZ, VC, VN, ZA, ZM,
`ZW.
`
`Designated States (unless otherwise indicated, for every
`kind of regional protection available): ARIPO (BW, GH,
`GM, KE, LR, LS, MW, MZ, NA, RW, SD, SL, SZ, TZ,
`UG, ZM, ZW), Eurasian (AM, AZ, BY, KG, KZ, RU, TJ,
`TM), European (AL, AT, BE, BG, CH, CY, CZ, DE, DK,
`EE, ES, FI, FR, GB, GR, HR, HU, IE, IS, IT, LT, LU, LV,
`MC, MK, MT, NL, NO, PL, PT, RO, RS, SE, SI, SK, SM,
`TR), OAPI (BF, BJ, CF, CG, CI, CM, GA, GN, GQ, GW,
`KM, ML, MR, NE, SN, TD, TG).
`
`[Continued on nextpage]
`
`(54) Title: METHOD AND APPARATUS FOR MANAGING ACCESS TO A DATABASE
`
`(57) Abstract: A method (100, 400) for
`managing access to a database is dis-
`closed. The method comprises receiving
`a database query, (110), executing the
`query on the database to obtain a result,
`(120), generating a noise value, (130),
`perturbing the result with the generated
`noise value, (140), and outputting the
`perturbed result, (150). The noise value
`is generated from a bimodal probability
`distribution having a minimum probabil-
`ity at zero noise. Also disclosed is an ac-
`cess management processing element,
`(200, 300, 600) for a database.
`
`100
`
`/
`
`
`
`Perturb the result with the generated noise value from a bimodal
`probability distribution having a minimum probability at zero noise
`
`140,
`
`Figure 2
`
`
`
`W02015/090445A1|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`

`

`WO 2015/090445 A1 |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`Published:
`
`— with international search report (Art. 21(3))
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`Method and apparatus for managing access to a database
`
`Technical Field
`
`The present invention relates to a method and apparatus for managing access to a
`
`database.
`
`The present
`
`invention also relates to a computer program product
`
`configured, when run on a computer, to carry out a method for managing access to a
`
`database.
`
`1O
`
`Background
`
`Large amounts of personal data are collated and stored by a range of businesses and
`
`organisations.
`
`In many circumstances, it is desirable to share insight and intelligence
`
`that may be gained from such data, without compromising the privacy of individuals
`
`contributing to the data. One way in which this may be achieved is through the
`
`construction of a statistical database, which holds the personal data and accepts
`
`queries from third parties.
`
`Instead of releasing individual data entries, the statistical
`
`database gives out statistical results based on the characteristics of the personal data
`
`held within the database.
`
`Example queries which may be submitted include
`
`summations or aggregate counts.
`
`In order to provide increased privacy protection for
`
`individuals contributing to the database, the statistical database may release inaccurate
`
`results, such as a range within which the query result falls, rather than the value of the
`
`query result.
`
`In principle, statistical databases permit
`
`the sharing of
`
`intelligence gained from
`
`personal data without compromising the privacy of individual data entries. However,
`
`malicious third parties, known as adversaries, may formulate queries with the specific
`
`purpose of deducing individual data entries from the database. Using carefully
`
`formulated query combinations, frequently combined with auxiliary information obtained
`
`from other independent sources, adversaries can gain access to individual data entries.
`
`The growth of communication networks has led to an unprecedented rise in the volume
`
`and detail of personal data available to the operators of such networks and to service
`
`providers who offer services through the networks. This data may include details of
`
`subscriber interests, commercial activities and subscriber location, as well as identity
`
`data and mobility data for the subscriber. Mobility data contains the approximate
`
`15
`
`20
`
`25
`
`30
`
`35
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`2
`
`whereabouts of individual subscribers in the network at any given time, and can be
`
`used to reconstruct an individual’s movements over a period of time.
`
`Individual mobility
`
`traces have been used to provide personalised services to users including tracking the
`
`movement of a competitor sales force, registering subscriber attendance at a particular
`
`event or individual subscriber presence in a specific location (e.g. hotel, commercial
`
`centre or hospital). Such data may also be used by service providers or third party
`
`marketers for the development of personalised advertising campaigns. Anonymised
`
`mobility data may also be provided to third parties for use in human mobility analysis,
`
`which involves the study of individual and group movement patterns in order to provide
`
`useful
`
`insight for a range of practical applications including urban planning,
`
`traffic
`
`congestion mitigation, mass transit planning, healthcare and education planning,
`
`ecological and green development etc.
`
`Communication network providers may thus make legitimate use of statistical data
`
`based on the large volume of information about subscribers’ real world activities to
`
`which they have access. They may also make such statistical data available for
`
`legitimate third party use. However, unethical advertisers or other adversaries may
`
`seek to acquire from the statistical data sensitive information about
`
`individual
`
`subscribers in order to support aggressive or abusive marketing practices. This may
`
`involve combining data from different independent sources with complex database
`
`query combinations in order, for example,
`
`to track individual user locations or other
`
`sensitive individual data. This data may then be used for aggressive marketing or to
`
`create a highly individualised, believable message for the targeting of even more
`
`sensitive information from the user, as is the case in phishing scams and other spam
`
`10
`
`15
`
`20
`
`25
`
`mail.
`
`Although an anonymized dataset does not contain name, home address, phone
`
`number or other identifiers,
`
`if an individual’s mobility patterns are sufficiently unique,
`
`independently sourced secondary information may be used to link mobility data back to
`
`3O
`
`an individual.
`
`In order to protect the privacy of individuals whose data may be held in a statistical
`
`database, techniques have been developed to ensure the anonymity of individual data
`
`entries and combat the above discussed abusive practices. A first technique is known
`
`35
`
`as k-anonymity, and involves suppressing or generalising individual data attributes until
`
`each row or entry within the database is identical to at least k—1 other entries. Although
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`3
`
`this technique hides the personal identity of individuals within a database, it has been
`
`shown that adversaries possess sufficient additional sources of personal data to enable
`
`the mapping of
`
`individual users onto an anonymised data set, so compromising
`
`individual privacy.
`
`Another technique which may be used to protect privacy in statistical databases is
`
`differential privacy. This technique involves adding noise to a query result before that
`
`result is released to the third party generating the query, with the aim of ensuring that
`
`the presence or absence of any particular
`
`individual
`
`in
`
`the database will not
`
`significantly affect the noise perturbed query result.
`
`In this manner, a third party is
`
`prevented from using sophisticated query combinations with auxiliary data to determine
`
`individual data entries. The noise value to be added to the query result is usually
`
`generated according to a Laplacian probability distribution, although a Gaussian
`
`distribution may also be used. The probability distribution is often scaled according to
`
`the sensitivity of the query,
`
`in an effort
`
`to balance the conflicting aims of privacy
`
`protection and the provision of useful statistical data. A probability distribution for
`
`Laplacian noise is illustrated in Figure 1, with noise values on the x axis and probability
`
`of generating noise values on the y axis. The width of the distribution may be scaled
`
`according to the sensitivity of the query, sometimes referred to as the diameter of the
`
`query. The mean of the distribution is set to zero, such that positive and negative noise
`
`values are equally likely.
`
`The aim of differential privacy is to perturb the results of database queries such that
`
`privacy of individuals is protected while still providing statistical data that is of value to
`
`third parties. While this technique has proved effective in the past, experiments have
`
`shown that when applied to use cases including human mobility data, as well as other
`
`existing use cases, known differential privacy techniques remain vulnerable to
`
`aggressive adversary querying strategies.
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`Summary
`
`It is an aim of the present invention to provide a method and apparatus which obviate
`
`or reduce at least one or more of the disadvantages mentioned above.
`
`35
`
`According to an aspect of the present
`
`invention,
`
`there is provided a method for
`
`managing access to a database, comprising receiving a database query, executing the
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`4
`
`query on the database to obtain a result, generating a noise value, perturbing the result
`
`with the generated noise value and outputting the perturbed result. The noise value is
`
`generated from a bimodal probability distribution having a minimum probability at zero
`
`noise.
`
`The database may be a statistical database.
`
`In some examples, the noise value may
`
`be generated from a bimodal probability distribution which is bounded.
`
`Such a
`
`distribution may place limits upon the magnitude of noise values which may be used to
`
`perturb a query result.
`
`In some examples,
`
`the noise value may be generated from a bimodal probability
`
`distribution which has a mean at zero noise.
`
`In some examples,
`
`the noise value may be generated from a bimodal probability
`
`distribution which is a u-quadratic probability distribution.
`
`In some examples, perturbing the result with the generated noise value may comprise
`
`adding the noise value to the generated result.
`
`In some examples, the method may further comprise determining a sensitivity of the
`
`received database query, and generating a noise value may comprise scaling the
`
`bimodal probability distribution according to the determined sensitivity.
`
`In some examples,
`
`sensitivity of
`
`the received database query may comprise a
`
`maximum value of the L1 norm of the difference in query result caused by the presence
`
`or absence of a single database element.
`
`In some examples, the method may further comprise retrieving a utility parameter, and
`
`generating a noise value may comprise scaling the bimodal probability distribution
`
`according to the retrieved utility parameter.
`
`In some examples retrieving a utility
`
`parameter may comprise getting the parameter from a memory. The utility parameter
`
`may thus be selected by an operator and programmed into a memory for retrieval.
`
`Alternatively, retrieving the utility parameter may comprise generating the parameter.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`5
`
`In some examples, scaling according to sensitivity and utility parameter may comprise
`
`equating a vertical scale parameter of the bimodal probability distribution to a
`
`combination of the sensitivity and the utility parameter.
`
`In some examples, the combination of sensitivity and utility parameter may comprise
`
`the square of a term formed by dividing the utility parameter by the sensitivity.
`
`According to another aspect of the present invention, there is provided a computer
`
`program product configured, when run on a computer, to execute a method according
`
`to the first aspect of the present invention. Examples of the computer program product
`
`may be incorporated into an apparatus such as an access management processing
`
`element for a database. The computer program product may be stored on a computer-
`
`readable medium, or it could, for example, be in the form of a signal such as a
`
`downloadable data signal, or it could be in any other form. Some or all of the computer
`
`program product may be made available via download from the internet.
`
`According to another aspect of the present invention, there is provided an access
`
`management processing element
`
`for a database, comprising a
`
`receiving unit
`
`configured to receive a database query, a query unit configured to execute the query
`
`on the database to obtain a result and a privacy unit configured to generate a noise
`
`value and to perturb the result with the generated noise value.
`
`The access
`
`management processing element further comprises an output unit configured to output
`
`the perturbed result. The privacy unit is configured to generate the noise value from a
`
`bimodal probability distribution having a minimum probability at zero noise. According
`
`to examples of the invention, the units of the access management processing element
`
`may be functional units, which may be realised in any combination of hardware and/or
`
`software.
`
`In some examples, the privacy unit may be configured to generate the noise value from
`
`a bimodal probability distribution which is bounded.
`
`In some examples, the privacy unit may be configured to generate the noise value from
`
`a bimodal probability distribution which has a mean at zero noise.
`
`In some examples, the privacy unit may be configured to generate the noise value from
`
`a u—quadratic probability distribution.
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`In some examples, the privacy unit may be configured to perturb the result with the
`
`generated noise value by adding the noise value to the generated result.
`
`In some examples,
`
`the privacy unit may comprise a query analyser configured to
`
`determine a sensitivity of the received database query, and the privacy unit may be
`
`configured to scale the bimodal probability distribution according to the determined
`
`sensitivity.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`In some examples, the privacy unit may further comprise a utility unit configured to
`
`retrieve a utility parameter, and the privacy unit may be configured to scale the bimodal
`
`probability distribution according to the retrieved utility parameter.
`
`In some examples,
`
`the privacy unit may be configured to equate a vertical scale
`
`parameter of the bimodal probability distribution to a combination of the sensitivity and
`
`the utility parameter
`
`In some examples, the combination of sensitivity and utility parameter may comprise
`
`the square of a term formed by dividing the utility parameter by the sensitivity.
`
`According to another aspect of the present invention, there is provided an access
`
`management processing element for a database, the access management processing
`
`element comprising a processor and a memory, the memory containing instructions
`
`executable by the processor whereby the access management processing element is
`
`operative to receive a database query, execute the query on the database to obtain a
`
`result, generate a noise value, perturb the result with the generated noise value and
`
`output the perturbed result. The access management processing element is further
`
`operative to generate the noise value from a bimodal probability distribution having a
`
`minimum probability at zero noise.
`
`In some examples,
`
`the access management processing element may be further
`
`operative to generate the noise value from a bimodal probability distribution which is
`
`bounded.
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`7
`
`In some examples,
`
`the access management processing element may be further
`
`operative to generate the noise value from a bimodal probability distribution which has
`
`a mean at zero noise.
`
`In some examples,
`
`the access management processing element may be further
`
`operative to generate the noise value from a bimodal probability distribution which is a
`
`u-quadratic probability distribution.
`
`In some examples,
`
`the access management processing element may be further
`
`operative to perturb the result with the generated noise value by adding the noise value
`
`to the generated result.
`
`In some examples,
`
`the access management processing element may be further
`
`operative to determine a sensitivity of the received database query and to scale the
`
`bimodal probability distribution according to the determined sensitivity.
`
`In some examples,
`
`the access management processing element may be further
`
`operative to retrieve a utility parameter and to scale the bimodal probability distribution
`
`according to the retrieved utility parameter.
`
`In some examples,
`
`the access management processing element may be further
`
`operative to equate a vertical scale parameter of the bimodal probability distribution to
`
`a combination of the sensitivity and the utility parameter.
`
`In some examples, the combination of sensitivity and utility parameter may comprise
`
`the square of a term formed by dividing the utility parameter by the sensitivity.
`
`Brief Description of the Drawings
`
`For a better understanding of the present invention, and to show more clearly how it
`
`may be carried into effect, reference will now be made, by way of example,
`
`to the
`
`following drawings in which:
`
`Figure 1 illustrates the probability density function for a Laplace distribution;
`
`Figure 2 is a flow chart showing steps in a method for managing access to a database;
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`Figure 3 is a block diagram illustrating functional units of an access management
`
`processing element for a database.
`
`Figure 4 is a block diagram illustrating functional units of another access management
`
`processing element for a database.
`
`Figure 5 illustrates the probability density function for a u-quadratic distribution;
`
`Figure 6 is a flow chart showing steps in another method for managing access to a
`
`database;
`
`Figure 7 is a block diagram representation of operation of the method of Figure 6;
`
`Figure 8 is a block diagram illustrating functional units of another access management
`
`processing element for a database; and
`
`Figures 9 and 10 are graphs illustrating the results of experiments investigating
`
`effectiveness of the method of Figure 6.
`
`Detailed Description
`
`Aspects of the present invention provide a method for managing access to a database,
`
`which may be a statistical database. Examples of the method allow for efficient
`
`balancing of utility of released information with protection of privacy for individuals
`
`whose data is present in the database. Figure 2 is a flow chart illustrating steps in such
`
`a method 100. As discussed in further detail below,
`
`the method may run on a
`
`dedicated processing element controlling access to the database. Such a processing
`
`element may be located with the database or in a dedicated network node of a
`
`communications network operating and populating the database.
`
`With reference to Figure 2,
`
`in a first step 110 the method comprises receiving a
`
`database query. The database query may be in a prescribed form such as a
`
`summation query or other forms of query specified by the operator of the database to
`
`be acceptable.
`
`In a second step 120, the method comprises executing the received
`
`query on the database to obtain a result. The method then comprises, at step 130,
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`9
`
`generating a noise value, which noise value is then used to perturb the query result in
`
`step 140. The noise value is generated from a bimodal probability distribution having a
`
`minimum probability at zero noise.
`
`Finally, at step 150,
`
`the perturbed result
`
`is
`
`outputted to the third party with whom the query originated.
`
`The database may for example be a statistical database, containing data compiled by
`
`an authority such as a communications network operator. Such operators may wish to
`
`make statistical
`
`information relating to the data in the database available to third
`
`parties, such as third party marketing companies. The operators may therefore allow
`
`such third parties to interact with the database by submitting queries. As discussed in
`
`the background section, malicious third parties, known as adversaries may attempt to
`
`determine individual data entries from the database through complex querying
`
`strategies and the use of independently obtained auxiliary data.
`
`In order to protect the
`
`individuals whose data is contained in the database,
`
`the methods of the present
`
`invention act as a release mechanism, perturbing an actual query result with a noise
`
`value, so protecting the privacy of individuals while still providing useful data to the third
`
`party.
`
`A feature of the above method 100 is that the noise value used to perturb the query
`
`result is generated from a bimodal probability distribution having a minimum probability
`
`at zero noise. As discussed above, known differential privacy methods have in the
`
`past used Laplace or Gaussian probability distributions for the generation of noise to
`
`perturb query results. The mean of these distributions is set to zero noise, such that
`
`positive and negative noise values are equally likely. Both the Laplace and Gaussian
`
`distributions have a peak or maximum probability value at zero noise, with probability
`
`values decreasing and tailing off with increasing noise values. Such distributions have
`
`been considered desirable,
`
`the thinking being that they promoted the use of small
`
`noise values, so increasing the utility of the released data to the third parties.
`
`However, the peak at zero noise means that while small noise values may be likely, the
`
`most likely action is in fact the addition of zero noise. Zero noise represents high utility
`
`data for the third party but a considerable risk to the privacy of the individuals whose
`
`data populates the database.
`
`In contrast to previous approaches, the method 100
`
`generates noise from a bimodal distribution having a minimum probability at zero noise.
`
`The nature of a bimodal distribution means that
`
`the probability of noise values
`
`increases away from the zero noise value. According to the method 100, zero noise is
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`10
`
`therefore the least likely noise value, providing greater protection to the privacy of
`
`individuals in the database.
`
`As noted above, apparatus for conducting the method 100, for example on receipt of
`
`suitable computer readable instructions, may be incorporated within a processing
`
`element, which may be a dedicated access management processing element for a
`
`database. Figure 3 illustrates functional units in an access management processing
`
`element 200 for a database. The processing element 200 may execute the steps of
`
`Figure 2 for example according to computer readable instructions received from a
`
`computer program.
`
`It will be understood that the units illustrated in Figure 3 are
`
`functional units, and may be realised in any appropriate combination of hardware
`
`and/or software.
`
`With reference to Figure 3,
`
`the access management processing element 200
`
`comprises a receiving unit 210, a query unit 220, a privacy unit 230 and an output unit
`
`250. The receiving unit 210 is configured to receive a database query from a third
`
`party. The receiving unit passes the query to the query unit 220, which is configured to
`
`execute the query on the database, returning a query result. The query unit 220
`
`passes the query result to the privacy unit 230, which is configured to generate a noise
`
`value and to perturb the query result with the generated noise value, the noise value
`
`being generated from a bimodal probability distribution having a minimum probability at
`
`zero noise. The privacy unit 230 then passes the perturbed query result to the output
`
`unit 250, which is configured to output the perturbed query result to the third party.
`
`In
`
`some examples of the invention, the privacy unit 230 may further comprise additional
`
`functional sub units, the functionality of which is discussed in further detail below with
`
`reference to Figure 8.
`
`Referring to Figure 4, in another example, an access management processing element
`
`300 for a database may comprise a processor 360 and a memory 370. The memory
`
`370 contains instructions executable by the processor 360 such that the processing
`
`element 300 is operative to conduct the steps of Figure 2 described above.
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`Operation of the method of Figure 2, for example executed by processing elements
`
`according to Figures 3 and 4,
`
`is now described in greater detail with reference to
`
`35
`
`Figures 5 to 8.
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`11
`
`In some examples of the invention, the bimodal probability distribution used to generate
`
`a noise value may be a u-quadratic probability distribution, an example of which is
`
`illustrated in Figure 5. The u-quadratic distribution is a polynomial bimodal distribution
`
`with peaks at both the minimum and maximum noise that could be used to perturb the
`
`true value of the query result, for example by being added to the true query result. The
`
`core of the u-quadratic distribution is a quadratic function and the curve is inverted-bell
`
`shaped, or u-shaped. The continuous u-quadratic distribution is defined by a unique
`
`quadratic function with lower limit “a” and upper limit “b”:
`
`1O
`
`f(x|a,b,a,B) = a(X-B)2,forxe [a,b]
`
`Equation1
`
`The distribution has only two parameters a, b, as or and B are explicit functions of the
`
`support defined by a and b:
`
`The gravitational balance centre or offset B is defined as: B=(b+a)/2 ----
`
`Equation 2
`
`The vertical scale or is defined as: cr=12/(b-a)3 ———— Equation 3
`
`for a E (-|nfinity, Infinity), and b E (a, Infinity)
`
`The mean and variance of the distribution are defined as:
`
`Mean= (a+b)/2 and Variance= 3 (b-a)2/20
`
`----
`
`Equations 4 and 5
`
`According to examples of the present invention, the mean is set to zero such that the
`
`generation of positive and negative noise values is equally likely. The u-quadratic
`
`distribution offers two importance features with respect to the generation of noise
`
`values for perturbing query results: the preservation of privacy and the preservation of
`
`utility. The importance of balancing privacy protection with the release of useful data
`
`has been discussed above, and noise generated according to a u-quadratic probability
`
`distribution offers an effective solution to the problem of balancing these conflicting
`
`aims.
`
`Privacy preservation
`
`15
`
`20
`
`25
`
`30
`
`35
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`12
`
`The u—quadratic probability function slopes upwards in both the directions from the
`
`mean of zero noise. Consequently, the probability density curve has a base at zero
`
`noise, meaning that the probability of generating zero noise for perturbing the query
`
`result
`
`is at or around zero. Ensuring that a non-zero noise is used in at
`
`least a
`
`significant majority of cases affords improved privacy protection with respect
`
`to
`
`previously known methods. Additionally, every noise value in the domain except zero
`
`possesses a non-zero probability, resulting in use of a non-zero noise value to perturb
`
`every query result: action to protect individual privacy is thus always taken. Evidence
`
`of this improved privacy protection can be seen in Experiments 1 and 2 below.
`
`10
`
`15
`
`2O
`
`Utility preservation
`
`The u-quadratic distribution is a bounded distribution and hence there exists no
`
`possibility for use of an unbounded noise value with a query result, which noise value
`
`might render the final disclosed output useless. Laplace and Gaussian distributions
`
`are unbounded. Although the probability of noise values reduces with increasing noise
`
`magnitude, the probability even at very high noise value is non zero, meaning the
`
`possibility exists for the generation of very large positive or negative noise values, the
`
`use of which could render the outputted query result meaningless.
`
`In contrast to the
`
`unbounded Laplace and Gaussian distributions,
`
`the u-quadratic distribution has
`
`maximum and minimum values a and b, which values may be scaled according to the
`
`nature of the query, as discussed in further detail below. These limits unsure an
`
`excessively large noise value is never used and so provide increased utility of data
`
`released to third parties. Evidence of this increased utility can be seen in Experiment 3
`
`25
`
`below.
`
`In some examples,
`
`the u—quadratic probability distribution used to generate noise
`
`values may be scaled according to a sensitivity of the query received, where sensitivity
`
`provides an indication of how results of the query differ with changes to the contents of
`
`the database. The noise used to perturb the query result may thus be adjusted
`
`according to the nature of the query and of the information in the database: if the query
`
`and database are such that a difference in a single database element has very little
`
`impact on the query result, then only small noise perturbation may be necessary to
`
`protect privacy. However,
`
`if a single element difference in the database has a large
`
`impact on the query result, then a greater noise perturbation may be required to protect
`
`3O
`
`35
`
`

`

`WO 2015/090445
`
`PCT/EP2013/077687
`
`13
`
`privacy, and hence the probability distribution used to generate the noise values may
`
`be scaled to increase the probability of generating larger noise values.
`
`Sensitivity may thus comprise an indication of the difference in query outcome
`
`depending on the presence or absence of single database element. The indication
`
`may be a maximum value of the L1 norm of the difference in query result caused by the
`
`presence or absence of a single database element. Thus, for two statistical databases
`
`D1, D2 which differ on a single element, the sensitivity Af of a query f(D) may be given
`as:
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`M = maXD1,02”f(D1)— f(DZ) ll1
`
`Equation 6
`
`In order to protect individual privacy,
`
`it is desirable to perturb query results such that
`
`the difference in result when run on database D1 and database D2 is minimal, so
`
`reducing the possibility for a malicious third party to infer individual data entries from
`
`different query results.
`
`By scaling the probability distribution according to query
`
`sensitivity, the probability of generating particular noise values is adjusted to match the
`
`magnitude of noise that
`
`is
`
`likely to be necessary to achieve the desired privacy
`
`protection.
`
`A utility parameter v may also be introduced in order to adjust the scaling of the
`
`probability distribution according to a desired balance between privacy protection and
`
`data utility. The utility parameter v expresses the accuracy of the perturbed output
`
`query, and thus provides a numerical representation of the balance to be achieved
`
`between privacy and utility of data. Thus for two datasets D1, D2 which differ only on a
`
`single element:
`
`Pr[Z(D1) €
`
`7'] S v2 Pr[Z(DZ) €
`
`T]
`
`----
`
`Equation 7
`
`where Z is a randomized v—quadratically private algorithm for all datasets D1 and D2, T
`
`Q Range(Z) and Range(Z) denotes the output range of the algorithm 2.
`
`Scaling of the u-quadratic probability distribution may be conducted on the basis both
`
`of the sensitivity Af of the query to be executed and the utility parameter v to be
`
`applied. Scaling is accomplished by equating the vertical scale or of the distribution to
`
`the square of the term formed b