Efficent Low Cost Process For Single Step Metal Forming of 3D Interconnected Above-IC Inductors

This paper presents a novel and efficient low cost process capable of integrating high-Q above-IC inductors and their interconnects using a single electroplating step. It relies on the SU8 and BPN resist as well as an optimized electroplating technique to form the 3D interconnected inductor. The SU8 is used to form a thick layer located underneath the inductor to elevate it from the substrate. Then, the BPN is used as a high resolution mold (16:1) for copper electroplating. Standard or time optimized electroplating is later used to grow copper in a 3D manner, making the transition between all metallic layers straight forward. High-Q (55 @ 5 GHz) power inductors have been designed and integrated above an RF power LDMOS device using this process. Finally, the process capabilities are demonstrated by integrating a solenoid inductor using only two lithography masks and a single electroplating step.

I.

INTRODUCTION

The limited availability of low-loss integrated inductor structures has long hindered the development of integrated circuits such as passive filters, matching networks, transformers, etc. Been mostly planar, these inductors tend to suffer from high losses and low quality factors (Q) at RF frequencies. These losses result generally from dielectric and/or magnetic losses incurred from coupling between the inductor and the host substrate, as well as from resistive losses due to the use of thin and relatively high resistivity conductors. Generally, the substrate poses the main challenge for High-Q inductor design and integration when its resistivity is very low, which is the case of high power RF devices like LDMOS.

Some approaches have been proposed to address the above issues for enhancing the overall performance of inductors. High resistivity silicon [START_REF] Ashby | High Q inductors for wireless applications in a complementary silicon bipolar process[END_REF] or SOI [START_REF] Gianesello | High current 3D symmetrical inductor integrated in an advanced HR SOI CMOS technology targeting RF power applications[END_REF] substrates offer an ideal solution, but they either aren't an option for all silicon technologies or present major drawbacks like high cost, limited heat dissipation and difficult implementation of backside source contact. Etching the silicon under the inductor [START_REF] Lei | Concave-Suspended High-Q Solenoid Inductors With an RFIC-Compatible Bulk-Micromachining Technology[END_REF], micromachining suspended planar coils or 3D structures [START_REF] Zou | Development of Three-Dimensional Inductors Using Plastic Deformation Magnetic Assembly (PDMA)[END_REF] [START_REF] Jun-Yu | Fabrication and Characterization of Microscaled On-Chip Toroidal Inductors[END_REF] are alternatives but they suffer from high process complexity/cost and from incompatibility with above-IC processing. Inserting a patterned ground shield between the inductor and the substrate [START_REF] Yue | On-chip spiral inductors with patterned ground shields for Si-based RF ICs[END_REF][7] enhances the performance, but, this solution appears ineffective for very low resistivity substrates [START_REF] Ghannam | High-Q SU8 based above-IC inductors for RF power devices[END_REF].

Therefore, a single yet efficient technology for inductors integration that can reply to both RF performance and industrial needs and compatible with existing IC technologies is required. Moreover, to meet the requirements for various applications, the process must allow depositing a dielectric with thicknesses ranging from few microns to more than 100 µm as well as ribbons with different widths and thicknesses. For example, unlike low power inductors, High-Q power inductors requires both thick dielectric and metallic layer [START_REF] Ghannam | High-Q SU8 based above-IC inductors for RF power devices[END_REF], which was always a blocking point for inductor integration on high power devices.

In a previous work [START_REF] Ghannam | High-Q SU8 based above-IC inductors for RF power devices[END_REF], we demonstrated means to optimize Above-IC inductors and presented a low cost SU8 based Above-IC process [START_REF] Ghannam | Low Cost SU8 Based Above IC Process for High-Q RF Power Inductors Integration[END_REF] capable of integrating High-Q RF power inductors. However, this process was mainly optimized for planar inductors and like other processes, its complexity rises drastically if complex shaped interconnects or structures like multilevel or 3D inductors have to be integrated. Figure 1 illustrates the technological steps of a typical planar process [START_REF] Ghannam | Low Cost SU8 Based Above IC Process for High-Q RF Power Inductors Integration[END_REF] used to integrate a distributed above-IC inductor. The technological steps are the following: The presence of vias during spinoff results an uneven SU8 surface which then requires mechanical polishing. (h) Sputtering the second seed layer and depositing the third negative photoresist layer. (i) Electroplating the third metallic layer.

Ayad GHANNAM 1 , Lamine OURAK 1,2 , David BOURRIER 1 , Christophe VIALLON 1,2 , Thierry PARRA 1,2 1 CNRS ; LAAS Toulouse, France 2

UPS University of Toulouse

Toulouse, France (j) Dissolving the negative resist and etching the seed layer.

Therefore, for 3D integration, this process suffers from several drawbacks such as:

• The relatively high number of technological steps that increases cost and processing time.

• The presence of a mechanical polishing step to level the SU8's surface, which increases the risk of wafer break and the processing time, is critical for manufacturing.

• The high mechanical strain on the wafer due to the presence of the SU8 on its whole surface (20 MPa for 90 µm thick SU8 [START_REF] Bourrier | Comparisons of the new thick negative resist to Su8 resist[END_REF]). • The presence of the seed layer at the interface between interconnects and the inductor, which can be broken during a mechanical stress (during backside thinning, for example).

a) f) b) g) c) h) d) i) e) j)
Substrate Seed Layer Neg. resist SU8 resist Copper Figure 1. Interconnected inductor integration steps using a planar Above-IC process

In this work, we present a novel and efficient low cost SU8 based process that overcomes all previous drawbacks and that leads to Above-IC integration of 3D interconnected inductors using a single metal electroplating step. The process relies on SU8 patterning, 3D seed layer deposit and 3D copper electroplating to form the inductor with its interconnects in a single metallization step. As a result, the number of technological steps and cost is reduced while enhancing both mechanical properties and electrical performance of the inductors. Moreover, the process is compatible with standard lithography and electroplating techniques, which makes its industrial implementation easy and straightforward. The process was used to integrate RF power inductors above a 50 W RF LDMOS transistor. Its capability is also demonstrated by integrating a solenoid inductor using two lithography masks and a single electroplating step.

II. PROCESS AND RESULTS

A. 3D interconnected inductor forming technique

Three-dimensionally copper electroplating is the key point to create the 3D interconnected inductor in a single metallization step. To achieve this, three prerequisites must be met which are: 1/ the dielectric must be patterned at specific locations; 2/ the seed layer deposit must be 3D; 3/ the copper electroplating needs a thick photoresist mold with a good resolution (high aspect ratio).

1) Dielectric resist choice and patterning

In this work, the SU8 resist was used as a dielectric for its good electrical characteristics for frequencies up to 7 GHz [START_REF] Ghannam | Dielectric microwave characterization of the SU-8 thick resin used in an above IC process[END_REF] and for its convenient technological properties. This resist allows depositing a dielectric layer with a wide range of thicknesses in a single spin-coat. Shapes with aspect ratios higher than 16:1 and vertical sidewalls can be realized.

Patterning and locating the dielectric under the inductor allows its elevation from the substrate while enabling direct access to the underlying substrate (metallic pads) (Figure 2.a). Therefore, after successful deposit of a 3D seed layer, both the substrate and the dielectric surfaces/faces will be electrically connected. This electrical continuity allows 3D copper electroplating of the inductor, vias (interconnects) and pads in a single step. This process presents a lot of advantages such as mainly the elimination of the mechanical polishing of the SU8, the reduction of mechanical strain, the large improvement of cost and processing time, etc.

The process isn't limited to a single dielectric layer since, if needed, multi-layers can be interconnected in a single electroplating step by simply adding additional SU8 layers as shown on Figure 2.b. As illustrated, two SU8 layers are used, one deposited on the entire wafer surface with via openings, and the other one only located under the inductor. This kind of topology poses a challenge for seed layer deposit as highlighted in the next paragraph.

Substrate

Seed Layer SU8 resist Copper

2) 3D Seed layer deposit

For copper growing with a single electroplating step, a 3D seed layer must be deposited insuring the electrical continuity between the substrate and the dielectric surfaces. This step poses a great challenge because of the vertical nature of the SU8's sidewalls. Furthermore, depending on the pattern's shape (pillar like or hollows), size, density and the used equipment (evaporation, sputtering), the seed layer deposit can be fairly easy or quite difficult. In fact, if evaporation technique is used, the presence of a high vertical sidewall might create an amber-like (shadow) effect which can produce a seed layer locally thinner or even voids (Figure 3 electroplating current. Sputtering technique can enhance the seed layer thickness homogeneity. However, in some severe cases, like the presence of narrow hollows (Figure 2.b), approaches like seed layer enhancement (SLE) must be used [START_REF] Beica | Advanced Metallization for 3D Integration[END_REF]. This SLE is done using a chemical solution for deposition of a thin 3D conductive layer on all the surfaces.

When the seed layer is homogenous, the electroplating current will circulate in a 3D matter allowing copper growing on all exposed surfaces and sidewalls which are bound into the electroplating mold.

3) Photoresist for thick mold formation

The choice of resist for mold formation is related to two major parameters. Firstly, it must be capable to reach high thicknesses as well as high aspect ratios. Secondly, it must be easily strippable. Under these conditions, the BPN negative resist appears the best choice. This resin has been optimized in our clean room to reach thicknesses as high as 160 µm with an aspect ratio of 16: 1 [START_REF] Bourrier | Comparisons of the new thick negative resist to Su8 resist[END_REF]. The main difficulties were to find the correct annealing temperatures/time, UV dose and development time since the presence of pillars/hollows creates two (or more) distinctive thicknesses to insulate (Figure 3.b).

B. Experimentation and results

For experimentation, 3D interconnected high-Q power inductors similar to the one presented on Figure 1 have been designed and integrated above a very low resistivity substrate using the following technological steps (Figure 4): a) Deposit of an 85 µm thick SU8 layer by spin coating and lithography to locate the SU8 under the future inductor. b) Evaporation of a titanium/gold seed layer followed by the deposit of a 100 µm thick BPN layer using spin coating, and apply photolithography to create molds for electroplating. c) Copper electroplating. d) BPN dissolution and seed layer etching.

The process used for an 85 µm thick SU8 layer deposit is the following:

• Coating of SU8 3050: 8 ml spun at 1500 RPM for 30s.

• Pre-anneal: 1 min @ 65 °C then 40 min @ 95 °C.

• Exposure: 360 mj/cm². • Post exposure bake: 1 min @ 65 °C then 3 min @ 95 °C.

• Development: 15 min using PGMEA.

• Final anneal: 1 min @ 65 °C then 2 min @ 125 °C.

For molds, we deposited a 100 µm thick BPN layer using the following steps:

• Coating of BPN: 8 ml spun at 750 RPM for 30s.

• Pre-anneal: 3 min @ 60 °C then 4 min @ 120 °C. Under probes measurements of these inductors exhibit a Q value of 55 at 5 GHz for a total inductance value of 0.8 nH (Figure 6). The good agreement between measurements and simulations must be pointed out, which validates both our inductor optimization and the technological process control.

1) Inductors above 50W LDMOS transistor

After validation, these inductors are applied above a low resistivity (8 mΩ.cm) power LDMOS silicon substrate. The inductor's ribbons are 110 µm wide and 40 µm thick. For their integration, two layers of SU8 with total thickness of 85 µm are deposited. The first layer is covering the entire wafer and integrates via openings, whereas the second one is located underneath each inductor (Figure 7). This design uses a pillar/hollow combination to demonstrate the effectiveness of the process. Figure 7 shows the excellent transition between all levels and the good filling of the vias.

2) Solenoid inductor

For further illustration of the new process capabilities, we integrated 3D solenoid inductors using only two lithography masks and a single electroplating step. These inductors are implemented using 90 µm thick SU8 pillars for realization of the upper parts of the ribbon. After copper electroplating, SU8 is removed. a) b)

Figure 8. SEM micrographs of a 3D inductor fabricated using the new process Figure 8.a shows an overall view of the integrated 3D solenoid inductor. Figure 8.b gives detail where the vertical copper from the substrate to the SU8 must be pointed out. On this example, the copper thickness is only 8 µm. One can also notice the excellent homogeneity of the ribbon's thickness on all surfaces and sidewalls.

III. CONCLUSION

An efficient and low cost above-IC process for the realization of 3D interconnected inductors using a single copper electroplating step is proposed. This process relies on three main developments: patterning of the SU8 based dielectric at specific locations, 3D deposit of a void free and homogenous seed layer thickness for 3D copper electroplating on all surfaces and sidewalls, and finally formation of thick molds using the BPN resist for keeping a good ribbon resolution. Inductors with vertical interconnections have been integrated on an 85 µm thick SU8 dielectric layer deposited on a very low resistivity silicon substrate. An excellent electroforming of the 3D copper ribbons has been demonstrated, and inductor measurements show a Q of 55 at 5 GHz. Furthermore, capabilities of the new process are fully applied for 3D integration of solenoid inductors using only two masks and a single metallic step. Finally, this technology appears of strong interest for passive device manufacturing since it can fit a large range of applications, like on chip antenna integration, packaging, baluns/transformers... and since it is fully compatible with standard IC process.

  (a) Sputtering the first seed layer and depositing the first negative photoresist layer. The openings in the resist will be used as a mold for copper electroplating of pads. (b) Electroplating copper to form the first metal level. (c) Dissolving the negative resist. (d) Depositing a second negative resist to form via holes. (e) Electroplating copper vias. (f) Dissolving the negative resist and etching the seed layer. (g) Depositing the SU8 layer which is used as dielectric.

Figure 2 .

 2 Figure 2. Methods of forming a 3D interconnected inductor: a) SU8 only under the inductor. b) two layers of SU8

  .a). Such thin or inhomogeneous seed layer can fuse while applying the a) b)

Figure 3 .

 3 Figure 3. Process difficulties: a) Seed layer. b) BPN lithography

•

  Exposure: 1350 mj/cm². • Development: 5 min using TMAH.

Figure 4 .Figure 5 .Figure 6 .

 456 Figure 4. 3D interconnected inductor integration steps using the novel process

Figure 7 .

 7 Figure 7. SEM micrograph 3D interconnected inductors integrated above a 50 W LDMOS transistor

ACKNOWLEDGMENT

The authors would like to thank Jean Marie BOULAY and Gerard BOUISSE from Freescale Semiconductors for supplying LDMOS wafers.


Ondřej Kaplan

Karel Bezouška

Anna Malandra

Alicja B Veselá

Alena Petříčková

Jürgen Felsberg

Anna Rinágelová

Vladimír Křen

Ludmila Martínková
email: martinko@biomed.cas.cz

Genome mining for the discovery of new nitrilases in filamentous fungi

Keywords: Aromatic nitrilase, Arylacetonitrilase, Aspergillus niger, Gibberella moniliformis, Neurospora crassa

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Nitrilases are useful for the preparation of carboxylic acids or amides from nitriles. However, their selectivity or stability is often a limitation to their applicability (Zhu et al. 2008). New nitrilases (wild-type or mutant enzymes) with improved properties would therefore be advantageous.

Most nitrilases have been obtained by either strain enrichment [START_REF] Asano | Overview of screening for new microbial catalysts and their uses in organic synthesisselection and optimization of biocatalysts[END_REF] or by a metagenomic approach [START_REF] Robertson | Exploring nitrilase sequence space for enantioselective catalysis[END_REF]). Genome mining, though, has become popular and new nitrilases have been obtained in this way from Synechocystis sp. [START_REF] Heinemann | Cloning of a nitrilase gene from the cyanobacterium Synechocystis sp. strain PCC6803 and heterologous expression and characterization of the encoded protein[END_REF], Pyrococcus abyssi [START_REF] Mueller | Cloning, overexpression, and characterization of a thermoactive nitrilase from the hyperthermophilic archaeon Pyrococcus abyssi[END_REF], Bradyrhizobium japonicum (Zhu et al. 2008;[START_REF] Seffernick | Investigative mining of sequence data for novel enzymes: A case study with nitrilases[END_REF]) and Burkholderia xenovorans [START_REF] Seffernick | Investigative mining of sequence data for novel enzymes: A case study with nitrilases[END_REF]. Several cyanide hydratases from fungi were also obtained using this method [START_REF] Basile | Genome mining of cyanide-degrading nitrilases from filamentous fungi[END_REF]). Here we have used this approach to search for new nitrilases in fungi which appears to be an abundant but so far relatively untapped, source of these enzymes [START_REF] Kato | Distribution of aldoxime dehydratase in microorganisms[END_REF][START_REF] Martínková | Fungal nitrilases as biocatalysts: Recent developments[END_REF].

Materials and methods

Database mining and sequence alignment

Database searches were performed using the BLASTX and BLASTP programmes (http://www.ncbi.nlm.nih.gov/blast/Blast.cgi) and the multiple aligment of amino acid sequences using COBALT: Constraint-based Multiple Alignment Tool (http://www.ncbi.nlm.nih.gov/tools/cobalt/ cobalt.cgi).

DNA manipulations

Synthetic nit genes (GeneArt, Regensburg, Germany; Table 1) were ligated into the NdeI and HindIII sites in pET 30a(+) plasmid (Novagen). The codon frequency was optimized using GeneArt´s own software. The resulting vectors were transformed into E. coli BL21-Gold (DE3) (Agilent Technologies -Stratagene Products) to give strains OK103 through OK105 (Table 1).

Enzyme assay

Nitrilase activity was assayed with an appropriate amount of whole cells in Tris/HCl buffer (50 mM, pH 8.0; 150 mM NaCl) with benzonitrile or phenylacetonitrile (25 mM each) as substrate. After 10 min at 30 °C with shaking, concentrations of substrates and products were determined by HPLC.

Results and discussion

Selection and heterologous expression of genes encoding hypothetical nitrilases

To obtain new nitrilases from filamentous fungi, GenBank was searched for nit genes and three distantly related ones (with amino acid identities of approximately 40 %; see Online resource 1 for multiple sequence aligment) were selected. These genes encoded hypothetical nitrilases in Gibberella moniliformis (GenBank: ABF83489), Aspergillus niger CBS 513.88 (GenBank: XP_001397369) and

Neurospora crassa OR74A (GenBank: CAD70472).
Genes optimized in terms of codon bias in Escherichia coli were synthesized (see Online resource 2 for optimized gene sequences), cloned into the pET 30a(+) plasmid and expressed under the T7 promotor without the His-Tag. After nitrilase induction with IPTG, all recombinant strains expressed protein subunits with the expected molecular weights (36-37 kDa). SDS-PAGE indicated nitrilase expression levels increasing in the following order: G. moniliformis << A. niger < N. crassa (Fig. 1).

The nitrilase activities were assayed with benzonitrile and phenylacetonitrile as typical substrates of aromatic nitrilases and arylacetonitrilases, respectively [START_REF] O'reilly | The nitrilase family of CN hydrolysing enzymes -a comparative study[END_REF]. Although the expression protocol was not optimized, the nitrilase activity yields in all recombinant strains were significant (see Table 1). The nitrilase from G. moniliformis exhibited a high preference for benzonitrile, but the activities of the other two enzymes studied here were two orders of magnitude higher for phenylacetonitrile than for benzonitrile.

Aromatic nitrilase from Gibberella moniliformis

Fig. 1 Table 1 5

The strain expressing the nit gene from G. moniliformis had approx. 10 times higher activity with benzonitrile than with phenylacetonitrile. Therefore, according to the classification work of [START_REF] Kobayashi | Versatile nitrilases: nitrile-hydrolysing enzymes[END_REF], the enzyme from this fungus was designated an aromatic nitrilase.

According to a mass spectrometric analysis of the tryptic fragments of two nitrilases from Fusarium solani strains IMI16840 and O1, these enzymes exhibited an amino acid sequence of high homology to the nitrilase from G. moniliformis (Vejvoda et al. 2010). These nitrilases from the Fusarium genus were also aromatic nitrilases. Their yields in the wild type producers of F. solani (1500 -3000 U l -1 with benzonitrile; Vejvoda et al. 2008Vejvoda et al. , 2010) ) were higher compared to E. coli expressing the nit gene from G. moniliformis (Table 1). However, production of the nitrilases in F. solani has been optimized by using a two-stage cultivation. Thus the heterologous production of the presumably highly similar enzyme from G. moniliformis was less laborious and required shorter cultivation times (20 h and 68-72 h for the heterologous and wild type strain, respectively).

A distantly related aromatic nitrilase from Aspergillus niger K10 was expressed in the wild type strain with a yield of approx. 100 U l -1 [START_REF] Kaplan | Purification and characterization of a nitrilase from Aspergillus niger K10[END_REF], which was increased to approx. 500 U l -1 by using an optimized heterologous expression protocol (IPTG concentration, time of induction, temperature shift after induction etc.; O. Kaplan, unpublished data). It is reasonable to expect that modifying these parameters will also be helpful in optimizing the expression of the G. moniliformis recombinant nitrilase.

Arylacetonitrilases from Aspergillus niger and Neurospora crassa

The activity yields of recombinant nitrilases from A. niger and N. crassa (over 2500 U l -1 for phenylacetonitrile) were in accordance with their high expression levels. The activities of these enzymes for benzonitrile were approx. 100 times lower. Members of two nitrilase subclassesarylacetonitrilases and aliphatic nitrilases -readily hydrolyze phenylacetonitrile (O'Reilly and Turner 2003) but the latter, such as the aliphatic nitrilase from Rhodococcus rhodochrous K22 [START_REF] Kobayashi | Purification and characterization of a novel nitrilase of Rhodococcus rhodochrous K22 that acts on aliphatic nitriles[END_REF], also hydrolyzed benzonitrile at comparable rates. Thus the new fungal enzymes appear to be arylacetonitrilases which have so far only been reported in bacteria (Thuku et al. 2009) but, as far as we know, not in filamentous fungi.

Conclusion

We confirmed that the E. coli expression system used by ourselves is suitable for a number of recombinant nitrilases from filamentous fungi. It enabled nitrilases from the genera Gibberella (aromatic nitrilase) and Neurospora (arylacetonitrilase) to be expressed for the first time. Another new enzyme of the latter type was found in the Aspergillus genus, which seems to be an abundant source of nitrilases with varying substrate specificities. The ongoing purification and characterization of these enzymes will indicate the areas where they can potentially be used as biocatalysts. E. coli BL21-Gold (DE3) strains OK103 through OK105 were grown in 50-ml Falcon tubes with 10 ml of LB broth with 50 µg kanamycin ml -1 . After 3.5 h of cultivation at 25 °C, the expression of nitrilase was induced with 0.5 mM IPTG. Cells were harvested after a further 17 h and assayed for nitrilase activity with benzonitrile or phenylacetonitrile. Activities for preferential substrates are shown.

  Thuku RN, Brady D, Benedik MJ, Sewell BT (2009) Microbial nitrilases: versatile, spiral forming, industrial enzymes. J Appl Microbiol 106: 703-727 Vejvoda V, Kaplan O, Bezouška K, Pompach P, Šulc M, Cantarella M, Benada O, Uhnáková B, Rinágelová A, Lutz-Wahl S, Fischer L, Křen V, Martínková L (2008) Purification and characterization of a nitrilase from Fusarium solani O1. J Mol Catal B-Enzym 50: 99-106. Vejvoda V, Kubáč D, Davidová A., Kaplan O, Šulc M, Šveda O, Chaloupková R, Martínková L (2010) Purification and characterization of nitrilase from Fusarium solani IMI196840. Process Biochem 45: 1115-1120 Zhu DM, Mukherjee C, Yang Y, Rios BE, Gallagher DT, Smith NN, Biehl ER, Hua L (2008) A new nitrilase from Bradyrhizobium japonicum USDA 110 -Gene cloning, biochemical characterization and substrate specificity. J Biotechnol 133: 327-333

Fig. 1

 1 Fig.1Cell-free extracts obtained by cell sonication and removal of cell debris at 13,000 g and 4 °C

Table 1

 1 Nitrilase activity of recombinant Escherichia coli strains expressing nit genes

	Strain	Gene source	Total nitrilase activity
			(U L -1 culture)
	OK103	Neurospora crassa	2678 ± 582 (phenylacetonitrile) a
	OK104	Gibberella moniliformis	390 ± 22 (benzonitrile) b
	OK105	Aspergillus niger	2512 ± 217 (phenylacetonitrile) a
	a means of three independent experiments
	a means of two independent experiments

Acknowledgements

. Financial support via projects IAA500200708 (Grant Agency of the Academy of Sciences of the Czech Republic), LC06010, OC09046 (Ministry of Education of the Czech Republic), European Cooperation in Science and Technology (COST) Action CM0701 (short-term scientific mission fellowships COST-STSM-CM0701-4765 and -4766 to A. Malandra), FT-TA5/043 (Ministry of Industry and Trade of the Czech Republic), 305/09/H008 (Czech Science Foundation) and Institutional Research Concept AV0Z50200510 (Institute of Microbiology) is gratefully acknowledged.


Mário S Alvim

Miguel E Andrés

Konstantinos Chatzikokolakis

Pierpaolo Degano

Catuscia Palamidessi

Differential Privacy: on the trade-off between Utility and Information Leakage ⋆

Differential privacy is a notion of privacy that has become very popular in the database community. Roughly, the idea is that a randomized query mechanism provides sufficient privacy protection if the ratio between the probabilities that two adjacent datasets give the same answer is bound by e ǫ . In the field of information flow there is a similar concern for controlling information leakage, i.e. limiting the possibility of inferring the secret information from the observables. In recent years, researchers have proposed to quantify the leakage in terms of min-entropy leakage, a concept strictly related to the Bayes risk. In this paper, we show how to model the query system in terms of an informationtheoretic channel, and we compare the notion of differential privacy with that of min-entropy leakage. We show that differential privacy implies a bound on the min-entropy leakage, but not vice-versa. Furthermore, we show that our bound is tight. Then, we consider the utility of the randomization mechanism, which represents how close the randomized answers are to the real ones, in average. We show that the notion of differential privacy implies a bound on utility, also tight, and we propose a method that under certain conditions builds an optimal randomization mechanism, i.e. a mechanism which provides the best utility while guaranteeing ǫ-differential privacy.

Introduction

The area of statistical databases has been one of the first communities to consider the issues related to the protection of information. Already some decades ago, Dalenius [START_REF] Dalenius | Towards a methodology for statistical disclosure control[END_REF] proposed a famous "ad omnia" privacy desideratum: nothing about an individual should be learnable from the database that could not be learned without access to the database. Differential privacy. Dalenius' property is too strong to be useful in practice: it has been shown by Dwork [2] that no useful database can provide it. In replacement, Dwork has proposed the notion of differential privacy, which has had an extraordinary impact in the community. Intuitively, such notion is based on the idea that the presence or the absence of an individual in the database, or its particular value, should not affect in a significant way the probability of obtaining a certain answer for a given query [START_REF] Dwork | Differential privacy[END_REF][START_REF] Dwork | Differential privacy in new settings[END_REF][START_REF] Dwork | A firm foundation for private data analysis[END_REF][START_REF] Dwork | Differential privacy and robust statistics[END_REF].

Note that one of the important characteristics of differential privacy is that it abstracts away from the attacker's auxiliary information. The attacker might possess information about the database from external means, which could allow him to infer an individual's secret. Differential privacy ensures that no extra information can be obtained because of the individual's presence (or its particular value) in the database.

Dwork has also studied a technique to create an ǫ-differential private mechanism from an arbitrary numerical query. This is achieved by adding random noise to the result of the query, drawn from a Laplacian distribution with variance depending on ǫ and the query's sensitivity, i.e. the maximal difference of the query between any neighbour databases [START_REF] Dwork | A firm foundation for private data analysis[END_REF].

Quantitative information flow. The problem of preventing the leakage of secret information has been a pressing concern also in the area of software systems, and has motivated a very active line of research called secure information flow. In this field, similarly to the case of privacy, the goal at the beginning was ambitious: to ensure non-interference, which means complete lack of leakage. But, as for Dalenius' notion of privacy, non-interference is too strong for being obtained in practice, and the community has started exploring weaker notions. Some of the most popular approaches are quantitative; they do not provide a yes-or-no answer but instead try to quantify the amount of leakage using techniques from information theory. See for instance [START_REF] Clark | Quantitative analysis of the leakage of confidential data[END_REF][START_REF] Clark | Quantitative information flow, relations and polymorphic types[END_REF][START_REF] Clarkson | Belief in information flow[END_REF][START_REF] Köpf | An information-theoretic model for adaptive side-channel attacks[END_REF][START_REF] Malacaria | Assessing security threats of looping constructs[END_REF][START_REF] Malacaria | Lagrange multipliers and maximum information leakage in different observational models[END_REF][START_REF] Smith | On the foundations of quantitative information flow[END_REF].

The various approaches in the literature mainly differ on the underlying notion of entropy. Each entropy is related to the type of attacker we want to model, and to the way we measure its success (see [START_REF] Köpf | An information-theoretic model for adaptive side-channel attacks[END_REF] for an illuminating discussion of this relation). The most widely used is Shannon entropy [START_REF] Shannon | A mathematical theory of communication[END_REF], which models an adversary trying to find out the secret x by asking questions of the form "does x belong to a set S?". Shannon entropy is precisely the average number of questions necessary to find out the exact value of x with an optimal strategy (i.e. an optimal choice of the S's). The other most popular notion of entropy in this area is the min-entropy, proposed by Rényi [START_REF] Rényi | On Measures of Entropy and Information[END_REF]. The corresponding notion of attack is a single try of the form "is x equal to value v?". Min-entropy is precisely the logarithm of the probability of guessing the true value with the optimal strategy, which consists, of course, in selecting the v with the highest probability. It is worth noting that the conditional min-entropy, representing the a posteriori probability of success, is the converse of the Bayes risk [START_REF] Cover | Elements of Information Theory[END_REF]. Approaches based on min-entropy include [START_REF] Smith | On the foundations of quantitative information flow[END_REF][START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF] while the Bayes risk has been used as a measure of information leakage in [START_REF] Braun | Compositional methods for informationhiding[END_REF][START_REF] Chatzikokolakis | On the Bayes risk in informationhiding protocols[END_REF].

In this paper, we focus on the approach based on min-entropy. As it is typical in the areas of both quantitative information flow and differential privacy [START_REF] Kasiviswanathan | A note on differential privacy: Defining resistance to arbitrary side information[END_REF][START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF], we model the attacker's side information as a prior distribution on the set of all databases. In our results we abstract from the side information in the sense that we prove them for all prior distributions. Note that an interesting property of min-entropy leakage is that it is maximized in the case of a uniform prior [START_REF] Smith | On the foundations of quantitative information flow[END_REF][START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF]. The intuition behind this is that the leakage is maximized when the attacker's initial uncertainty is high, so there is a lot to be learned. The more information the attacker has to begin with, the less it remains to be leaked.

Goal of the paper

The first goal of this paper is to explore the relation between differential privacy and quantitative information flow. First, we address the problem of characterizing the protection that differential privacy provides with respect to information leakage. Then, we consider the problem of the utility, that is the relation between the reported answer and the true answer. Clearly, a purely random result is useless, the reported answer is useful only if it provides information about the real one. It is therefore interesting to quantify the utility of the system and explore ways to improve it while preserving privacy. We attack this problem by considering the possible structure that the query induces on the true answers.

Contribution. The main contributions of this paper are the following:

-We propose an information-theoretic framework to reason about both information leakage and utility. -We prove that ǫ-differential privacy implies a bound on the information leakage.

The bound is tight and holds for all prior distributions. -We prove that ǫ-differential privacy implies a bound on the utility. We prove that, under certain conditions, the bound is tight and holds for all prior distributions. -We identify a method that, under certain conditions, constructs the randomization mechanisms which maximizes utility while providing ǫ-differential privacy.

Plan of the paper. The next section introduces some necessary background notions. Section 3 proposes an information-theoretic view of the database query systems, and of its decomposition in terms of the query and of the randomization mechanisms. Section 4 shows that differential privacy implies a bound on the min-entropy leakage, and that the bound is tight. Section 5 shows that differential privacy implies a bound on the utility, and that under certain conditions the bound is tight. Furthermore it shows how to construct an optimal randomization mechanism. Section 6 discusses related work, and Section 7 concludes. The proofs of the results are in the appendix.

Background

This section recalls some basic notions on differential privacy and information theory.

Differential privacy

The idea of differential privacy is that a randomized query provides sufficient privacy protection if two databases differing on a single row produce an answer with similar probabilities, i.e. probabilities whose ratio is bounded by e ǫ for a given ǫ ≥ 0. More precisely:

Definition 1 ([4]).

A randomized function K satisfies ǫ-differential privacy if for all of data sets D ′ and D ′′ differing on at most one row, and all S ⊆ Range(K),

P r[K(D ′ ) ∈ S] ≤ e ǫ × P r[K(D ′′ ) ∈ S] (1)

Information theory and interpretation in terms of attacks

In the following, X, Y denote two discrete random variables with carriers X = {x 0 , . . . , x n-1 }, Y = {y 0 , . . . , y m-1 }, and probability distributions p X (•), p Y (•), respectively. An information-theoretic channel is constituted of an input X, an output Y , and the matrix of conditional probabilities p Y |X (• | •), where p Y |X (y | x) represent the probability that Y is y given that X is x. We shall omit the subscripts on the probabilities when they are clear from the context.

Min-entropy.

In [START_REF] Rényi | On Measures of Entropy and Information[END_REF], Rényi introduced a one-parameter family of entropy measures, intended as a generalization of Shannon entropy. The Rényi entropy of order α (α > 0, α = 1) of a random variable X is defined as

H α (X) = 1 1-α log 2 x ∈ X p(x) α .
We are particularly interested in the limit of H α as α approaches ∞. This is called minentropy. It can be proven that H ∞ (X)

def = lim α→∞ H α (X) = -log 2 max x∈X p(x).
Rényi also defined the α-generalization of other information-theoretic notions, like the Kullback-Leibler divergence. However, he did not define the α-generalization of the conditional entropy, and there is no agreement on what it should be. For the case α = ∞, we adopt here the definition proposed in [START_REF] Dodis | Fuzzy extractors: How to generate strong keys from biometrics and other noisy data[END_REF]:

H ∞ (X | Y ) = -log 2 y∈Y p(y) max x∈X p(x | y) (2)
We can now define the min-entropy leakage as

I ∞ = H ∞ (X) -H ∞ (X | Y ).
The worst-case leakage is taken by maximising over all input distributions (recall that the input distribution models the attacker's side information):

C ∞ = max pX (•) I ∞ (X; Y ).
It has been proven in [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF] that C ∞ is obtained at the uniform distribution, and that it is equal to the sum of the maxima of each column in the channel matrix, i.e.,

C ∞ = y ∈ Y max x ∈ X p(y | x).
Interpretation in terms of attacks. Min-entropy can be related to a model of adversary who is allowed to ask exactly one question of the form "is X = x?" (one-try attack). More precisely, H ∞ (X) represents the (logarithm of the inverse of the) probability of success for this kind of attacks with the best strategy, which consists, of course, in choosing the x with the maximum probability.

The conditional min-entropy H ∞ (X | Y ) represents (the logarithm of the inverse of) the probability that the same kind of adversary succeeds in guessing the value of X a posteriori, i.e. after observing the result of Y . The complement of this probability is also known as probability of error or Bayes risk. Since in general X and Y are correlated, observing Y increases the probability of success. Indeed we can prove formally that H ∞ (X | Y ) ≤ H ∞ (X), with equality if and only if X and Y are independent. The min-entropy leakage I ∞ (X; Y ) = H ∞ (X) -H ∞ (X|Y ) corresponds to the ratio between the probabilities of success a priori and a posteriori, which is a natural notion of leakage. Note that it is always the case that I ∞ (X; Y ) ≥ 0, which seems desirable for a good notion of leakage.

A model of utility and privacy for statistical databases

In this section we present a model of statistical queries on databases, where noise is carefully added to protect privacy and, in general, the reported answer to a query does not need to correspond to the real one. In this model, the notion of information leakage can be used to measure the amount of information that an attacker can learn about the database by posting queries and analysing their (reported) answers. Moreover, the model allows us to quantify the utility of the query, that is, how much information about the real answer can be obtained from the reported one. This model will serve as the basis for exploring the relation between differential privacy and information flow.

We fix a finite set Ind = {1, 2, . . . , u} of u individuals participating in the database. In addition, we fix a finite set V al = {v 1 ,v 2 , . . . ,v v }, representing the set of (v different) possible values for the sensitive attribute of each individual (e.g. disease-name in a medical database) 1 . Note that the absence of an individual from the database, if allowed, can be modeled with a special value in V al. As usual in the area of differential privacy [START_REF] Nissim | Smooth sensitivity and sampling in private data analysis[END_REF], we model a database as a u-tuple D = {d 0 , . . . , d u-1 } where each d i ∈ Val is the value of the corresponding individual. The set of all databases is X = Val u . Two databases D, D ′ are adjacent, written D ∼ D ′ iff they differ for the value of exactly one individual. Let K be a randomized function from X to Z, where Z = Range(K) (see Figure 1). This function can be modeled by a channel with input and output alphabets X , Z respectively. This channel can be specified as usual by a matrix of conditional probabilities p Z|X (•|•). We also denote by X, Z the random variables modeling the input and output of the channel. The definition of differential privacy can be directly expressed as a property of the channel: it satisfies ǫ-differential privacy iff p(z|x) ≤ e ǫ p(z|x ′ ) for all z ∈ Z, x, x ′ ∈ X with x ∼ x ′ Intuitively, the correlation between X and Z measures how much information about the complete database the attacker can obtain by observing the reported answer. We will refer to this correlation as the leakage of the channel, denoted by L(X, Z). In Section 4 we discuss how this leakage can be quantified, using notions from information theory, and we study the behavior of the leakage for differentially private queries.

We then introduce a random variable Y modeling the true answer to the query f , ranging over Y = Range(f ). The correlation between Y and Z measures how much we can learn about the real answer from the reported one. We will refer to this correlation as the utility of the channel, denoted by U(Y, Z). In Section 5 we discuss in detail how utility can be quantified, and we investigate how to construct a randomization mechanism, i.e. a way of adding noise to the query outputs, so that utility is maximized while preserving differential privacy.

In practice, the randomization mechanism is often oblivious, meaning that the reported answer Z only depends on the real answer Y and not on the database X. In this case, the randomized function K, seen as a channel, can be decomposed into two parts: a channel modeling the query f , and a channel modeling the oblivious randomization Leakage about an individual. As already discussed, L(X, Z) can be used to quantify the amount of information about the whole database that is leaked to the attacker. However, protecting the database as a whole is not the main goal of differential privacy. Indeed, some information is allowed by design to be revealed, otherwise the query would not be useful. Instead, differential privacy aims at protecting the value of each individual. Although L(X, Z) is a good measure of the overall privacy of the system, we might be interested in measuring how much information about a single individual is leaked.

To quantify this leakage, we assume that the values of all other individuals are already known, thus the only remaining information concerns the individual of interest. Then we define smaller channels, where only the information of a specific individual varies. Let D -∈ Val u-1 be a (u -1)-tuple with the values of all individuals except the one of interest. We create a channel K D -whose input alphabet is the set of all databases in which the u -1 other individuals have the same values as in D -. Intuitively, the information leakage of this channel measures how much information about one particular individual the attacker can learn if the values of all others are known to be D -. This leakage is studied in Section 4.1.

Leakage

As discussed in the previous section, the correlation L(X, Z) between X and Z measures the information that the attacker can learn about the database by observing the reported answers. In this section, we consider min-entropy leakage as a measure of this information, that is L(X, Z) = I ∞ (X; Z). We then investigate bounds on information leakage imposed by differential privacy. These bounds hold for any side information of the attacker, modelled as a prior distribution on the inputs of the channel.

Our first result shows that the min-entropy leakage of a randomized function K is bounded by a quantity depending on ǫ, the numbers u, v of individuals and values respectively. We assume that v ≥ 2.

Theorem 1.

If K provides ǫ-differential privacy then for all input distributions, the min-entropy leakage associated to K is bounded from above as follows:

I ∞ (X; Z) ≤ u log 2 v e ǫ (v -1 + e ǫ )
Fig. 3. Graphs of B(u, v, ǫ) for u=100 and v=2 (lowest line), v=10 (intermediate line), and v = 100 (highest line), respectively.

Note that this bound

B(u, v, ǫ) = u log 2 v e ǫ (v-1+e ǫ )
is a continuous function in ǫ, has value 0 when ǫ = 0, and converges to u log 2 v as ǫ approaches infinity. Figure 3 shows the growth of B(u, v, ǫ) along with ǫ, for various fixed values of u and v.

The following result shows that the bound B(u, v, ǫ) is tight. Proposition 1. For every u, v, and ǫ there exists a randomized function K which provides ǫ-differential privacy and whose minentropy leakage is I ∞ (X; Z) = B(u, v, ǫ) for the uniform input distribution. u,v,ǫ) is guaranteed to be reached with the uniform input distribution. We know from the literature [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF][START_REF] Smith | On the foundations of quantitative information flow[END_REF] that the I ∞ of a given matrix has its maximum in correspondence of the uniform input distribution, although it may not be the only case.

The construction of the matrix for Proposition 1 gives a square matrix of dimension v u × v u . Often, however, the range of K is fixed, as it is usually related to the possible answers to the query f . Hence it is natural to consider the scenario in which we are given a number r < v u , and want to consider only those K's whose range has cardinality at most r. In this restricted setting, we could find a better bound than the one given by Theorem 1, as the following proposition shows. Proposition 2. Let K be a randomized function and let r = |Range(K)|. If K provides ǫ-differential privacy then for all input distributions, the min-entropy leakage associated to K is bounded from above as follows:

0 1 1 1 1 2 2 2 2 ab 1 0 1 2 2 1 2 1 2 ac 1 1 0 2 2 2 1 2 1 ba 1 2 2 0 1 1 1 2 2 ca 1 2 2 1 0 2 2 1 1 bb 2 1 2 1 2 0 1 1 2 bc 2 2 1 1 2 1 0 2 1 cb 2 1 2 2 1 1 2 0 1 cc 2 2 1 2 1 2 1 1 0 (b)
I ∞ (X; Z) ≤ log 2 r (e ǫ ) u (v -1 + e ǫ ) ℓ -(e ǫ ) ℓ + (e ǫ ) u
where ℓ = ⌊log v r⌋.

Note that this bound can be much smaller than the one provided by Theorem 1. For instance, if r = v this bound becomes:

log 2 v (e ǫ ) u v -1 + (e ǫ ) u
which for large values of u is much smaller than B(u, v, ǫ). In particular, for v = 2 and u approaching infinity, this bound approaches 1, while B(u, v, ǫ) approaches infinity.

Let us clarify that there is no contradiction with the fact that the bound B(u, v, ǫ) is strict: indeed it is strict when we are free to choose the range, but here we fix the dimension of the range.

Finally, note that the above bounds do not hold in the opposite direction. Since min-entropy averages over all observations, low probability observations affect it only slightly. Thus, by introducing an observation with a negligible probability for one user, and zero probability for some other user, we could have a channel with arbitrarily low min-entropy leakage but which does not satisfy differential privacy for any ǫ.

Measuring the leakage about an individual

As discussed in Section 3, the main goal of differential privacy is not to protect information about the complete database, but about each individual. To capture the leakage about a certain individual, we start from a tuple D -∈ Val u-1 containing the given (and known) values of all other u-1 individuals. Then we create a channel whose input X D - ranges over all databases where the values of the other individuals are exactly those of D -and only the value of the selected individual varies. Intuitively, I ∞ (X D -; Z) measures the leakage about the individual's value where all other values are known to be as in D -. As all these databases are adjacent, differential privacy provides a stronger bound for this leakage. Theorem 2. If K provides ǫ-differential privacy then for all D -∈ Val u-1 and for all input distributions, the min-entropy leakage about an individual is bounded from above as follows:

I ∞ (X D -; Z) ≤ log 2 e ǫ
Note that this bound is stronger than the one of Theorem 1. In particular, it depends only on ǫ and not on u, v.

Utility

As discussed in Section 3, the utility of a randomized function K is the correlation between the real answers Y for a query and the reported answers Z. In this section we analyze the utility U(Y, Z) using the classic notion of utility functions (see for instance [START_REF] Bernardo | Bayesian Theory[END_REF]).

For our analysis we assume an oblivious randomization mechanism. As discussed in Section 3, in this case the system can be decomposed into two channels, and the utility becomes a property of the channel associated to the randomization mechanism H which maps the real answer y ∈ Y into a reported answer z ∈ Z according to given probability distributions p Z|Y (•|•). However, the user does not necessarily take z as her guess for the real answer, since she can use some Bayesian post-processing to maximize the probability of success, i.e. a right guess. Thus for each reported answer z the user can remap her guess to a value y ′ ∈ Y according to a remapping function ρ(z) : Z → Y, that maximizes her expected gain. For each pair (y, y ′ ), with y ∈ Y, y ′ = ρ(y), there is an associated value given by a gain (or utility) function g(y, y ′ ) that represents a score of how useful it is for the user to guess the value y ′ as the answer when the real answer is y.

It is natural to define the global utility of the mechanism H as the expected gain:

U(Y, Z) = y p(y) y ′ p(y ′ |y)g(y, y ′ ) (3)
where p(y) is the prior probability of real answer y, and p(y ′ |y) is the probability of user guessing y ′ when the real answer is y.

We can derive the following characterization of the utility. We use δ x to represent the probability distribution which has value 1 on x and 0 elsewhere.

U(Y, Z) = y p(y)
y ′ δ ρ(z) (y ′ )g(y, y ′ ) = y,z p(y, z) y ′ δ ρ(z) (y ′ )g(y, y ′ ) = y,z
p(y, z)g(y, ρ(z))

A very common utility function is the binary gain function, which is defined as g bin (y, y ′ ) = 1 if y = y ′ and g bin (y, y ′ ) = 0 if y = y ′ . The rationale behind this function is that, when the answer domain does not have a notion of distance, then the wrong answers are all equally bad. Hence the gain is total when we guess the exact answer, and is 0 for all other guesses. Note that if the answer domain is equipped with a notion of distance, then the gain function could take into account the proximity of the reported answer to the real one, the idea being that a close answer, even if wrong, is better than a distant one.

In this paper we do not assume a notion of distance, and we will focus on the binary case. The use of binary utility functions in the context of differential privacy was also investigated in [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] 2 .

By substituting g with g bin in the above formula we obtain:

U(Y, Z) = y,z p(y, z)δ y (ρ(z)) (4)
which tells us that the expected utility is the greatest when ρ(z) = y is chosen to maximize p(y, z). Assuming that the user chooses such a maximizing remapping, we have:

U(Y, Z) = z max y p(y, z) (5)
This corresponds to the converse of the Bayes risk, and it is closely related to the conditional min-entropy and to the min-entropy leakage:

H ∞ (Y |Z) = -log 2 U(Y, Z) I ∞ (Y ; Z) = H ∞ (X) + log 2 U(Y, Z)

A bound on the utility

In this section we show that the fact that K provides ǫ-differential privacy induces a bound on the utility. We start by extending the adjacency relation ∼ from the datasets X to the answers Y. Intuitively, the function f associated to the query determines a partition on the set of all databases (X , i.e. Val u ), and we say that two classes are adjacent if they contain an adjacent pair. More formally:

Definition 2. Given y, y ′ ∈ Y, with y = y ′ , we say that y and y ′ are adjacent (notation

y ∼ y ′ ), iff there exist D, D ′ ∈ Val u with D ∼ D ′ such that y = f (D) and y ′ = f (D ′ ).
Since ∼ is symmetric on databases, it is also symmetric on Y, therefore also (Y, ∼) forms an undirected graph. Definition 3. The distance dist between two elements y, y ′ ∈ Y is the length of the minimum path from y to y ′ . For a given natural number d, we define Border d (y) as the set of elements at distance d from y:

Border d (y) = {y ′ | dist (y, y ′ ) = d}
We recall that a graph automorphism is a permutation of its vertices that preserves its edges. If σ is a permutation of S then an orbit of σ is a set of the form {σ i (s) | i ∈ N} where s ∈ S. A permutation has a single orbit iff {σ i (s)|i ∈ N} = S for all s ∈ S.

The next theorem provides a bound on the utility in the case in which (Y, ∼) admits a graph automorphism with a single orbit. Note that this condition implies that the graph has a very regular structure; in particular, all nodes must have the same number of incident edges. Examples of such graphs are rings and cliques (but they are not the only cases). Theorem 3. Let H be a randomization mechanism for the randomized function K and the query f , and assume that K provides ǫ-differential privacy. Assume that (Y, ∼) admits a graph automorphism with a single orbit. Furthermore, assume that there exists a natural number c and an element y ∈ Y such that, for every natural number d > 0,

either |Border d (y)| = 0 or |Border d (y)| ≥ c. Then U(X, Y ) ≤ (e ǫ ) n (1 -e ǫ ) (e ǫ ) n (1 -e ǫ ) + c (1 -(e ǫ ) n )
where n is the maximum distance from y in Y.

The bound provided by the above theorem is strict in the sense that for every ǫ and Y there exist an adjacency relation ∼ for which we can construct a randomization mechanism H that provides ǫ-differential privacy and whose utility achieves the bound of Theorem 3. This randomization mechanism is therefore optimal, in the sense that it provides the maximum possible utility for the given ǫ. Intuitively, the condition on ∼ is that |Border d (y)| must be exactly c or 0 for every d > 0. In the next section we will define formally such an optimal randomization mechanism, and give examples of queries that determine a relation ∼ satisfying the condition.

Constructing an optimal randomization mechanism

Assume f : X → Y, and consider the graph structure (Y, ∼) determined by f . Let n be the maximum distance between two nodes in the graph and let c be an integer. We construct the matrix M of conditional probabilities associated to H as follows. For every column z ∈ Z and every row y ∈ Y, define:

p Z|Y (z|y) = α/(e ǫ ) d where d = dist (y, z) and α = (e ǫ ) n (1-e ǫ ) (e ǫ ) n (1-e ǫ )+c (1-(e ǫ ) n ) (6)
The following theorem guarantees that the randomization mechanism H defined above is well defined and optimal, under certain conditions. Then, for such c, the definition in ( 6) determines a legal channel matrix for H, i.e., for each y ∈ Y, p Z|Y (•|y) is a probability distribution. Furthermore, the composition K of f and H provides ǫ-differential privacy. Finally, H is optimal in the sense that it maximizes utility when the distribution of Y is uniform.

The conditions for the construction of the optimal matrix are strong, but there are some interesting cases in which they are satisfied. Depending on the degree of connectivity c, we can have several different cases whose extremes are:

-(Y, ∼) is a ring, i.e. every element has exactly two adjacent elements. This is similar to the case of the counting queries considered in [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF], with the difference that our "counting" is in arithmetic modulo |Y|. -(Y, ∼) is a clique, i.e. every element has exactly |Y| -1 adjacent elements.

p Z|Y (z|y) = 2 α (e ǫ ) n if dist (y, z) = n
For all the other elements the definition remains as in (6).

Remark 2. Note that our method can be applied also when the conditions of Theorem 4 are not met: We can always add "artificial" adjacencies to the graph structure so to meet those conditions. Namely, for computing the distance in (6) we use, instead of (Y, ∼), a structure (Y, ∼ ′ ) which satisfies the conditions of Theorem 4, and such that ∼ ⊆ ∼ ′ . Naturally, the matrix constructed in this way provides ǫ-differential privacy, but in general is not optimal. Of course, the smaller ∼ ′ is, the higher is the utility. The matrices generated by our algorithm above can be very different, depending on the value of c. The next two examples illustrate queries that give rise to the clique and to the ring structures, and show the corresponding matrices.

Example 2. Consider a database with electoral information where rows corresponds to voters. Let us assume, for simplicity, that each row contains only three fields:

-ID: a unique (anonymized) identifier assigned to each voter; -CITY: the name of the city where the user voted; -CANDIDATE: the name of the candidate the user voted for.

Consider the query "What is the city with the greatest number of votes for a given candidate?". For this query the binary function is a natural choice for the gain function: only the right city gives some gain, and any wrong answer is just as bad as any other.

It is easy to see that every two answers are neighbors, i.e. the graph structure of the answers is a clique.

Consider the case where CITY={A,B,C,D,E,F} and assume for simplicity that there is a unique answer for the query, i.e., there are no two cities with exactly the same number of individuals voting for a given candidate. Table 1 shows two alternative mechanisms providing ǫ-differential privacy (with ǫ = log 2). The first one, M 1 , is based on the truncated geometric mechanism method used in [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] for counting queries (here extended to the case where every two answers are neighbors). The second mechanism, M 2 , is the one we propose in this paper.

Taking the input distribution, i.e. the distribution on Y , as the uniform distribution, it is easy to see that U(M 1 ) = 0.2243 < 0.2857 = U(M 2 ). Even for non-uniform distributions, our mechanism still provides better utility. For instance, for p(A) = p(F ) = 1/10 and p(B) = p(C) = p(D) = P (E) = 1/5, we have U(M 1 ) = 0.2412 < 0.2857 = U(M 2 ). This is not too surprising: the Laplacian method and the geometric mechanism work very well when the domain of answers is provided with a metric and the utility function takes into account the proximity of the reported answer to the real one. It also works well when (Y, ∼) has low connectivity, in particular in the cases of a ring and of a line. But in this example, we are not in these cases, because we are considering binary gain functions and high connectivity.

Example 3. Consider the same database as the previous example, but now assume a counting query of the form "What is the number of votes for candidate cand ?". It is easy to see that each answer has at most two neighbors. More precisely, the graph (a) M1: truncated structure on the answers is a line. For illustration purposes, let us assume that only 5 individuals have participated in the election. Table 2 shows two alternative mechanisms providing ǫ-differential privacy (ǫ = log 2): (a) the truncated geometric mechanism M 1 proposed in [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] and (b) the mechanism M 2 that we propose, where c = 2 and n = 3.

Note that in order to apply our method we have first to apply Remark 2 to transform the line into a ring, and then Remark 1 to handle the case of the elements at maximal distance from the diagonal. Le us consider the uniform prior distribution. We see that the utility of M 1 is higher than the utility of M 2 , in fact the first is 4/9 and the second is 4/11. This does not contradict our theorem, because our matrix is guaranteed to be optimal only in the case of a ring structure, not a line as we have in this example. If the structure were a ring, i.e. if the last row were adjacent to the first one, then M 1 would not provide ǫ-differential privacy. In case of a line as in this example, the truncated geometric mechanism has been proved optimal [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF].

Related work

As far as we know, the first work to investigate the relation between differential privacy and information-theoretic leakage for an individual was [START_REF] Alvim | Differential privacy versus quantitative information flow[END_REF]. In this work, a channel is relative to a given database x, and the channel inputs are all possible databases adjacent to x. Two bounds on leakage were presented, one for the Shannon entropy, and one for the min-entropy. The latter corresponds to Theorem 2 in this paper (note that [START_REF] Alvim | Differential privacy versus quantitative information flow[END_REF] is an unpublished report).

Barthe and Köpf [START_REF] Barthe | Information-theoretic bounds for differentially private mechanisms[END_REF] were the first to investigates the (more challenging) connection between differential privacy and the min-entropy leakage for the entire universe of possible databases. They consider only the hiding of the participation of individuals in a database, which corresponds to the case of v = 2 in our setting. They consider the "end-to-end differentially private mechanisms", which correspond to what we call K in our paper, and propose, like we do, to interpret them as information-theoretic channels. They provide a bound for the leakage, but point out that it is not tight in general, and show that there cannot be a domain-independent bound, by proving that for any number of individual u the optimal bound must be at least a certain expression f (u, ǫ). Finally, they show that the question of providing optimal upper bounds for the leakage of K in terms of rational functions of ǫ is decidable, and leave the actual function as an open question. In our work we used rather different techniques and found (independently) the same function f (u, ǫ) (the bound B(u, v, ǫ) in Theorem 1 for v = 2), but we proved that f (u, ǫ) is a bound, and therefore the optimal bound3 .

Clarkson and Schneider also considered differential privacy as a case study of their proposal for quantification of integrity [START_REF] Clarkson | Quantification of integrity[END_REF]. There, the authors analyzed database privacy conditions from the literature (such as differential privacy, k-anonymity, and ldiversity) using their framework for utility quantification. In particular, they studied the relationship between differential privacy and a notion of leakage (which is different from ours -in particular their definition is based on Shannon entropy) and they provided a tight bound on leakage.

Heusser and Malacaria [START_REF] Heusser | Applied quantitative information flow and statistical databases[END_REF] were among the first to explore the application of information-theoretic concepts to databases queries. They proposed to model database queries as programs, which allows for statical analysis of the information leaked by the query. However [START_REF] Heusser | Applied quantitative information flow and statistical databases[END_REF] did not attempt to relate information leakage to differential privacy.

In [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] the authors aimed at obtaining optimal-utility randomization mechanisms while preserving differential privacy. The authors proposed adding noise to the output of the query according to the geometric mechanism. Their framework is very interesting because it provides us with a general definition of utility for a randomization mechanism M that captures any possible side information and preference (defined as a loss function) the users of M may have. They proved that the geometric mechanism is optimal in the particular case of counting queries. Our results in Section 5 do not restrict to counting queries, however we only consider the case of binary loss function.

Conclusion and future work

An important question in statistical databases is how to deal with the trade-off between the privacy offered to the individuals participating in the database and the utility provided by the answers to the queries. In this work we proposed a model integrating the notions of privacy and utility in the scenario where differential-privacy is applied. We derived a strict bound on the information leakage of a randomized function satisfying ǫ-differential privacy and, in addition, we studied the utility of oblivious differential privacy mechanisms. We provided a way to optimize utility while guaranteeing differential privacy, in the case where a binary gain function is used to measure the utility of the answer to a query.

As future work, we plan to find bounds for more generic gain functions, possibly by using the Kantorovich metric to compare the a priori and a posteriori probability distributions on secrets.

H M

′ ∞ (A) = H M ∞ (A).
Proof. We first show that there exists an n × m matrix N and an injective total function ρ : A → B such that:

-N i,ρ(i) = max ρ(i) N for all i ∈ A, -N i,j = 0 for all j ∈ B\ρ(A) and all i ∈ A.

We iteratively construct ρ, N "column by column" via a sequence of approximating partial functions ρ s and matrices N s (0 ≤ s ≤ m).

-Initial step (s = 0). Define ρ 0 (i) = ⊥ for all i ∈ A and N 0 = M .

-

s th step (1 ≤ s ≤ m).
Let j be the s-th column and let i ∈ A be one of the rows containing the maximum value of column j in M , i.e. M i,j = max j M . There are two cases: 1. ρ s-1 (i) = ⊥: we define

ρ s = ρ s-1 ∪ {i → j} N s = N s-1 2. ρ s-1 (i) = k ∈ B: we define ρ s = ρ s-1 N s = N s-1 [j → k]
Since the first step assigns j in ρ s and the second zeroes the column j in N s , all unassigned columns B \ ρ m (A) must be zero in N m . We finish the construction by taking ρ to be the same as ρ m after assigning to each unassigned row one of the columns in B \ ρ m (A) (there are enough such columns since n ≤ m). We also take N = N m . Note that by construction N is a channel matrix.

Thus we get a matrix N and a function ρ : A → B which, by construction, is injective and satisfies N i,ρ(i) = max ρ(i) N for all i ∈ A, and N i,j = 0 for all j ∈ B\ρ(A) and all i ∈ A. Furthermore, N provides ǫ-differential privacy because each column is a linear combination of columns of M . It is also easy to see that

j max j N = j max j M , hence H N ∞ (A) = H M ∞ (A) (remember that A has the uni- form distribution).
Finally, we create our claimed matrix M ′ from N as follows: first, we eliminate all columns in B \ ρ(A). Note that all these columns are zero so the resulting matrix is a proper channel matrix, provides differential privacy and has the same conditional min-entropy. Finally, we rearrange the columns according to ρ. Note that the order of the columns is irrelevant, any permutation represents the same conditional probabilities thus the same channel. The resulting matrix M ′ is n × n and has all maxima in the diagonal.

Lemma 2. Let M be a channel with input and output alphabets A = B = Val u , and let ∼ be the adjacency relation on V al u defined in Section 3. Assume that the maximum value of each column is on the diagonal, that is M i,i = max i M for all i ∈ A. If M provides ǫ-differential privacy then we can construct a new channel matrix M ′ such that:

1. M ′ provides ǫ-differential privacy; 2. M ′ i,i = M ′ h,h for all i, h ∈ A i.e. all the elements of the diagonal are equal; 3.

M ′ i,i = max i M ′ for all i ∈ A; 4. H M ∞ (A) = H M ′ ∞ (A).
M ′ h,k = 1 n|B h,d(h,k) | i∈A j∈B i,d(h,k) M i,j
We first show that this is a well defined channel matrix, namely k∈B M ′ h,k = 1 for all h ∈ A. We have

k∈B M ′ h,k = k∈B 1 n|B h,d(h,k) | i∈A j∈B i,d(h,k) M i,j = 1 n i∈A k∈B 1 |B h,d(h,k) | j∈B i,d(h,k) M i,j
Let ∆ = {0, . . . , u}. Note that B = d∈∆ B h,d , and these sets are disjoint, so the summation over k ∈ B can be split as follows

= 1 n i∈A d∈∆ k∈B h,d 1 |B h,d | j∈B i,d M i,j = 1 n i∈A d∈∆ j∈B i,d M i,j k∈B h,d 1 |B h,d | as k∈B h,d 1 |B h,d | = 1, we obtain = 1 n i∈A d∈∆ j∈B i,d M i,j
and now the summations over j can be joined together

= 1 n i∈A j∈B M i,j = 1
We now show that the elements of the diagonal have the intended properties. First, we show that the elements of the diagonal are all the same. We have that B i,d(h,h) = B i,0 = {i} for all h ∈ A, and therefore:

M ′ h,h = 1 n i∈A M i,i
Then, we show that they are the maxima for each column. Note that |B i,d | = u d (v-1) d which is independent of i. We have:

M ′ h,k = 1 n|B h,d(h,k) | i∈A j∈B i,d(h,k) M i,j ≤ 1 n|B h,d(h,k) | i∈A j∈B i,d(h,k) M i,i
(M has maxima in the diag.)

= 1 n i∈A |B i,d(h,k) | |B h,d(h,k) | M i,i = 1 n i∈A M i,i = M ′ h,h
It easily follows that j max j M ′ = j max j M which implies that

H M ∞ (A) = H M ′ ∞ (A).
It remains to show that M ′ provides ǫ-differential privacy, namely that

M ′ h,k ≤ e ǫ M ′ h ′ ,k ∀h, h ′ , k ∈ A : h ∼ h ′ Since d(h, h ′ ) = 1
, by the triangular inequality we derive:

d(h ′ , k) -1 ≤ d(h, k) ≤ d(h ′ , k) + 1
Thus, there are exactly 3 possible cases:

1. d(h, k) = d(h ′ , k). The result is immediate since M ′ h,k = M ′ h ′ ,k . 2. d(h, k) = d(h ′ , k) -1. Define S i,j = {j ′ ∈ B i,d(i,j)+1 |j ′ ∼ j} Note that |S i,j | = (u -d(i, j))(v - 1
) (i and j are equal in u -d(i, j) elements, and we can change any of them in v -1 ways). The following holds:

M i,j ≤ e ǫ M i,j ′ ∀j ′ ∈ S i,j (diff. privacy) ⇒ (u -d(i, j))(v -1)M i,j ≤ e ǫ j ′ ∈Si,j M i,j ′ (sum of the above) ⇒ j∈B i,d(h,k) (u -d(h, k))(v -1)M i,j ≤ e ǫ j∈B i,d(h,k) j ′ ∈Si,j
M i,j ′ (sum over j)

Let d = d(h, k). Note that each j ′ ∈ B i,d+1 is contained in exactly d + 1 different sets S i,j , j ∈ B i,d . So the right-hand side above sums all elements of B i,d+1 , d + 1 times each. Thus we get

(u -d)(v -1) j∈B i,d M i,j ≤ e ǫ (d + 1) j∈B i,d+1 M i,j (7)
Finally, we have

M ′ h,k = 1 n|B h,d | i∈A j∈B i,d M i,j ≤ e ǫ 1 n u d (v -1) d d + 1 (u -d)(v -1) i∈A j∈B i,d+1 M i,j
(from [START_REF] Clark | Quantitative information flow, relations and polymorphic types[END_REF])

≤ e ǫ 1 n u d+1 (v -1) d+1 i∈A j∈B i,d+1 M i,j = e ǫ M ′ h ′ ,k 3. d(h, k) = d(h ′ , k) + 1. Symmetrical to the case d(h, k) = d(h ′ , k) -1.
We are now ready to prove our first main result.

Theorem 1.

If K provides ǫ-differential privacy then the min-entropy leakage associated to K is bounded from above as follows:

I ∞ (X; Z) ≤ u log 2 v e ǫ (v -1 + e ǫ )
Proof. Let us assume, without loss of generality, that |X | ≤ |Z| (if this is not the case, then we add enough zero columns, i.e. columns containing only 0's, so to match the number of rows. Note that adding zero columns does not change the min-entropy leakage).

For our proof we need a square matrix with all column maxima on the diagonal, and all equal. We obtain such a matrix by transforming the matrix associated to K as follows: first we apply Lemma 1 to it (with A = X and B = Z), and then we apply Lemma 2

The next proposition shows that the bound obtained in previous theorem is tight. Proposition 1. For every u, v, and ǫ there exists a randomized function K which provides ǫ-differential privacy and whose min-entropy leakage, for the uniform input distribution, is I ∞ (X; Z) = B(u, v, ǫ).

Proof. The adjacency relation in X determines a graph structure G X . Set Z = X and define the matrix of K as follows:

p K (z|x) = B(u, v, ǫ) (e ǫ ) d
where d is the distance between x and z in G X

It is easy to see that p K (•|x) is a probability distribution for every x, that K provides ǫ-differential privacy, and that I ∞ (X; Z) = B(u, v, ǫ).

We consider now the case in which |Range(K)| is bounded by a number smaller than v u .

In the following when we have a random variable X, and a matrix M with row indices in A X , we will use the notations H M ∞ (X) and I M ∞ (X) to represent the conditional min-entropy and leakage obtained by adding "dummy raws" to M , namely rows that extend the input domain of the corresponding channel so to match the input X, but which do not contribute to the computation of H M ′ ∞ (X). Note that it is easy to extend M this way: we only have to make sure that for each column j the value of each of these new rows is dominated by max j M ′ .

We will also use the notation ∼ u and ∼ ℓ to refer to the standard adjacency relations on Val u and Val ℓ , respectively. Lemma 3. Let K be a randomized function with input X, where X = Val Ind , providing ǫ-differential privacy. Asssume that r = |Range(K)| = v ℓ , for some ℓ < u. Let M be the matrix associated to K. Then it is possible to build a square matrix M ′ of size v ℓ × v ℓ , with row and column indices in A ⊆ X , and a binary relation ∼ ′ ⊆ A × A such that (A, ∼ ′ ) is isomorphic to (Val ℓ , ∼ ℓ ), and such that:

1. M ′ i,j ≤ (e ǫ ) u-l+d M ′ i,j for all i, j, k ∈ A, where d is the ∼ ′ -distance between j and k.

M ′

i,i = M ′ h,h for all i, h ∈ A, i.e. elements of the diagonal are all equal 3. M ′ i,i = max i M ′ for all i ∈ A, i.e. the diagonal contains the maximum values of the columns. [START_REF] Dwork | A firm foundation for private data analysis[END_REF]

. H M ′ ∞ (X) = H M ∞ (X).
Proof. We first apply a procedure similar to that of Lemma 1 to construct a square matrix of size v ℓ × v ℓ which has the maximum values of each column in the diagonal. (In this case we construct an injection from the columns to rows containing their maximum value, and we eliminate the rows that at the end are not associated to any column.) Then define ∼ ′ as the projection of ∼ u on Val ℓ . Note that point 1 in this lemma is satisfied by this definition of ∼ ′ . Finally, apply the procedure in Lemma 2 (on the structure (A, ∼ ′ )) to make all elements in the diagonal equal and maximal. Note that this procedure preserves the property in point 1, and conditional min-entropy. Hence H

M ′ ∞ (X) = H M ∞ (X).
Proposition 2. Let K be a randomized function and let r = |Range(K)|. If K provides ǫ-differential privacy then the min-entropy leakage associated to K is bounded from above as follows:

I ∞ (X; Z) ≤ log 2 r (e ǫ ) u (v -1 + e ǫ ) ℓ -(e ǫ ) ℓ + (e ǫ ) u
where ℓ = ⌊log v r⌋.

Proof. Assume first that r is of the form v ℓ . We transform the matrix M associated to K by applying Lemma 3, and let M ′ be the resulting matrix. Let us denote by α the value of every element in the diagonal of M ′ , i.e. α = M ′ i,i for every row i, and let us denote by Border ′ d (i) the border (Def 3) wrt ∼ ′ . Note that for every j ∈ Border ′ d (i) we have that M ′ i,i ≤ M ′ i,j (e ǫ ) u-ℓ+d , hence

M ′ i,j ≤ α (e ǫ ) u-ℓ+d
Furthermore each element j at ∼ ′ -distance d from i can be obtained by changing the value of d individuals in the ℓ-tuple representing i (remember that (A, ∼ ′ ) is isomorphic to (Val ℓ , sim ℓ )). We can choose those d individuals in ℓ d possible ways, and for each of these individuals we can change the value (with respect to the one in i) in v -1 possible ways. Therefore

|Border ′ d (i)| = ℓ d (v -1) d
Taking into account that for M ′ i,i we do not need to divide by (e ǫ ) u-ℓ+d , we obtain:

α + ℓ d=1 ℓ d (v -1) d α (e ǫ ) u-ℓ+d ≤ j M ′ i,j
Since each row represents a probability distribution, the elements of row i must sum up to 1. Hence:

α + u d=1 u d (v -1) d α (e ǫ ) u-ℓ+d ≤ 1 (9)
By performing some simple calculations, similar to those of the proof of Theorem 1, we obtain:

α ≤ (e ǫ ) u (v -1 + e ǫ ) ℓ -(e ǫ ) ℓ + (e ǫ ) u Therefore:

I M ′ ∞ (X) = H ∞ (X) -H M ′ ∞ (X) (by definition) = log 2 v u + log 2 v ℓ j=1 α 1 v u = log 2 v u + log 2 1 v u + log 2 (v ℓ α)
≤ log 2 v ℓ (e ǫ ) u (v -1 + e ǫ ) ℓ -(e ǫ ) ℓ + (e ǫ ) u (by ( 9) ) [START_REF] Malacaria | Assessing security threats of looping constructs[END_REF] Consider now the case in which r is not of the form v ℓ . Let ℓ be the maximum integer such that v ℓ < r, and let m = r -v ℓ . We transform the matrix M associated to K by collapsing the m columns with the smallest maxima into the m columns with highest maxima. Namely, let j 1 , j 2 , . . . , j m the indices of the columns which have the smallest maxima values, i.e. max jt M ≤ max j M for every column j = j 1 , j 2 , . . . , j m . Similarly, let k 1 , k 2 , . . . , k m be the indexes of the columns which have maxima values. Then, define

N = M [j 1 → k 1 ][j 2 → k 2 ] . . . [j m → k m ]
Finally, eliminate the m zero-ed columns to obtain a matrix with exactly v ℓ columns. It is easy to show that

I M ∞ (X) ≤ I N ∞ (X) r v ℓ
After transforming N into a matrix M ′ with the same min-entropy leakage as described in the first part of this proof, from [START_REF] Malacaria | Assessing security threats of looping constructs[END_REF] we conclude

I M ∞ (X) ≤ I M ′ ∞ (X) r v ℓ ≤ log 2
r (e ǫ ) u (v -1 + e ǫ ) ℓ -(e ǫ ) ℓ + (e ǫ ) u

We now turn our attention to the min-entropy leakage associated to an individual. Therefore:

H ∞ (A|B) ≥ H ∞(A) -ǫ log 2 e (11)
This gives us a bound on the min-entropy leakage:

I ∞ (A; B) = H ∞ (A) -H ∞ (A|B)
≤ ǫ log 2 e (by ( 11))

Theorem 2. If K provides ǫ-differential privacy then for all D -∈ Val u-1 the minentropy leakage about an individual is bounded from above as follows:

I ∞ (X D -; Z) ≤ log 2 e ǫ
Proof. By construction, the elements of X D -are all adjacent. Hence K D -respects an ǫ-ratio. Thus we are allowed to apply Lemma 4 (with X = X D -and K = K D -), which gives immediately the intended result.

Utility

In this part we prove the results on utility. We start with a lemma which plays a role analogous to Lemma 2, but for a different kind of graph structure: in this case, we require the graph to have an automorphism with a single orbit.

Lemma 5. Let M be the matrix of a channel with the same input and output alphabet A. Assume an adjacency relation ∼ on A such that the graph (A, ∼) has an automorphism σ with a single orbit. Assume that the maximum value of each column is on the diagonal, that is M i,i = max i M for all i ∈ A. If M provides ǫ-differential privacy then we can construct a new channel matrix M ′ such that:

Finally, we prove that

I M ′ ∞ (A) = I M ∞ (A). It is enough to prove that H M ′ ∞ (A) = H M ∞ (A). H M ′ ∞ (A) = n-1 h=0 M h,h = 1 n n-1 h=0 n-1 i=0 M σ i (h),σ i (h) (since {σ i (h)|0 ≤ i ≤ n -1} = A) = 1 n n-1 h=0 H M ∞ (A) (since M σ i (h),σ i (h) = max σ i (h) M ) = H M ∞ (A)
Theorem 3. Let H be a randomization mechanism for the randomized function K and the query f , and assume that K provides ǫ-differential privacy. Assume that (Y, ∼) admits a graph automorphism with a single orbit. Furthermore, assume that there exists a natural number c and an element y ∈ Y such that, for every natural number where n is the maximum distance from y in Y.

Proof. Consider the matrix M obtained by applying Lemma 1 to the matrix of H, and then Lemma 5 to the result of Lemma 1. Let us call α the value of the elements in the diagonal of M .

Let us take an element M i,i = α. For each element j ∈ Border d (M i,i ), the value of M i,j can be at most α e dǫ . Also, the elements of row i represent a probability distribution, so they sum up to 1. Hence we obtain:

Fig. 1 .

 1 Fig. 1.Randomized function K as a channel

Fig. 2 .

 2 Fig. 2. Leakage and utility for oblivious mechanisms

Example 1 .

 1 Assume that we are interested in the eye color of a certain population Ind = {Alice, Bob}. Let Val = {a, b, c} where a stands for absent (i.e. the null value), b stands for blue, and c stands for coal (black). We can represent each dataset with a tuple d 1 d 0 , where d 0 ∈ Val represents the eye color of Alice (cases d 0 = b and d 0 = c), or that Alice is not in the dataset (case d 0 = a). The value d 1 provides the same kind of information for Bob. Note that v = 3. Fig 4(a) represents the set X of all possible datasets and its adjacency relation. We now construct the matrix with input X which provides ǫ-differential privacy and has the highest min-entropy leakage. From the proof of Proposition 1, we know that each element of the matrix is of the form α e ǫ d , where α = v e ǫ (v-1+e ǫ ) = 3 e ǫ (2+e ǫ ) , and d is the graph-theoretic distance (in Fig 4(a)) between (the dataset of) the row which contains such element and (the dataset of) the row with the highest value in the same column. Fig 4(b) illustrates this matrix, where, for the sake of readability, each value a e ǫ d is represented simply by d. Note that the bound B(

  The datasets and their adjacency relation aa ab ac ba ca bb bc cb cc aa

Fig. 4 .

 4 Fig. 4. Universe and highest min-entropy leakage matrix giving ǫ-differential privacy for Example 1.

  y ′ p(y ′ |y)g(y, y ′ ) )p(y ′ |z) g(y, y ′ ) )δ ρ(z) (y ′ ) g(y, y ′ ) (by remap y ′ = ρ(z))

Theorem 4 .

 4 Let f : X → Y be a query and let ǫ ≥ 0. Assume that (Y, ∼) admits a graph automorphism with a single orbit, and that there exists c such that, for every y ∈ Y and every natural number d > 0, either |Border d (y)| = 0 or |Border d (y)| = c.

Remark 1 .

 1 Note that when we have a ring with an even number of nodes the conditions of Theorem 4 are almost met, except that |Border d (y)| = 2 for d < n, and |Border d (y)| = 1 for d = n, where n is the maximum distance between two nodes in Y. In this case, and if (e ǫ ) 2 ≥ 2, we can still construct a legal matrix by doubling the value of such elements. Namely, by defining

Proof.

  Let k, l ∈ Val u . Recall that dist (k, l) (distance between k and l) is the length of the minimum ∼-path connecting k and l (Definition 3), i.e. the number of individuals in which k and l differ. Since A = B = Val u we will use dist (•, •) also between rows and columns. Recall also that Border d (h) = {k ∈ B|dist(h, k) = d}. For typographical reasons, in this proof we will use the notation B h,d to represent Border d (h), and d(k, l) to represent dist (k, l).Let n = |A| = v u . The matrix M ′ is given by

Lemma 4 .

 4 If a randomized function K : A → B respects an ǫ-ratio in the sense that p K (b|a ′ ) ≤ e ǫ • p K (b|a ′′ ) for all a ′ , a ′′ ∈ A and b ∈ B, then the min-entropy leakage from A to B is bounded by:I ∞ (A; B) ≤ ǫ log 2 eProof. For clarity reasons, in this proof we use the notation p(b|A = a) for the probability distributions p K (b|A = a) associated to K. -H ∞ (A|B) = log 2 b p(b) max a p(a|b) (by definition) = log 2 b max a (p(b) p(a|b)) = log 2 b max a (p(a) p(b|a)) (by the Bayes theorem) ≤ log 2 b max a (p(a) e ǫ p(b|â)) (by hypothesis on K, for some fixed â) = log 2 b e ǫ p(b|â) max a p(a) = log 2 (e ǫ max a p(a) b p(b|â)) = log 2 (e ǫ max a p(a)) (by probability laws) = log 2 e ǫ + log max a p(a) = ǫ log 2 e -H ∞ (A) (by definition)

  d > 0, either |Border d (y)| = 0 or |Border d (y)| ≥ c. Then U(X, Y ) ≤ (e ǫ ) n (1 -e ǫ ) (e ǫ ) n (1 -e ǫ ) + c (1 -(e ǫ ) n )

  ) d ≤ 1

Table 1 .

 1 Mechanisms for the city with higher number of votes for a given candidate

	(a) M1: truncated geometric mechanism	(b) M2: our mechanism
	In/Out A	B	C	D	E	F	In/Out A B C D E F
	A 0.535 0.060 0.052 0.046 0.040 0.267	A 2/7 1/7 1/7 1/7 1/7 1/7
	B 0.465 0.069 0.060 0.053 0.046 0.307	B 1/7 2/7 1/7 1/7 1/7 1/7
	C	0.405 0.060 0.069 0.060 0.053 0.353	C	1/7 1/7 2/7 1/7 1/7 1/7
	D 0.353 0.053 0.060 0.069 0.060 0.405	D 1/7 1/7 1/7 2/7 1/7 1/7
	E 0.307 0.046 0.053 0.060 0.069 0.465	E 1/7 1/7 1/7 1/7 2/7 1/7
	F	0.267 0.040 0.046 0.052 0.060 0.535	F	1/7 1/7 1/7 1/7 1/7 2/7

Table 2 .

 2 Mechanisms for the counting query(5 voters)

				1 2 -geom. mechanism		(b) M2: our mechanism
	In/Out 0	1	2	3	4	5	In/Out 0	1	2	3	4	5
	0	2/3 1/6 1/12 1/24 1/48 1/48	0	4/11 2/11 1/11 1/11 1/11 2/11
	1	1/3 1/3 1/6 1/12 1/24 1/24	1	2/11 4/11 2/11 1/11 1/11 1/11
	2	1/6 1/6 1/3 1/6 1/12 1/12	2	1/11 2/11 4/11 2/11 1/11 1/11
	3	1/12 1/12 1/6 1/3 1/6 1/6	3	1/11 1/11 2/11 4/11 2/11 1/11
	4	1/24 1/24 1/12 1/6 1/3 1/3	4	1/11 1/11 1/11 2/11 4/11 2/11
	5	1/48 1/48 1/24 1/12 1/6 2/3	5	2/11 1/11 1/11 1/11 2/11 4/11

In case there are several sensitive attributes in the database (e.g. skin color and presence of a certain medical condition), we can think of the elements of V al as tuples.

Instead of gain functions,[START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] equivalently uses the dual notion of loss functions.

When discussing our result with Barthe and Köpf, they said that they also conjectured that f (u, ǫ) is the optimal bound.

⋆ This work has been partially supported by the project ANR-09-BLAN-0169-01 PANDA, by the INRIA DRI Equipe Associée PRINTEMPS and by the RAS L.R. 7/2007 project TESLA.

Appendix Notation

In the following we assume that A and B are random variables with carriers A and B, respectively. Let M be a channel matrix with input A and output B. We recall that the matrix M represents the conditional probabilities p B|A (•|•). More precisely, the element of M at the intersection of row a ∈ A and column b ∈ B is M a,b = p B|A (b|a). Note that if the matrix M and the input random variable A are given, then the output random variable B is completely determined by them, and we use the notation B(M, A) to represent this dependency. We also use H M ∞ (A) to represent the conditional minentropy H ∞ (A|B(M, A)). Similarly, we use I M ∞ (A) to denote I ∞ (A; B(M, A)). We denote by M [l → k] the matrix obtained by "collapsing" the column l into k, i.e.

Given a partial function ρ : A → B, the image of A under ρ is ρ(A) = {ρ(a)|a ∈ A, ρ(a) = ⊥}, where ⊥ stands for "undefined".

In the proofs we need to use several indices, hence we typically use the letters i, j, h, k, l to range over rows and columns (usually i, h, l range over rows and j, k range over columns). Given a matrix M , we denote by max j M the maximum value of column j over all rows i, i.e. max j M = max i M i,j .

Proofs

For the proofs, it will be useful to consider matrices with certain symmetries. In particular, it will be useful to transform our matrices in square matrices having the property that the elements of the diagonal contain the maximum values of each column, and are all equal. This is the purpose of the following two lemmata: the first one transforms a matrix into a square matrix with all the column maxima in the diagonal, and the second makes all the elements of the diagonal equal. Both transformations preserve ǫ-differential privacy and min-entropy leakage.

Leakage

In this part we prove the results about the bounds on min-entropy leakage. In the following lemmata, we assume that M has input A and output B, and that A has a uniform distribution.

Lemma 1. Given an n × m channel matrix M with n ≤ m, providing ǫ-differential privacy for some ǫ ≥ 0, we can construct a square n × n channel matrix M ′ such that:

the diagonal contains the maximum values of the columns.

to the result of Lemma 1. The final matrix M has size n × n, with n = |X | = v u , provides ǫ-differential privacy, and for all rows i, h we have that M i,i = M h,h and M i,i = max i M . Furthermore, I M ∞ (X) is equal to the min-entropy leakage of K. Let us denote by α the value of every element in the diagonal of M , i.e. α = M i,i for every row i. Note that for every j ∈ Border d (i) (i.e. every j at distance d from a given i) the value of M i,j is at least

Since each row represents a probability distribution, the elements of row i must sum up to 1. Hence:

Now we apply some transformations: α ≤ e ǫ v -1 + e ǫ u [START_REF] Clarkson | Belief in information flow[END_REF] Therefore:

Proof. Let n = |A|. For every h, k ∈ A let us define the elements of M ′ as:

First we prove that M ′ provides ǫ-differential privacy. For every pair h ∼ l and every k:

Now we prove that for every h, M ′ h,• is a legal probability distribution. Remember that

Next we prove that the diagonal contains the maximum value of each column, i.e., for every

Now we perform some simple calculations: Then, for such c, the definition in (6) determines a legal channel matrix for H, i.e., for each y ∈ Y, p Z|Y (•|y) is a probability distribution. Furthermore, the composition K of f and H provides ǫ-differential privacy. Finally, H is optimal in the sense that it maximizes utility when the distribution of Y is uniform. From the same theorem, we know that this is a maximum for the utility.