Marjorie Albino

Philippe Veber

Stanislav Pechev

Christine Labrugère

Matias Velázquez

Mario Maglione

Michaël Josse

Growth and characterization of Ba2LnFeNb4O15 (Ln = Pr, Nd, Sm, Eu) relaxor single crystals

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

Introduction

Relaxor materials exhibit a large number of interesting dielectric properties, and the origin of the relaxor behaviour for the Tetragonal Tungsten Bronze (TTB) structure is debated in the literature [START_REF] Shvartsman | Lead-free relaxor ferroelectrics[END_REF] . Although the presence of different cations inside the same crystallographic sites has been found to trigger a relaxor effect in the SBN system [START_REF] Glass | Investigation of the electrical properties of Sr1-xBaxNb2O6 with special reference to pyroelectric detection[END_REF][START_REF] Kakimoto | Synthesis and dielectric properties of SrxBa1-xNb2O6 formed by YAG laser ablation[END_REF] or in the Ba5LaTi3Nb7O30 compound [START_REF] Li | Relaxor ferroelectric characteristics of Ba5LaTi3Nb7O30 tungsten bronze ceramics[END_REF] , other driving forces have been proposed. The relaxor behaviour seems to depend on the radius ratio of the ions occupying the pentagonal and square channels in some systems [START_REF] Zhu | Dielectric relaxations, ultrasonic attenuation, and their structure dependence in Sr4(LaxNd1-x)2Ti4Nb6O30 tungsten bronze ceramics[END_REF] , and of the size of the elements inserted in the octahedral sites in others [START_REF] Rotaru | Origin and stability of the dipolar response in a family of tetragonal tungsten bronze relaxors[END_REF] . The polarization of a large number of substituted relaxor compounds with TTB structure is caused by off-centering of the cations localized inside the octahedral sites. However it is obvious that other characteristics of the crystalline structure, particularly the cationic [START_REF] Yao | Phase transitions and electrical characterizations of (K0.5Na0.5)2x(Sr0.6Ba0.4)5-xNb10O30 (KNSBN) ceramics with 'unfilled' and 'filled' tetragonal tungsten-bronze (TTB) crystal structure[END_REF] and anionic [START_REF] Prades | Synthesis, structural characterization, and electrical properties of new oxygen-deficient tetragonal tungsten bronzes Ba2NdTi2+xNb3-xO15-x/2[END_REF] defects, the cationic distribution or cationic radii, impact the organization of dipolar moments. Moreover one can find reports in the literature, of octahedral distortions and rotations related to incommensurate modulated structures [START_REF] Woike | The modulated structure of Ba0.39Sr0.61Nb2O6. I. Harmonic solution[END_REF][START_REF] Surmin | Modulated structure of potassium sodium strontium barium niobates (KNSBN) : harmonic solution[END_REF][START_REF] Graetsch | Incommensurate modulation of calcium barium niobate (CBN28 and Ce:CBN28)[END_REF] which may also impact the dielectric properties.

In the case of the Ba2LnFeNb4O15 (BLnFNO) TTB compounds, where Fe 3+ and Nb 5+ ions are distributed within the octahedral sites, the effect of the incorporation of rare-earth cations inside the square sites was highlighted by Josse et al. [START_REF] Josse | The Ba2LnFeNb4O15 "tetragonal tungsten bronze": Towards RT composites multiferroics[END_REF] . In fact, study of the BLnFNO ceramics showed that the accommodation of La 3+ and Pr 3+ in the TTB structure triggers a relaxor behaviour while the incorporation of smaller rare-earths, such as Nd 3+ , Sm 3+ and Eu 3+ , induces a ferroelectric state. Further studies revealed original behaviours, such as ferroelectric to relaxor crossovers [START_REF] Castel | Flexible relaxor materials: Ba2PrxNd1-xFeNb4O15 tetragonal tungsten bronze solid solution[END_REF][START_REF] Roulland | Influence of ceramic process and Eu content on the composite mutiferroic properties of the Ba6-2xLn2xFe1-xNb9-xO30 TTB system[END_REF][START_REF] Kinka | Coexistence of ferroelectric and relaxor states in Ba2PrxNd1-xFeNb4O15 ceramics[END_REF][START_REF] Albino | Synthèse et caractérisation structurale et diélectrique de céramiques et de monocristaux relaxeurs de structure TTB[END_REF] , which led us to undertake the crystal growth of these BLnFNO TTBs, as single crystal studies should allow for a better comprehension of the dielectric behaviours encountered in this system.

Recently we have successfully developed a flux growth method [START_REF] Castel | Crystal growth and characterization of tetragonal tungsten bronze ferroniobates Ba2LnFeNb4O15[END_REF] , which was further optimized and allowed us to grow centimeter-sized Ba2LaFeNb4O15 single crystals [START_REF] Albino | Growth and characterization of centimeter-sized Ba2LaFeNb4O15 crystals from high-temperature solution under a controlled atmosphere[END_REF] . The present study report the use of this optimized growth process applied to the BLnFNO compositions where Ln = Pr, Nd, Sm and Eu. The crystal growth attempts of these materials are presented, and the chemical, structural and dielectric properties of the single crystals obtained are investigated and discussed, with respect to those of the corresponding ceramics concerning the dielectric properties.

Experimental methods

Quantitative analyses for Ba, Ln, Fe, and Nb contents on polished crystals were performed by electron probe micro-analysis EPMA (CAMECA SX100). The cationic contents were determined by assuming the full occupancy of the octahedral sites by Fe 3+ and Nb 5+ ions. Anionic content were calculated with respect to electroneutrality. For each composition, several single crystals underwent multiple tests to make sure the chemical compositions are homogeneous within a crystal and a batch. Chemical compositions were also determined from XRD data collected on BLnFNO single crystals. X-ray photoelectron spectroscopy (XPS) measurements were carried out with a ESCALAB VG 220i-XL spectrometer using MgKα (hν = 1253.6 eV) radiation on as-grown crystals. Ar etching time of 0, 120, 360 and 720 sec. (etching speed ~0.2nm.s -1 ) were used prior to data acquisition. X-ray powder diffraction (XRPD) patterns at room temperature were used to identify the main and secondary phases stabilized following the crystal-growth process. Data collection was performed on a PANalitycal X'pert MPD Bragg-Brentano θ-2θ geometry diffractometer equipped with a secondary monochromator over an angular range of 2θ = [8-80]°. The Cu-Kα radiation was used (λ = 1.5418 Å).

The crystallographic directions of the crystal surfaces were determined using X-ray Laue backscattering analysis (Mo source).

Single crystal XRD was performed with a Nonius Kappa CCD four circles diffractometer with monochromatized Mo-Kα radiation (λ = 0.71073 Å). Cell parameters, space group and modulation vectors were obtained from single crystals XRD data and the basic structure was refined in the P4/mbm space group with the WINGX program [START_REF] Farrugia | WinGX suite for small-molecule single-crystal crystallography[END_REF] .

For dielectric measurements, crystals (1-2 mm in thickness) were polished and were annealed at 900°C for 3h [START_REF] Albino | Growth and characterization of centimeter-sized Ba2LaFeNb4O15 crystals from high-temperature solution under a controlled atmosphere[END_REF] , and silver electrodes were painted on (001) faces. Dielectric response from 80K to 400K was measured using a HP4194a impedance analyzer at frequencies ranging from 10kHz to 1MHz.

Throughout the manuscript, data from the study of BLaFNO crystals will be recalled as reference.

Crystal growth by the flux method

The BLnFNO solutes were first prepared by a conventional solid-state reaction method using starting materials barium carbonate BaCO3 (Cerac, 99.9 %), lanthanide oxides Pr6O11 and Ln2O3 with Ln = Nd, Sm and Eu (Cerac, 99.99%), iron oxide Fe2O3 (Rectapur, 99%), and niobium oxide Nb2O5 (LTS chemical, 99.95 %). Lanthanide oxides were dried overnight at 900°C to drive off hydroxyls groups prior to weighing. After mixing in stoichiometric proportions in an agate mortar and next by ball-milling in ethanol, the mixtures were calcined at 1280°C for 12h.

BLnFNO single crystals were grown with LiBO2 flux under controlled atmosphere using the experimental conditions recently reported by Albino et al. [START_REF] Albino | Growth and characterization of centimeter-sized Ba2LaFeNb4O15 crystals from high-temperature solution under a controlled atmosphere[END_REF] . The loads of 20g of 30mol.% BLnFNO-70mol.% LiBO2 powders were mixed and compressed uniaxially into pellets and placed into a platinum crucible which was then introduced in a sealed platinum chamber under a primary vacuum (P = 10 -2 mbar). A thermal gradient about 0.5°C.cm -1 was achieved all along the platinum assembly placed into a resistive vertical furnace where the minimal temperature was set at the bottom of the inner crucible. The solutions were soaked at 1293°C during 24h. They were first cooled down to 1261°C at a rate of 0.4°C.h -1 , then heated quickly up to 1278°C, and finally cooled down to 1223°C at a rate of 0.2°C.h -1 in order to grow crystals with a significant size [START_REF] Albino | Growth and characterization of centimeter-sized Ba2LaFeNb4O15 crystals from high-temperature solution under a controlled atmosphere[END_REF][START_REF] Elwell | Crystal Growth from High-Temperature Solutions[END_REF] .

Crystal growth attempts led to single crystals trapped into the remaining solidified loads. After removing LiBO2 flux in hot HCl aqueous solution, BLnFNO brown/black single crystals were found at the top of the solidified solutions for each composition (Figure 1a) whereas the bottom of the charges did not melt (Figure 1b). XRPD measurements performed on BLnFNO crushed crystals confirmed the TTB structure.

Maghemite γ-Fe2O3 and fergusonites LnNbO4 were observed (Figure 1c) and identified by XRPD as secondary phases for each growth. In addition, in the case of BEuFNO growth attempt, Ba3Fe2Nb6O21, with the Hexagonal Tungsten Bronze (HTB) structure (ICDD 79-0074), was also detected as sub-millimeter brown single crystals which may have grown within the non-molten part of the load.

As depicted in Figure 1b the estimated height of the non-molten part of the loads, located between the bottom of the inner crucible and the location of the first BLnFNO single crystals (hBPrFNO = 2 mm; hBNdFNO = 2.5 mm; hBSmFNO = 4 mm and hBEuFNO = 10 mm) increases with the molar mass of the solute. According to the low 0.5°C.cm -1 thermal gradient set in the furnace, we deduced that the 30 mol.% BLnFNO-70 mol.% LiBO2 solidus temperatures for Ln = Pr, Nd, Sm, Eu are in the range 1293°C-1294°C and increase with the molar weight of the solute.

The decreasing height of the molten solution (from Pr to Eu) directly influence the BLnFNO growths, decreasing the yield of as-grown crystals, and also their typical size from (4.5 x 7 x 2) mm 3 for BPrFNO to (2 x 2 x 1) mm 3 for BEuFNO (Figure 2). Laue back diffraction experiments were carried out on samples depicted in Figure 2 and revealed that they were actually single crystals. Laue patterns also revealed that the largest natural growth facet, whatever the considered rare earth ion, is perpendicular to the [001] direction.

Results and discussion

Chemical compositions

The compositions of BLnFNO crystals as determined by EPMA are listed in Table 1. Results

show that chemical compositions of the crystals are different from the nominal composition (i.e. the composition of the load). In particular, the Ln content is significantly smaller than expected, especially in BSmFNO and BEuFNO crystals where it lies around 0.5 Ln per formula unit, i.e. even smaller than those of others crystals (0.9; 0.9 and 0.7 for La, Pr and Nd, resp.). For all the crystals, EPMA analyses show a relative stability of barium content, which probably remains inside the pentagonal sites, except for the Eu-based crystals. As for the octahedral sites, compositional analyses support a Nb excess, which can be understood as an adjustment of the Fe/Nb ratio. This adjustment is induced by the partial accommodation of Ln 3+ ions, for sake of electroneutrality. It should be noted that the reduction of lanthanides and iron content is consistent with the formation of LnNbO4 and γ-Fe2O3 secondary phases during the flux growth process.

X-ray photoelectron spectroscopy

We will present first the XPS study of Ba2La0.9Fe0.8Nb4.2O15 (BLaFNO) crystals, never reported previously, as this compound is prototypical of the BLnFNO family.

The C1s peak (Figure 3a), visible on the BLaFNO crystal before Ar-ion etching, was used as the reference and was positioned at 284.7 eV [START_REF] Wagner | Handbook of X-ray Photoelectron Spectroscopy[END_REF] . The XPS method allowed for the observation of Ba 2+ and Nb 5+ ions at the surface of BLaFNO single crystal, while the detection of cations present in lower contents, i.e. La 3+ and Fe 3+ , was hindered by the C contamination (~ 64at.%). By comparison, the peaks observed after etching shift toward a lower binding energy after the first Ar-ion etching (120 sec.). This indicates that the local electronic environment of the corresponding atoms is affected by the etching.

As shown in Figure 3, the binding energies of Ba3d (781.0 eV), La3d (835.3 eV), Fe2p (707.4 eV), Nb3d (203.5 eV) and O1s (530.9 eV), as observed following a 120s etching, do not evolve with prolonged Ar-ion etching (above 120 sec.). XPS spectra on etched BLnFNO crystals are compatible with Ba 2+ and Ln 3+ ions, while if Nb 5+ is the main oxidation state of niobium, other oxidation states (induced by etching as will be shown thereafter) are also observed, and finally the observations concerning Fe2p core-level suggest metallic iron. We will now comment in more detail each of these spectra. For La3d3/2 and La3d5/2 core-level spectra, we observed on the Figure 3d double-peak structures, which were described as the charge-transfer effect from the ligand to the rare-earth 4f orbitals due to the creation of the 3d vacancy [START_REF] Suzuki | Calculation for the charge-transfer effect of La compounds in the 3d -1 core-hole state[END_REF][START_REF] Suzuki | The electronic structure of rare-earth oxides in the creation of the core hole[END_REF] . For each double peak present in the La3d spectra, the peak to a lower and a higher binding energy correspond to the bonding and antibonding orbital respectively.

As shown in Figure 3f, an additional Nb3d core level spectrum with lower binding energies appears and grows with the etching time. This is related to the reduction of Nb 5+ ions by Ar ions, inducing the appearance of Nb 4+ and Nb 3+ ions. A similar phenomenon was previously observed in potassium lithium niobate (KLN) crystal, although in this case the O1s line was also affected (it is not the case in the present study) and suggested that the creation of Nb 4+ and Nb 3+ ions is connected with the loss of oxygen [START_REF] Jun | Ar-ion etching effects on the XPS spectra of the ferroelectric potassium lithium niobate crystal[END_REF] . Whether oxygen vacancies are involved or not, niobium reduction is certainly responsible for the surprising results concerning Fe2p core level spectrum, as the binding energies observed are consistent with metallic iron. Such a situation is rather unexpected in a dielectric, but appears consistent with observations in Fe/NbO thin films suggesting the propensity of iron to be reduced in the presence of niobium [START_REF] Wong | XPS observations of the accelerated oxidation of niobium in the presence of iron[END_REF] .

Line XPS spectra for all the constituting elements of BLnFNO single crystals (Ln = Pr, Nd, Sm, Eu), after 120 sec. Ar etching time, are reported in Figure 4. The shapes and positions of the observed signals are similar to what was observed for BLaFNO crystals, except for the Eu sample in which the O1s peak is significantly broader. To further investigate the chemical properties of BLnFNO crystals, peak fitting was performed using Gaussian-Lorentzian peak function with a gaussian component of [25-50]% and a lorentzian component of [25-50]%. For the Fe2p and Nb3d line spectra, three components related to the oxidation states of both elements were taken into account. Then the binding energy (BE) and the full width at half maximum (FWHM) for Ba, Ln, Fe and Nb were determined and reported in Table 2. Three components were also used for the analysis of O1s spectra, for which the results are gathered in Table 3.

The Ba3d and Ln3d (Ln = Pr, Nd, Sm) lines are consistent with the presence of Ba 2+ and Ln 3+ ions, respectively. The Eu4d line (not presented) is also consistent with the presence of Eu 3+ in BEuFNO crystals. For all crystals, the higher energy peak associated to Nb 5+ is positioned at ~208 eV, and signals associated to the smaller oxidation states (induced by Ar etching) are found at lower energies, close to ~203.5 eV for Nb 3+ and ~205 eV for Nb 4+ . The most prominent peaks are found for Nb 5+ and Fe 0 , while Nb 4+ , Nb 3+ , Fe 2+ and Fe 3+ display relatively small peaks. The equilibrium between iron and niobium oxidation states can be followed throughout the whole series of crystals, as reported in Figure 5. The components associated to Fe 0, 2+, 3+ seem to be correlated to those associated to Nb 3+, 4+, 5+ , as for example in BLaFNO a minimum concentration of Fe 0 correspond to a maximum concentration of Nb 5+ . As the reduction of Nb 5+ cations to intermediate oxidation states by Ar etching was previously reported in the literature [START_REF] Jun | Ar-ion etching effects on the XPS spectra of the ferroelectric potassium lithium niobate crystal[END_REF] , one may consider that the reduction of iron is a secondary effect of niobium reduction, in which electrons are transferred from Nb 3+ or Nb 4+ ions to Fe 3+ ions which are in turn reduced. Thus iron and niobium ions act as communicating vessels with respect to the reduction phenomenon. The smaller iron content found in BLnFNO, with Ln = Nd, Sm and Eu, could however induce a saturation of this equilibrium, or in other word, when iron vessel is (almost) fully reduced to a metallic state, the reduction of Nb 5+ ions induced by Ar-etching is hindered. This reduction mechanism, as it is induced by Ar ions etching, is of little interest with respect to dielectric materials. However TTBs are also studied as mixed conductors [START_REF] Kaiser | Tetragonal tungsten bronze type phases (Sr1-xBax)0.6Ti0.2Nb0.8O3-: Material characterisation and performance as SOFC anodes[END_REF] , and may present opportunities for the development of thermoelectrics [START_REF] Lee | Ferroelectric-thermoelectricity and Mott transition of ferroelectric oxides with high electronic conductivity[END_REF] . Our observations suggest that the association of iron and niobium could be a way to enhance such kind of properties in TTBs.

The O1s core level spectrum visible in Figure 4 can be deconvoluted in three components, which correspond to (Fe,Nb)-O, Ln-O and Ba-O bonds, from higher to lower binding energy respectively (Table 3). The relative areas of these three components evolves within the BLnFNO series, the (Fe,Nb)-O component increasing from La to Eu, while the Ba-O component decreases, but the evolution of the Ln-O is difficult to analyze, except for the Eu-O component which is responsible for the broadening of the O1s line in BEuFNO. The (Fe,Nb)-O component (and thus the corresponding environment) appears very stable in shape and position throughout the BLnFNO series, while the Ba-O component, stable in position, is broadened when going from La to Nd, and stable afterwards. The width of the Ln-O component can hardly be rationalized, but its position appears to shift towards higher binding energies for Ln = Sm and Eu.

Overall, the XPS study show that the oxidation states of Ba and Ln elements are consistent with the ones expected, and that niobium and iron are successively reduced due to Ar ions etching. The environment of oxide anions is essentially stable throughout the series for (Fe,Nb)-O and Ba-O bonds, although a complicated evolution is observed for Ln-O bonds.

XRD on single crystals

XRD on BLnFNO single crystals at room temperature revealed that they retain the TTB structure (Table 4), despite the variation of their chemical composition, and adopt an incommensurately modulated structure, the basic structure of which can be described in the space group P4/mbm (n°127). The modulation is bidimensionnal and is characterized by modulation vectors q1 = α, α, ½ and q2 = α, -α, ½. The modulation parameter, α, was found almost identical, at room temperature, for all the TTB crystals of the BLnFNO series. It should be noted that α values, 0.290 (5) for Ln = La, Pr, Nd and 0.280 (5) for Sm and Eu were extracted from the initial automatic search procedure, but were not further refined.

Refinement of XRD data was carried out only for the basic TTB structure in the space group P4/mbm. Initially, cationic positions were assumed to be fully occupied with no crosssubstitution. In order to obtain a consistent estimate of the occupancies, the two octahedral sites (M(1) and M(2)) were both assumed to be i)fully occupied and ii)statically occupied by iron and niobium ions. Tentative refinements confirmed that the pentagonal sites were fully occupied by barium. The Ba position was split (x and y coordinates being no longer correlated), as frequently encountered [START_REF] Jamieson | Ferroelectric tungsten bronze-type crystal structures. II. Barium sodium niobate Ba(4+x)Na(2-2x)Nb10O30[END_REF] . The possibility of cross-substitution between Ba and Ln sites, the latter occupying the square sites, was ruled out by tentative refinements, even in BEuFNO crystals, in which EPMA results suggested the presence of barium in the square sites. The iron/niobium ratio and the lanthanide contents were then refined with restraints set for sake of electroneutrality. Anionic positions were assumed to be fully occupied throughout the whole refinement process. Cell parameters, unit cell volume, and agreement factors for BLnFNO crystals are given in Table 4.

One could expect a decrease of the a and c lattice parameters from La-to Eu-based compounds with respect to the reduction of Ln 3+ ionic radius, and this trend is observed for Ln = La, Pr and Nd. Nevertheless, smaller Eu 3+ and Sm 3+ cations are associated with significantly larger cells than their Nd 3+ counterparts, although high Ln 3+ vacancies contents could imply unit cell expansion for Ba2Sm0.60(1)□0.40(1)Fe0.41(1)Nb4.59(1)O15 and Ba2Eu0.60(1)□0.40(1)Fe0.39(1)Nb4.61(1)O15 crystals. It is remarkable that the chemical compositions of the crystals within the BLnFNO series (Ln = La, Pr, Nd, Sm, Eu, Table 5) can be described by the formulation Ba2Ln1-x□xFe1-3x/2Nb4+3x/2O15, which is somewhat reminiscent of the formulation Ba2-x/8Ln1-x□xFe1-3x/2Nb4+3x/2O15-x/8 found in corresponding ceramics.

The niobium and lanthanides occupancies refined from XRD data are consistent with those extracted from EPMA analysis (Figure 6), and thus the hypotheses of a fully occupied octahedral framework (EPMA and XRD) and the restraints applied on Fe/Nb ratio and Ln contents in XRD refinements are validated. The EPMA and XRD results clearly show that the square tunnels are partially occupied by Ln 3+ ions, and that the niobium content in the octahedral sites increases from BLaFNO to BEuFNO. These observations are in agreement with the formation of secondary phases (LnNbO4 and γ-Fe2O3) during the growth, as reported in part 2. Thus the variation of the lanthanide content in the square sites is associated with a higher content of ferroelectrically active Nb 5+ cations, especially in BSmFNO and BEuFNO crystals. It is worth mentioning that iron and niobium atoms are localized inside regular M(1) and distorted M(2) octahedral sites, the latter being prone to bear a dipole moment.

In BLnFNO single crystals the barium atoms are in the pentagonal sites, the lanthanides in the square sites, the triangular site is empty and both M(1) and M(2) octahedral sites are occupied by a statistical distribution of iron and niobium, as reported in Table 6. A representation of the overall structure, showing polyhedral linking and the anisotropic displacement parameters (represented by ellipsoids), is given for BPrFNO in Figure 7. The ellipsoids associated to the anionic framework are the largest ones, suggesting that the modulation strongly affects the anionic sublattice. One can also clearly see, from Figure 7, the distortion of the M(2) site related to the accommodation of the Ln 3+ ions within the square channels. Thus the XRD study shows that in BLnFNO crystals, the structural distortion is undoubtedly influenced by both parameters, Ln 3+ cation radius, as illustrated by Figure 7, and vacancies content, as illustrated by the evolution of cell volume (Table 4), both being located in the square channels, the central role of which concerning TTBs crystal chemistry was previously pointed out [START_REF] Josse | The Ba2LnFeNb4O15 "tetragonal tungsten bronze": Towards RT composites multiferroics[END_REF] . Further crystal chemical considerations, from detailed analysis of atomic and bonding parameters, confirm these trends. In Figure 8 can be found the identification of the various parameters discussed below.

Atomic parameters

The For atoms located at z=0, the amplitude of their shifts, is related to their distance from the square channel accommodating the rare earth ions, as schematized in Figure 9b. This trend is confirmed for atoms located at z=1/2 (not represented), for which O(5) in distorted M (2) octahedral sites displays the largest shifts.

The trend observed for atomic position is also relevant concerning the atomic displacement parameters of the anionic framework. At z=1/2, U11O(5), for the oxygen closest to the square channels, ranges from 0.079(5) (La) to 0.158( 16)Ų (Nd) in the BLnFNO series, while for all the others oxygen atoms, U11 is systematically smaller than 0.07Ų. At z=0, U33O(3), for the oxygen which delimits the square channels, vary from 0.059(4) (La) to 0.129( 10)Ų (Eu) in the BLnFNO series, while U33 is systematically smaller than 0.07Ų for all the others oxygen atoms. As illustrated by the ellipsoids in Figure 7, the large atomic displacement parameters of O(3) and O(5) may be related to a tilting of the [M(2)O6] octahedra which define the square channel of the TTB structure.

Bond length

Overall, the Ba-O and M-O bond length appear rather stable within the series, with Ba-O distances variations being smaller than 0.026Å (with the exception of Ba-O(3) distances with a 0.056Å variation), and M-O distances variations being smaller than 0,017Å (with the exception of M(2)-O(3) (0.049Å) and M(2)-O(3)' (0,042Å)). However both Ln-O(3) and Ln-O(5) distances vary by slightly more than 0.05Å within the series.

It is remarkable that bond length involving either the Ln 3+ ions (located in the square channels at z=1/2) or the O(3) independent oxygen atoms (defining the square channel at z=0) display the largest variations, emphasizing again the central role of this channel in the crystal chemistry of BLnFNO TTBs.

The influence of Ln vacancies can be seen in the increase of Ln-O bond lengths observed for BSmFNO and BEuFNO (Figure 10).

A further look at the evolution of cation-anion distances also shows that Ln-O and Ba-O distances evolve in opposite ways. This observation brings support to the idea that the ionic radii ratio of B (square) to A (pentagonal) sites is a relevant crystal-chemical parameter for the TTB structure [START_REF] Shvartsman | Lead-free relaxor ferroelectrics[END_REF][START_REF] Albino | Synthèse et caractérisation structurale et diélectrique de céramiques et de monocristaux relaxeurs de structure TTB[END_REF] .

There is also some subtle differences in the evolution of M(2)-O(3) and M(2)-O(3)' bond lengths, the former being rather monotonous with respect to Ln 3+ ionic radii, while the latter behaves differently for Sm and Eu-based crystals. This observation supports the results of previous studies emphasizing the role of vacancies, inside both square and pentagonal sites, in the crystal chemistry of TTBs 29 .

Bonding angles

The largest variations among intra-and inter-polyhedra bonding angles in the BLnFNO series 2)O6] octahedron itself, in relation with the species accommodated in the square channels. It is remarkable that while the former evolves discontinuously, and is likely to be affected by vacancies content, the latter display a rather continuous evolution, which appears closely related to Ln 3+ ionic radius.

Furthermore the variation of the M(2)-O(3)-M(2) angle can be related to correlated rotations of these octahedra associated with the accommodation of the species located in the square channels.

The widest opening of this angle is found in Sm and Eu crystals, which accommodate a large amount of vacancies. This again supports the idea that vacancies within the square channels have to be accounted for, when investigating the crystal chemistry of TTBs.

Dielectric properties

The temperature dependence of the real and imaginary parts of the dielectric permittivity of BLnFNO (Ln = Pr, Nd, Sm and Eu) crystals, in the frequency range 10kHz-1MHz, is displayed in Figure 12. All the crystals display notably larger maximum permittivities (from 400 to 1700, at 10kHz) than those observed in ceramics (from 180 to 700, at 10kHz [START_REF] Josse | The Ba2LnFeNb4O15 "tetragonal tungsten bronze": Towards RT composites multiferroics[END_REF] ). Significant dielectric losses can clearly be seen at room temperature in the imaginary part of the dielectric permittivity ε''=f(T), which may be related, for example, to electron hopping within the octahedral framework, as it is statistically occupied by Fe 3+ and Nb 5+ ions.

Before the onset of these dielectric losses, a dielectric transition takes place, with a very specific signature, common to all crystals. As frequency increases, the temperature of the maximum of permittivity, Tm is shifted to higher temperature while the permittivity decreases. This causes the transition to be spread over a wide range of temperatures, while far below and far above the transition, the permittivity remains rather frequency independent. These phenomena reveal that these TTB crystals have a typical relaxor behaviour, as the rather low dielectric losses below these transitions (tan < 10%) do not support extrinsic mechanisms such as Maxwell-Wagner relaxation. The temperature corresponding to the maximum value of the dielectric constant at a given frequency is shifted to lower temperatures with the increase in Ln 3+ ionic radius.

The Tm at 1MHz for BLnFNO crystals with Ln = La, Pr, Nd, Sm and Eu are displayed in Figure 13, along with the evolution of the normalized dielectric permittivity. One can clearly see the similarity of the dielectric response throughout the BLnFNO series, and the quite monotonous evolution of Tm(1MHz) which decreases from Eu to La. The maximum value of the permittivity at 10kHz (Figure 14a) also decreases with increasing Ln 3+ ionic radius, from Eu 3+ (1.066 Å) to La 3+ (1.16 Å). Here the Ln 3+ ionic radius obviously has the most influence, as the maximum permittivity is obtained for BEuFNO (~1700), although in this crystal the square channel encompasses as much as 40% of vacancies. As can be seen from Figure 14b, the dielectric dispersion associated to the relaxor behaviour of BLnFNO crystals, which can be described by ΔTm=Tm(500Hz)-Tm(1MHz), decreases with the increase of lanthanides ionic radius. The specific feature detected for the BPrFNO crystals, with almost no dispersion apparent in the real part of the permittivity, is related to the contribution of dielectric losses. Although the dispersion is actually small for the BPrFNO crystal, an obvious dielectric dispersion can be seen in the imaginary part of the permittivity. One can also note that the evolution of Tm(1MHz) is almost linear with respect to Ln 3+ ionic radius, contrary to the evolution of the dielectric permittivity.

These results show that the dielectric permittivity of BLnFNO TTBs is strongly dependent on the Ln 3+ radius, as is Tm(1MHz). The amplitude of the dielectric dispersion associated to the relaxor behaviour may be controlled either by Ln 3+ ionic radius, by the vacancies content or by both parameters, as it reaches maxima for the smallest rare earths studied and for the largest vacancies content. Once again, however, the square channels, and the Ln 3+ ions and vacancies accommodated within, obviously play a central role concerning the dielectric properties.

Discussion

The BLnFNO crystals (Ln = Pr, Nd, Sm, Eu) obtained by flux method present significant deviations from the target compositions, stronger than those observed in the corresponding ceramics. However their chemical compositions can be rationalized, in a similar way to the one used for ceramics, by the formulation Ba2Ln1-x□xFe1-3x/2Nb4+3x/2O15 (from x=0.16 for Ln = Pr to x=0.40 for Ln = Eu). In these crystals, the barium and lanthanides oxidation states are consistent with the expectations, while the XPS study highlighted the propensity of iron to be reduced in the presence of niobium. This observation could be related to the important dielectric losses observed in all the BLnFNO crystals at room temperature. Actually they are prepared in a reducing atmosphere and usually bear some oxygen vacancies, that can cause the niobium and iron ions to be reduced. However the oxygen vacancies can be cured, to some extent, by subsequent annealing in oxygen.

The BLnFNO single crystals retain the TTB structure, and display a bidimensionnal incommensurate modulation which was not solved nor refined in the present study. It is remarkable that these modulations share (almost) the same modulation parameter ≈ 0.29. This value is nonetheless consistent with those reported in the literature (0.25<<0.31) [START_REF] Woike | The modulated structure of Ba0.39Sr0.61Nb2O6. I. Harmonic solution[END_REF][START_REF] Surmin | Modulated structure of potassium sodium strontium barium niobates (KNSBN) : harmonic solution[END_REF][START_REF] Graetsch | Incommensurate modulation of calcium barium niobate (CBN28 and Ce:CBN28)[END_REF][START_REF] Schneck | Incommensurate phases in barium sodium niobate[END_REF][START_REF] Graetsch | Thermally induced structural changes in incommensurate calcium barium niobate Ca0.28Ba0.72Nb2O6 (CBN28)[END_REF][START_REF] Labbé | X-ray structural determination of the quasi-commensurate phase of barium sodium niobate[END_REF][START_REF] Bursill | Incommensurate superstructures and phase transition of strontium barium niobate[END_REF][START_REF] Peng | ferroelectric barium sodium niobate[END_REF] . The main feature of the incommensurate modulations in TTBs is cooperative tiltings in the octahedral framework [START_REF] Woike | The modulated structure of Ba0.39Sr0.61Nb2O6. I. Harmonic solution[END_REF][START_REF] Surmin | Modulated structure of potassium sodium strontium barium niobates (KNSBN) : harmonic solution[END_REF][START_REF] Graetsch | Incommensurate modulation of calcium barium niobate (CBN28 and Ce:CBN28)[END_REF][START_REF] Jamieson | Ferroelectric tungsten bronze-type crystal structures. II. Barium sodium niobate Ba(4+x)Na(2-2x)Nb10O30[END_REF] , which are likely to affect any kind of polar order the TTB framework may possess.

The basic structure of BLnFNO crystals was refined, and the strongest structural variations were found around the square channels in which Ln 3+ ions and vacancies are accommodated. A survey of several crystal chemical parameters (atomic positions, bond length...) has confirmed the central role of the square channels in the crystal chemistry of BLnFNO TTBs. The atomic positions and displacement parameters, in particular, display variations which scale with the proximity of the considered atom with the square channel. The crystal chemistry of TTBs, however, can not be reduced to this square channel, and must account for the contributions of other features of the TTB framework (pentagonal channels, cationic framework...), in order to build a complete understanding of the TTB matrix. In this view, some crystal chemical parameters pointed out in the literature (ionic radii ratio of cations occupying the square and pentagonal channels [START_REF] Shvartsman | Lead-free relaxor ferroelectrics[END_REF][START_REF] Albino | Synthèse et caractérisation structurale et diélectrique de céramiques et de monocristaux relaxeurs de structure TTB[END_REF] , vacancies content 29 ...) are supported by some of our observations. In the end, it is likely that the accommodation of the species inserted in the square channel, depending on their content and the characteristics of the species occupying the other channels of the TTB structure, plays an important role in the onset of aperiodic modulations.

All the BLnFNO crystals display a relaxor behaviour, in contrast with the ferroelectric response previously observed in Ba2LnFeNb4O15 ceramics with Ln = Nd, Sm and Eu [START_REF] Josse | The Ba2LnFeNb4O15 "tetragonal tungsten bronze": Towards RT composites multiferroics[END_REF] . Larger dielectric permittivities (up to ε'=1700) than those of corresponding ceramics are also found in all the crystals. It is unclear, however, if these higher permittivities arise from chemical (compositional variation), crystalline (larger dielectric permittivities in single-crystals due to measurement along a specific [001] direction) or microstructural (limitation of ceramics permittivities by microstructure and secondary phases) phenomena. At this stage of the study, it is difficult to establish connections between the relaxor behaviour and modulated TTB structure, as the latter is still present at room temperature in the paraelectric state. However modulated structures usually evolve with temperature, and thus may indirectly affect the dielectric state of BLnFNO crystals.

Meanwhile the TTB crystal structure and dielectric properties remain highly sensitive to the content of the square channels, in agreement with previous studies [START_REF] Surmin | Modulated structure of potassium sodium strontium barium niobates (KNSBN) : harmonic solution[END_REF] . The dielectric transition temperatures of TTB crystals increase linearly with the decrease of Ln 3+ ionic radius, but also with the increase of Nb 5+ content, as illustrated by the afore-mentioned formulation. However the much higher contents of ferroelectrically active ions inside the octahedral sites is not necessarily the driving force of the relaxor behaviour, as in some ceramics its increase is associated with the disappearance of a ferroelectric state [START_REF] Roulland | Influence of ceramic process and Eu content on the composite mutiferroic properties of the Ba6-2xLn2xFe1-xNb9-xO30 TTB system[END_REF] . It is thus extremely interesting to compare the dielectric transitions temperatures and the content of the square sites, as observed in BLnFNO crystals and in the corresponding ceramics, with respect to Ln 3+ ionic radius (Figure 15).

The main difference between crystals and ceramics chemical compositions is the Ln 3+ content within the square sites, which reach values as low as 60% in BSmFNO and BEuFNO crystals, vs 81% in BEuFNO ceramics [START_REF] Castel | Synthèse de nouveaux matériaux multiferroïques au sein de la famille des bronzes quadratiques de formule Ba2LnFeNb4O15[END_REF] . As the single crystals were grown from a liquid phase containing a flux, and thus compositional modifications were easier, one can consider that the composition of the BLnFNO crystals are the most stable ones. Meanwhile, for Nd, Sm and Eu ceramics, in which the Ln 3+ content is higher, the compositional modifications were somehow limited by the mechanism compensating the Ln 3+ deficit and producing the secondary phases. The compensation mechanism for the ceramics can be resumed as follows:

Ba2-x/8Ln1-x□xFe1-3x/2Nb4+3x/2O15-x/8 + x LnNbO4 + 3x/24 BaFe12O19 36 while the compensation mechanism for the single crystals would be:

Ba2Ln1-x□xFe1-3x/2Nb4+3x/2O15 + x LnNbO4 + 3x/4 -Fe2O3
In fact, the difference between Ln 3+ deficit compensation mechanisms in ceramics and single crystals lies in the involvement of Ba 2+ ions, as the BaFe12O19 phase is formed in ceramics (responsible of their composite multiferroic properties [START_REF] Castel | In-situ formation of barium ferrite in iron-doped "tetragonal tungsten bronze" : Elaboration of room temperature multiferroic composites[END_REF] ), while -Fe2O3 is formed during the growth of single crystals.

While the Ln 3+ ionic radius appears to control the ordering temperature in crystals, as a rather linear evolution of both parameters is found (Figure 15), the vacancies content obviously affects the range of the polar order. This latter point is illustrated by the relaxor behaviour found in BNdFNO crystals (Nd content: 76%), while BNdFNO ceramics are ferroelectric (Nd content: 100%). There is however limits to the impact of vacancies on the dielectric behaviour, as BLaFNO and BPrFNO crystals and ceramics (84% ≤ Ln content ≤ 100%) are relaxors. Furthermore, although BSmFNO and BEuFNO encompass similar Ln 3+ contents, and display larger cell volumes than their Nd analogue, the ordering temperature increase from BSmFNO to BEuFNO, supporting the prevalence of Ln 3+ ionic radius on the dielectric behaviour of BLnFNO TTBs. Thus, the BLnFNO single crystals offer a solid basis to investigate the underlying mechanism of relaxor behaviour in Ba2LnFeNb4O15 TTBs, but may also give hints on the most important parameters controlling the composition of TTB materials, the expression of ferroelectric properties and ultimately the formation of multiferroic "crystal chemical composites".

Conclusion

We successfully grew millimeter-to centimeter-sized BLnFNO single crystals with the TTB structure by using a high temperature solution growth method performed under controlled atmosphere. The growth conditions allowed locating the solidus (1293 to 1294°C) for the 30 mol.% BLnFNO-70 mol.% LiBO2 region of the phase diagrams. Two secondary phases, namely fergusonite LnNbO4 and maghemite Fe2O3 were invariably detected whatever the rare earth element Ln = Pr, Nd, Sm, Eu involved.

The chemical compositions of the crystals strongly deviate from the nominal composition, due to partial accommodation of Ln 3+ ions within the square sites of the TTB framework. This induces high concentrations of vacancies in the square channels, reaching 40% for Ln = Sm, Eu.

The deviation from the nominal composition can be described by the following formulation: Ba2Ln1-x□xFe1-3x/2Nb4+3x/2O15. This formulation is consistent with the composition of all BLnFNO crystals (Ln = La, Pr, Nd, Sm and Eu), as determined by EPMA and XRD, and accounts for the secondary phases formation.

XPS studies indicated that Ba and Ln oxidation states are consistent with the expected values, while reduction of iron and niobium due to Ar etching suggest hopping as the mechanism responsible for the dielectric losses observed at room temperature in all crystals. Structural investigations performed by single-crystal XRD revealed an incommensurately modulated structure at room temperature in all crystals. The basic structure was refined in the P4/mbm space group, and the results obtained allowed for the examination of several crystal chemical parameters. While some of our observations supports the relevance of some parameters concerning the crystal chemistry of TTBs, the central role played by the square channel in BLnFNO TTBs has been confirmed.

The dielectric measurements performed on crystals equipped with electrodes perpendicular to the [001] direction revealed a relaxor behaviour in all BLnFNO crystals (Ln = Pr, Nd, Sm and Eu), which are thus good candidates for the study of the driving forces concerning relaxor behaviour in TTBs. Finally comparison of the dielectric transition temperatures and lanthanide contents of the BLnFNO crystals and of the corresponding ceramics confirm the prevalent role of the square channels (and the species accommodated wherein) on the dielectric properties of BLnFNO TTBs. Our observations also suggest that these crystals may provide further understanding of TTBs, especially concerning the parameter controlling their chemical composition, their ferroelectric and ultimately multiferroic composite properties.

Acknowledgements

  atoms are distributed in layers located at z=0 (Nb, Fe, O(2), O(3), O(4)) and z=1/2 (Ln, Ba, O(1) et O(5)), which allows for comparison of their positions within the series of BLnFNO single crystals. The modifications of positional parameters are rather small, and systematically below 0.5%. The relative variations of O(3) and M(2) positional parameters (with respect to the corresponding BLaFNO parameters), which display the largest variations within the series, are displayed in Figure 9a. While the evolution of M(2) positional parameters appears quite monotonous, those of O(3) are strongly modified in BSmFNO and BEuFNO single-crystals. This singular evolution, with respect to La, Pr and Nd representatives, may be related to the high vacancies content (40%) in these samples.

  are found within the [M(2)O6] octahedra, with a 6% opening of the O(3)-M(2)-O(3)' angle (from 81.2(3)° (La) to 86.1(5)° (Sm)) and a 2.8% closing of the opposite O(4)-M(2)-O(2) angle (from 97.8(2)° (La) to 95.1(3)° (Eu)). As [M(2)O6] octahedra define the square channels in the TTB framework, these observation again evidence its central role in BLnFNO TTBs crystal chemistry. Further details of the evolution of the angles associated to the [M(2)O6] octahedra are displayed in Figure 11. Within the octahedron, the variation of O(3)-M(2)-O(3)' and O(4)-M(2)-O(2) angles can be linked to the distortions of the [M(

Figure 1 .

 1 Figure 1. (a) As-grown BLnFNO crystals, shown on millimetric paper.

Figure 2 .

 2 Figure 2. Post-annealed BLnFNO (Ln = Pr, Nd, Sm and Eu) crystals used for the dielectric

Figure 3 .

 3 Figure 3. XPS spectra evolution following Ar-ion etching on a BLaFNO crystal. The etching

Figure 4 .

 4 Figure 4. Line XPS spectra of O1s, Ba3d, Fe2p, Nb3d and Ln3d (except Eu) on BLnFNO crystals

Figure 5 .

 5 Figure 5. Component area (%) of (a) iron and (b) niobium extracted from fits of the XPS data

Figure 6 .

 6 Figure 6. Evolution of niobium and lanthanides contents, as in BLnFNO crystals, extracted from

Figure 7 .

 7 Figure 7. Crystal structure of BPrFNO at room temperature projected on the ab plane and along

Figure 8 .

 8 Figure 8. Identification of the atomic positions used for discussion of various crystal chemical

Figure 9 .

 9 Figure 9. (a) Variation of atomic position in BLnFNO single-crystals with respect to BLaFNO

Figure 10 .

 10 Figure 10. Evolution of selected Ba-O, Ln-O and M(2)-O bond length with respect to the ionic

Figure 11 .

 11 Figure 11. Relative variations (with reference to BLaFNO) of the various angles associated to the

Figure 12 .

 12 Figure 12. Real and imaginary part of the dielectric permittivity reported for BLnFNO crystals

Figure 13 .

 13 Figure 13. Thermal variation of the normalized dielectric permittivity at the frequency f=1MHz

Figure 14 .

 14 Figure 14. (a) Evolution of the maximum dielectric permittivity (at lowest frequency, 10kHz,

Figure 15 .

 15 Figure 15. Evolution of dielectric ordering temperatures and Ln 3+ contents (as determined from

Table 3 .

 3 Gaussian-Lorentzian fitting results of O1s core levels after 120 sec. Ar etching time on

Table 1 .

 1 Cationic contents, determined using EPMA, assuming a 100% filled octahedral framework.

	Crystals	Ba (th.: 2) Ln (th.: 1) Fe (th.: 1) Nb (th.: 4) O
	BLaFNO 18 2.03(2)	0.88(2)	0.77(2)	4.23(2)	15.08(2)
	BPrFNO	2.01(2)	0.88(2)	0.62(2)	4.38(2)	15.21(2)
	BNdFNO	2.06(2)	0.72(2)	0.61(2)	4.39(2)	15.03(2)
	BSmFNO	2.08(2)	0.53(2)	0.53(2)	4.47(2)	14.85(2)
	BEuFNO	2.13(2)	0.47(2)	0.35(2)	4.65(2)	14.99(2)

Table 2 .

 2 Gaussian-Lorentzian fitting results of Ba3d, Ln3d, Fe2p and Nb3d core levels after 120 sec. Ar etching time on BLnFNO crystals.

		Ba3d	Ln3d		Fe2p			Nb3d
					BLaFNO
	Cation	Ba 2+	Ln 3+	Fe 3+	Fe 2+	Fe 0	Nb 5+	Nb 4+	Nb 3+
	BE (eV)	781.0(1)	835.3(1)	711.5(1)	709.6(1)	707.4(1)	207.6(1)	205.2(1)	203.5(1)
	FWHM (eV)	2.1(1)	1.9(1)	1.8(1)	2.2(1)	2.0(1)	1.9(1)	2.0(1)	1.9(1)
	Area (%)			9.2(1)	15.5(1)	75.3(1)	59.6(1)	19.7(1)	20.7(1)
					BPrFNO
	BE (eV)	780.8(
	FWHM (eV)
	Area (%)

Table 4 .

 4 Crystallographic data and agreement factors for BLnFNO single crystals, in the space group P4/mbm at room temperature.

			Crystallographic data		Agreement factors
		a (Å)	c (Å)	V (Å 3 )	R	wR	S
	BLaFNO 18 12.5202(2) 3.9364(1)	617.05(2)	0.0272	0.0534	1.176
	BPrFNO	12.4899(2) 3.9266(1)	612.54(2)	0.0274	0.0586	1.159
	BNdFNO	12.4408(2) 3.9144(1)	605.85(2)	0.0416	0.1021	1.323
	BSmFNO	12.4911(2) 3.9391(1)	614.61(2)	0.0328	0.0849	1.273
	BEuFNO	12.4707(2) 3.9345(1)	611.89(2)	0.0357	0.0933	1.163

Table 6 .

 6 Fractional atomic coordinates refined on BLnFNO from single crystal XRD. Atomic positions omitted in the table: Ln 2b (0 0 1/2), M(1) 2d (1/2 0 0) and O(1) at 2c (1/2 0 1/2).

	Ba 8j	M(2) 8i
	(x, y, 1/2)

The authors acknowledge financial supports from the Centre National de la Recherche Scientifique (CNRS), Aquitaine region (Grant 20091101010) and the Agence National de la Recherche (ANR CROCODIEL) (Grant ANR-09-JCJC-0079). Crystal Growth platform acknowledges the financial support of GIS AMA "Advanced Materials in Aquitaine". The authors wish to thank Viraphong Oudomsack for Pt assembly soldering. Michel Lahaye is acknowledged for the EPMA characterization of the crystals.


Bogdan Cautis
email: bogdan.cautis@inria.fr

Distributed Access Control: A Privacy-conscious Approach

Keywords: H.2.7 [Database administration]: Security, integrity and protection -Access control Security, Algorithms access control, privacy, digital signatures, relational data, semi-structured data, XML

With more and more information being exchanged or published on the Web or in peer-to-peer, and with the significant growth in numbers of distributed, heterogeneous data sources, issues like access control and data privacy are becoming increasingly complex and difficult to manage. Very often, when dealing with sensitive information in such settings, the specification of access control policies and their enforcement are no longer handled by the actual data sources, and are (partially) delegated to third-parties. Besides practical reasons, this is the case when decisions regarding access depend on factors which overpass the scope and knowledge of some of the entities involved. More specifically, policies may depend on private aspects concerning users (accessing data) or data owners. In this case, the only solution is to entrust some third-party authority with all the information needed to apply access policies. However, as the policies themselves depend on sensitive information, this outsourcing raises new privacy issues, that were not present in centralized environments. In particular, information leaks may occur during access control enforcement.

In this paper, we consider these issues and, starting from non-conventional digital signatures, we take a first step towards an implementation solution for such settings where both data and access policies are distributed. Our approach involves rewriting user queries into forms which are authorized, and we illustrate this for both structured (relational) and semi-structured (XML) data and queries.

INTRODUCTION

Access control has been studied extensively, for both relational and semi-structured data, yet mostly in centralized settings. With more and more information being exchanged and published on the Web or in peer-to-peer, and with the significant growth in numbers of heterogenous, distributed data sources (such as PDAs or medical devices), issues like access control and privacy are becoming increasingly complex and difficult to manage.

Consider for instance health information [START_REF]Health Level Seven[END_REF]. By nature, a patient record consists of many pieces owned and managed by different entities (patient, referring doctor, specialists, hospitals, insurance company, various medical devices, etc). Moreover, it has often a sensitive nature, since patients clearly do not want unauthorized parties to access parts of their medical record.

Very often, for such data that is both highly distributed and partially confidential, the specification of access control policies and their enforcement are no longer handled by the actual data sources, and have to be (partially) delegated to third-parties [START_REF] Abendroth | Partial outsourcing: a new paradigm for access control[END_REF][START_REF] Abiteboul | An electronic patient record "on steroids": Distributed, P2P, secure and privacy-conscious[END_REF][START_REF] Di Vimercati | An access control model for querying XML data[END_REF][START_REF] Carminati | Selective and authentic third-party distribution of XML documents[END_REF][START_REF] Harrington | Cryptographic access control in a distributed file system[END_REF]. There are several reasons in favor of such an approach. For example, access control tasks may be too resource demanding for some data devices. Also, policies may be somewhat global and not necessarily chosen by data owners, and by delegating access control to such trusted authorities, one does not risk to misinterpret policies or rely on obsolete ones.

Even more importantly, decisions regarding access may depend on various factors which could overpass the scope and knowledge of some of the entities involved. More specifically, policies may depend on private aspects concerning both the user (who is demanding access to resources) and the data source. In this case, the only solution is to entrust some third-party authority with all the information needed to apply access policies and let it handle their enforcement. We can imagine that such authorities are at the boundary between private domains, having access to private information from several parties and managing access policies that rely on this information.

However, when the policies themselves depend on sensitive information, this outsourcing of access control can raise new issues, mainly concerning privacy, that were not present in centralized environments. More precisely, information leaks may occur even during the initial enforcement phase, i.e., when decisions are made about how the evaluation and answering of the original user query are altered, and before actually returning query answers. Let us consider a high-level example which illustrates this situation and re-lated ideas. (This example will be detailed further on for semi-structured data and queries.) Example 1.1. Consider the 3-party scenario of Figure 1, in which a user, Specialized Medical Doctor (SMD), is demanding access to some patient information from a medical record stored by a Hospital source.

Assume the initial user query asks for: "treatment data for John Smith, either from the hospital's regular medical records or from clinical trials which were conducted there".

Assume Hospital does not accept queries for patients unless they are first verified, properly restricted and certified by their corresponding authority, Referring Medical Doctor (RMD). In other words, RMD acts as an access control proxy for incoming queries from users, modifying them so that they access only allowed information. Let us assume that some access rule from RMD triggers only when

• SMD performs clinical trials (which is a piece of private information concerning SMD, not to be disclosed to parties such as Hospital),

• the patient has some blood related diagnosis (also a piece of private information, not to be disclosed to parties such as SMD).

Assume that the effect of this rule will be that SMD can only access the treatment data from regular medical records (but not the one from clinical trial records).

In order to apply this rule, RMD must have access to these private sensitive details from both parties. But if the rule is triggered, and the query issued by SMD is transformed accordingly, then simply disclosing to either party that the query is not the original one but was modified (and how) reveals private sensitive information.

Notice that we assume in the above example that access control is implemented in a pre-processing phase, via query rewriting, i.e., modifying the user query into an authorized one. Indeed, this is one of the most common approaches on controlling access and has several advantages, such as avoiding information disclosure due to visible data manipulations and exploiting existing query optimization techniques. Moreover, it is particularly suited for settings where storage and access control tasks are decoupled, since answers can be safely returned directly to the user who issued the query, without any additional filtering of sensitive data.

We revisit in this paper access control in a distributed setting similar to the one considered in [START_REF] Abiteboul | An electronic patient record "on steroids": Distributed, P2P, secure and privacy-conscious[END_REF], where each source may delegate to other peers some or all of the tasks of defining/enforcing access control for the data it owns. In other words, before being evaluated at the data source, a user query may be modified and restricted by some intermediaries, denoted access control authorities (ACAs, in short). The applied restrictions correspond to policies referring to the particular user and data source. A query reaching the source is valid only if certified by all the required ACAs. Once the restricted query is evaluated at the source, the results can be directly returned to the user. This access control setting is illustrated in Figure 2. We refer to this hereafter as distributed access control.

Importantly, we consider that access policies may rely on sensitive information. The goal of this paper is to contribute

Q Q' Medical Record

SMD RMD Hospital

Figure 1: A simple example scenario. to the understanding of the requirements and challenges that are raised in this context, and to suggest a possible solution for the privacy-preserving implementation of distributed access control. Our solution uses cryptographic techniques, and in particular non-conventional (homomorphic) digital signatures.

Q Answers User ACA 1 Source … ACA n Q 1 Q n-1 Q n (Q n authorized
The foremost challenge and our main focus is on preventing information leaks that may occur during query rewriting while, at the same time, providing provenance and validity guarantees for queries "traveling" between a user and the targeted data source. As witnessed in Example 1, simply disclosing to either the user, the source or other ACAs that query transformations were performed at some step may breach privacy. We stress that this does not mean that the actual effect of transformations should also be hidden, but only the fact that such operations occurred after the user initiated the exchange.

To the best of our knowledge, this is the first paper to address the issue of information leaks that may occur in query rewriting-based access control in non-centralized environments. While the work presented in this paper is a step towards enforcing access control when both data and policies are distributed, more is needed in order to achieve this task without breaching privacy. Other aspects, such as the effect of collusion or the inference of private information from query results (see, for example, [START_REF] Farkas | The inference problem: a survey[END_REF]), are also important. A complete study of these aspects is beyond the scope of this paper.

Outline. We start by identifying the core issues that need to be addressed in the context of distributed and privacyconscious access control, in Section 2. In Section 3, we introduce auxiliary cryptographic tools, namely homomorphic signature schemes for modifiable collections. We first illustrate their usage and the main ideas behind our approach by considering relational data and select-project-join queries with non-equalities, in Section 4.1. In Section 4.2, we extend and adapt these techniques to XML data accessed in terms of a rich family of tree pattern queries. We consider related work and we conclude in Section 5.

PRELIMINARIES

We start by introducing some initial assumptions and auxiliary notions. We assume some familiarity with common cryptographic notions such as public-key digital signing (for a comprehensive study we refer the reader to [START_REF] Goldreich | Foundations of Cryptography[END_REF]).

Basic assumptions. For simplicity, we assume that the ACAs who need to be first consulted in order to access a given source are always publicly known. We assume that queries follow a linear path, in which each ACA is visited once (as illustrated in Figure 2). (Indeed, this is the only scenario which does not pose a threat to privacy.) Also, the order in which ACAs intercept a query is not important for the source; regardless of the path that was followed, all that matters is which authorities are certifying it as valid. So, when a query is initially sent, the user chooses one of the required ACAs and redirects her query to this authority. Besides the origin and target destination, we assume that each query will carry an ID and a timestamp. Parties are assumed to have well-known identities to which public/private keys are associated. While ACAs are trusted to apply the access policies they are assigned and accordingly, have access to the (potentially private) information on which their policies rely, they should not gain access to any other details about users and sources.

Query rewriting-based access control. Many access control frameworks adopt a query-level enforcement of policies [START_REF] Vercammen | Query translation for xpath-based security views[END_REF][START_REF] Rizvi | Extending query rewriting techniques for fine-grained access control[END_REF][START_REF] Kanza | Authorization-transparent access control for XML under the non-Truman model[END_REF][START_REF] Fan | Secure XML querying with security views[END_REF][START_REF] Di Vimercati | An access control model for querying XML data[END_REF], in which all the validity checking is done in a pre-processing phase, before accessing data. In this way, user queries are modified into forms which are authorized (if at all possible), the modifications being aimed at restricting the query to reveal only accessible data.

We assume a role-based approach on access control. Given the user identity and the data item which is to be accessed, each ACA decides to grant or deny access; once access is denied, it cannot be granted back. Denied access translates (if possible) into query restrictions.

Abstracting away from how policies are specified, we will focus directly on the language-specific query restrictions that can be applied to enforce them. According to intuition, what is returned (explicitly or implicitly) by a restricted version of a query should be a subset of what is returned by the initial one. Informally, ACAs can restrict queries by either introducing additional conditions that must be met by the queried data, or by limiting the scope of the query output. We say that a query is authorized by an ACA w.r.t. a certain user and source if it obeys the policies handled by that ACA. Importantly, we assume a "monotone" semantics for query-based access, in the sense that if a query is considered authorized by some ACA, then a more restricted version of it should be authorized as well. More details on query restrictions will be given in Sections 4.1 and 4.2, when discussing relational and XML queries respectively.

Distributed Access Control requirements. We next discuss the main requirements that need to be addressed in the context of distributed privacy-preserving access control:

• Query provenance. An important aspect of distributed access control in general is the need for provenance guarantees. Being able to determine where an incoming query originates, even if it may have been modified along the way, is even more crucial in our case, since access decisions are made based on the identity of the querier. So, a first requirement is that the origin of a query that arrives at an ACA or at the target source must be authentic, in the sense that it should not be possible to maliciously attribute queries to users. Obviously, this is needed when choosing and enforcing access policies, but may also be useful in tasks such as auditing and monitoring access as well.

• Query validity. Besides provenance, a source must be able to verify that an incoming query is authorized by the all the required ACAs; only in this case, the query is considered valid. Otherwise, the query is rejected. Thus a second requirement is that false validity assertions for queries should be prevented.

• No history. As illustrated in Example 1, since access policies may depend on sensitive information, simply disclosing how they were applied in the ACA process, and as a consequence, how a given query was modified, may cause a privacy breach. In other words, while intermediaries must certify that a given query is authorized, they have to be able to hide the fact that some query aspects do not originate at the query issuer. This should be hidden to the user, source or even other authorities.

Unsurprisingly, what is particulary problematic and almost contradictory in this model is the need to guarantee provenance and validity for a query, while hiding what transformations occurred at ACAs.

In general, in order to authenticate a piece of information that is exchanged, one usually needs to digitally sign it. Indeed, this can be done by the user who issues the query, in order to prove its provenance. Similarly, if some intermediary (ACA) intercepts a query and wants to certify that the resulting (restricted) version is valid (as far as she is concerned), she can do this by digitally signing it. However, while digital signatures are well established techniques for enforcing data integrity and authenticity, the common assumption is that they disallow any kind of modification on the signed message. Hence, once a query is signed by the user or some ACA, this would prevent downstream ACAs from further restricting it. This means that the query will remain valid (w.r.t. the ACA who signed it) only as long as it is not modified. In fact, what we want is for ACAs to be able to modify an incoming query provided they only perform restrictions. In particular, ACAs should not be able to undo or relax previous transformations.

Supporting only partially these requirements is fairly easy. For instance, if we accept to disclose the query changes to the data source, the simplest way would be to take the following high-level steps1 (see Figure 3(a)):

• the user signs her query (using some classic signing scheme) and sends it forward to the intermediaries that have to validate it.

• the query passes by each of those intermediaries in turn, and each of them can add some changes (e.g., to a list of deltas) that are to be considered by the destination.

• each of the intermediaries signs her changes (by any classic signing scheme).

• when the query and its list of deltas arrive at the destination, it is immediate to check the provenance of the initial query (still available), of the changes, and the fact that modifications are only restricting the query.

Q Q + 1 User ACA 1 ACA 2 Source Q + 1 + 2 + … … Answers (a)
Disclosing the query modifications to other ACAs and the source by keeping explicit deltas.

Q Q Q 2 Q n-1 1 User ACA 1 ACA 2 ACA n … … Q n Q n Q n Q n Source Q n Answers
(b) Disclosing the query modifications to other ACAs and the user by first obtaining the final query. Similarly, if we accept to disclose the query changes to the user, the simplest way is by taking the following high-level steps (see Figure 3(b)):

• the user sends her query to the intermediaries that have to validate it.

• the query passes by each of those intermediaries in turn, and each of them performs some changes on the received query.

• the final restricted version follows the same path back, and in the process is signed by each intermediary and finally by the user.

• last, the query and all its certifications are sent to the destination party.

Solution overview. Our solution is based on non-conventional digital signing techniques, which allow some pre-defined type of modifications over signed information. (These are generally known as homomorphic signatures.) To guarantee provenance and to enable validity, the origin will indeed sign her queries, but in a way that allows downstream intermediaries to modify them, provided they only perform restrictions. Each ACA will be able to apply restrictions from a language-specific range, and then update the digital signature of the query (via the mechanisms of homomorphic signatures), reflecting these changes. Since the query signature will remain valid only as long as further restrictions are applied, each ACA can safely put its validity certificate on the query it sends further to the source or other ACAs. Since homomorphic signatures do not reveal anything about the evolution of the signed data, our approach allows ACA authorities to enforce policies by query rewriting while being able to hide all details about the performed modifications.

No key sharing is needed and no particular details about potential restrictions to a given query have to be chosen or agreed in advance by the user, source or ACAs. Importantly, our approach is generic, in the sense that it does not depend on how policies are specified, but only on how they are enforced in query rewriting. In this way, any query rewritingbased access control model can rely on our algorithm, using it as a black box.

The following section introduces the cryptographic tools we will use.

HOMOMORPHIC SIGNATURES

While the common assumption about digital signatures is that they disallow any kind of modification on signed data, a more flexible approach is often needed and has been advocated lately, one in which some restricted modifications may still occur, without invalidating the data. This is made possible by offering signatures which are homomorphic with respect to some operation on the message domain. Starting from the signature(s) of some data instance(s), computed by the data owner, anybody else can derive the signature corresponding to a new data instance, if obtained only via some accepted operation from the previous one(s). More, updated signatures should be indistinguishable from the ones computed by the data owner and this updating step should be applicable as many times as needed.

For a given data domain Dom and signature space S, we say that a public-key signature scheme (Sign sk , V erif y pk ) is homomorphic with respect to some binary operation ⊙ : Dom 2 → Dom, if there exists an efficient and public signature update algorithm U pdate pk : Dom 2 × S 2 → S (or U pdate pk : Dom 2 × S → S) such that

U pdate pk (d1, s1, d2, [s2]) = Sign sk (⊙(d1, d2))
for any pair of matching public-private keys (pk, sk) and pairs (di, si) such that V erif y pk (di, si) outputs {true}.

An important requirement is that signatures obtained via the (secret) signing algorithm and the ones obtained via the (public) updating algorithm should be indistinguishable (as defined below). For such signature schemes, a forgery will refer to a message which is not obtainable via ⊙ from already signed messages.

Insert-only and delete-only sets. Of particular interest to this paper are two homomorphic set-signing schemes. First, starting from an RSA-like scheme, [START_REF] Johnson | Homomorphic signature schemes[END_REF] proposes a public-key set-signing scheme (Sign sk , V erif y pk ) that is homomorphic with respect to both set difference and union. More specifically, it provides two (public) updating functions U pdate pk and U pdate pk , such that:

(1) ∀U, U ′ ⊆ U, U pdate pk (U, Sign sk (U ), U ′ ) = Sign sk (U ′ ) (2) ∀U1, U2, U pdate pk (U1, Sign sk (U1), U2, Sign sk (U2)) = Sign sk (U1 ∪ U2)
Given a collection U = {a1, ..., an} and the signature s = Sign sk (U ) (for some secret key sk), someone who wants to remove elements, for instance update U to the subset U ′ , will be able to sign U ′ by using [START_REF] Abendroth | Partial outsourcing: a new paradigm for access control[END_REF]. The signatures obtained by the homomorphic property are completely history independent, because an updated signature is exactly the one that the signing procedure would yield. It is easy to see that we can consider this scheme as one for delete-only sets if distinct (fresh) public-private key pairs are used each time a collection is signed.

Second, starting from the above technique for delete-only sets, [START_REF] Abiteboul | Digital signatures for modifiable collections[END_REF] proposes the dual signature scheme, for insert-only sets 2 . More precisely, this scheme provides a public-key setsigning scheme (Sign sk , V erif y pk ) and updating function U pdate pk , such that:

∀U, an+1 / ∈ U, U pdate pk (U, Sign sk (U ), an+1) = Sign sk (U ∪ {an+1})
Given a set U = {a1, ..., an}, some new element an+1, and the signature s = Sign sk (U ) (for some secret key sk), someone who wants to insert an+1 can do so without having to know the private key. After insertion(s), she simply updates the set signature. The signatures obtained by the homomorphic property are no longer history independent, because the signing and updating algorithms are probabilistic. However, they are computationally indistinguishable [START_REF] Goldreich | Foundations of Cryptography[END_REF]. In particular, the order of insertions is not disclosed.

We stress that the above updating steps on the data and its corresponding signature, for both delete-only and insertonly sets, can be applied as many times as needed.

In practice. Consider someone who wants to publish a collection with one-way updating, allowing everybody else to perform the legal kind of updates. While the signing techniques support this behavior, their success depends on one aspect: the public key used to verify and update signatures.

This key should not be modifiable, if we want to guarantee the one-way updating. For that, the owner of the collection has to simply sign this collection key with her (conventional) personal public key. Of course, we assume that each party has such a key, which is also known by everybody else. By signing the collection key we create a "fixed point" from which we can indeed enforce one-way updating. Someone receiving a collection signed in this way, will only be able to conclude that it is either the initial one or a subset (resp. a superset) of the initial one.

SIGNING MODIFIABLE QUERIES

We are now ready to describe how the two homomorphic signatures described in the previous section can be used to provide authenticity and validity guarantees for queries, without revealing how/if they were modified. For simplicity, low-level details of our cryptography-based approach are omitted.

In the following sections, for relational and XML data in turn, we will detail how queries can be signed such that restrictions can still be performed without invalidating the digital signature. What will be exchanged at each step between the user, ACAs and data source will be a tuple (user, source, Q, S, timestamp, Id, certif icates).

Q denotes here the actual body of the query while S denotes the modifiable signature of Q (which includes its corresponding Id and timestamp), initially computed by the user. Certificates denotes a set of tuples (ACAi, Si), for Si being ACAi's (classic) public-key signature for the tuple (user, source, Id, timestamp).

We stress that the query signature is initially computed by the user and then only updated by intermediaries. Each of them certifies Q by signing not the query body, but only its "name". We next detail the techniques for modifiable query signatures.

Relational Data and Queries

We start by considering relational data and select-projectjoin queries (also known as conjunctive queries) with nonequalities (denoted CQ = ). We then consider in Section 4.2 XML data and tree pattern queries.

We first illustrate query rewriting within this class by an example. We will assume that queries are first normalized, i.e., joins are made explicit (by variable equalities), with no variable appearing twice in query terms. And assume that one or several ACAs restrict Q, obtaining in the end the version Q ′ :

(Q ′ ) q(S, D, T ) : -patient(S, N, A), S = S ′ visit(V, S ′ , "21/01/2001", W, D), treatment(I, V ′ , T, C), V = V ′ diagnosis(D ′ , T ′ ), D = D ′ , T ′ = "bloodRelated"
Notice that two modifications occurred. First, the C-variable was projected out of the output tuples. Second, the condition that the diagnosis (D) is not of type bloodRelated was introduced.

CQ = query rewriting. The CQ = query restrictions that we consider are the following:

• add new query terms.

• introduce a join either between existing terms of the query, i.e., an equality between two variables, or between a variable and a constant.

• introduce a non-equality either between two variables which are not already marked as equal, or between a variable and a constant.

• remove a variable from the output.

It is straightforward to check that these transformations will only yield more restricted queries, since the restricted version is contained in the initial one (as a boolean query) and the output variables of the former are among the output variables of the latter.

Next, notice that we can describe a CQ = query using several collections (concerning variables, output variables, terms, equalities or non-equalities), as follows:

• C1, for query terms.

• C2, for variables.

• C3, for tuples (query term, variable, position).

• C4, for pairs of equal variables, or pairs of equal variables and constants.

• C5, for pairs of non-equal variables, or pairs of nonequal variables and constants.

• C6, for output variables. Now, assume that the user digitally signs her initial query using homomorphic signatures for its various collections, as follows:

• C1, C2, C3, C4, C5 as insert-only collections.

• C6 as a delete-only collection.

So, the query signature will consist of seven parts, each of them referring to one of the collections. Obviously, these collections can describe meaningless queries, but this is a situation that can be easily detected and poses no security threat.

If these steps are taken, then any ACA downstream can perform restrictions and then update the query signature accordingly. More specifically, this means that ACAs can only remove output nodes or introduce more conditions (terms, equalities/inequalities). They will be able to do these transformations in a persistent and confidential manner, while modifications that do not further restrict the query are not possible. We note that for the CQ = query language, delete-only sets play a lesser role in our signing approach, and in fact we could rely completely on insert-only ones (although with higher computation cost). However, delete-only sets should become necessary in more expressive SQL-style queries, for example in the presence of disjunction. We omit further details.

XML Data and Queries

We now employ similar ideas for XML data, the de facto standard for data exchange. In short, an XML document contains nested labeled elements and text, and can be viewed as a rooted, unranked tree with labeled element nodes and text (or data value) nodes. Figure 4 illustrates an XML document and its corresponding tree representation. For simplicity, we ignore other aspects such as attributes, idrefs or ordering among siblings (more details about XML can be found in [START_REF]Extensible Markup Language 1[END_REF]). XML data is often associated with schema information (such as DTDs or XSchema) which describes the possible structure of documents. For exemplification, we adopt here the Document Type Definition (in short, DTD) of [START_REF] Fan | Secure XML querying with security views[END_REF], illustrated in Figure 5, which specifies the structure of medical records. This DTD says that a hospital contains records which are either immediate children of a medicaRecords node or are found below intermediary clinicalTrial nodes (denoting records from medical trials). A patient record contains various information such as treatment and diagnosis. Some of the fields of the patient record are considered optional (denoted by the ? annotation). In particular, the document fragment of Figure 4 conforms to this specification.

XML queries. The XML query language that we consider here is essentially an extension of the most commonly used XPath fragment (namely XPath{/,[],//, * }) with (a) multiple output nodes and (b) negated patterns. By / we denote child axis navigation, by // we denote descendant axis navigation, and * denotes the wildcard label, which matches any node label. We represent such queries by patterns, as illustrated in Figures 6(a) and 6(b). Edges can be positive (representing branches that must be matched) or negative (the sub-pattern starting at a negative edge must not match). Moreover, two kinds of output nodes can be specified: nodes which are returned without their corresponding subtree in the document (denoted simple-output nodes) and nodes for which we return their entire subtree (denoted subtree-output nodes). Nodes which are not returned by the query are called non-output nodes.

We use the following graphical representation: simple edges denote child axis, double edges denote descendant axis, simple-output nodes are marked by an s annotation and subtree-output nodes are marked by a t annotation. Negative edges are annotated by ¬. The nodes with positive (resp. negative) incoming edges are also called positive (resp. negative) nodes. Obviously, output nodes can only occur in the positive parts of the query. Finally, all the edges / nodes below a negative edge are assumed negative.

Classically, the semantics of a query is the following: on the document tree, we match all the query's positive edges, we check that negative patterns cannot be matched, and the result is the tuple containing the simple-output nodes and the subtrees rooted at subtree-output nodes. We omit here formal definitions of the language and its semantics (see, for example, [START_REF] Miklau | Containment and equivalence for an XPath fragment[END_REF] and [START_REF] Benedikt | XPath leashed[END_REF]). An example of a query and its result over the previous document fragment are given in Figure 6.

XML query rewriting. We assume the following range of modifications that restrict a query: (a) add anything below a subtree-output node (i.e., positive sub-patters, output nodes and negative sub-patterns).

(b) add a positive edge below a positive edge.

(c) add a negative sub-pattern below a positive edge.

(d) remove the s annotation of a simple-output node (i.e., turning a simple-output node into a non-output one).

(e) transform the t annotation of a subtree-output node into an s annotation (i.e., the subtree rooted at that node is no longer returned).

(f) expand a positive descendant edge into a more detailed (hence less general) linear path.

(g) turn a wildcard label of a positive node into a concrete label.

For instance, the query in Figure 6(b) is a restricted version (after applying some of these transformations) of the one in Figure 6(a). Let us now rephrase the scenario of Example 1 in XML terms: Example 4.3. Let us assume that the initial query (Q) from the user (SMD) asks for the medical data of patient John Smith, including (by the descendant axis) that coming from clinical trials (Figure 6(a)). All the data below patient elements is to be returned.

Next, this query is restricted by the ACA (RMD) into Q ′ (Figure 6(b)), which has the following differences:

• it does not access the clinicalTrial parts of the record (the descendant axis is transformed into a child one)

• it limits the returned data to treatment information

• and it excludes bloodRelated diagnosis from the query result For instance, one of the policies that guided the ACA peer in applying these transformations could be the following: "Physicians who perform clinical trials cannot access clinical trials of patients with blood related diagnosis."

We can easily see that if the query modifications would be known to SMD or the Hospital, private information would be disclosed. From Q ′ alone, the Hospital cannot understand how the initial query was modified, and from the potential answers, the SMD peer cannot conclude that there were some clinical trials for that particular patient, or some blood related diagnosis information.

We next consider how such restrictions can be handled by modifiable signatures. Similar to the case of relational queries, we need to encode a query into various sets over which we enforce either delete-only or insert-only limitations. While this kind of encoding was straightforward for conjunctive queries, more work is need in the case of tree pattern queries. To this end, we first show how a model of trees with modification restrictions, namely annotated trees, can be handled. Then, we show how queries can be translated into this model.

Annotated trees. We extend the delete-only/insertonly notions to trees with nodes annotated by + and/or -, saying that insertions or deletions of children nodes may be prohibited (hereafter called annotated trees). More precisely, we consider that node labels are combined with an annotation from +, -, or both (i.e., immutable, noted ⊤). For each node, its annotation will indicate the disallowed transformations on its children set. Intuitively, -(deleteonly) for a node indicates that one cannot insert new subtrees as children; + (insert-only) that the deletion of existing children subtrees is not allowed. The absence of annotations indicates the absence of constraints. (An obvious "soundness" rule is that below a unconstrained node everything else is unconstrained.) Besides the tree modifications given by annotations, we also allow for type changes that are further restricting modifications, i.e., adding a new sign.

Next, starting from insert-only and delete-only signatures for sets, we design a signing approach for annotated trees such that one can perform allowed modifications on a signed annotated tree without affecting the authenticity of the tree (i.e., the signature can be updated accordingly) and without revealing the actual modifications. The details of this signing approach are technical but not difficult and are deferred to the Appendix. A similar approach can be employed, for instance, to +/-annotated DAGs.

Encoding queries by annotated trees. The above model takes us one step closer to tree patterns, since queries and the possible restrictions specified for this language can be exactly captured by such annotated trees. We next illus-trate the basic steps needed to encode tree pattern queries by annotated trees.

Let us ignore for now descendant edges and wildcard. Figure 7 illustrates how the core blocks of queries can be modeled as a combinations of annotated nodes.

Output properties. Since the output type of a positive node can be modified from subtree-output to simple-output and from there to non-output, we associate to each node an insert-only list in which the reserved labels t, s and n can be added. The labels denote subtree-output, simpleoutput and non-output nodes respectively. The "weakest" label present in the list will denote the output type.

Subtree-output nodes. In Figure 7(a), we illustrate how a subtree-output node can be represented by an immutable node with four intermediary children. Let L denote the list of output nodes which are children of n, T1 denote the positive patterns below n and T2 denote the negative patterns below n.

The first three intermediary nodes in the corresponding annotated tree capture these three components (indicated by the out, pos, and neg indices respectively). The fourth annotated node, type, denotes the output kind. The node for positive patterns and the one for negative patterns are annotated insert-only (more positive or negative edges may be added), while the one for output nodes is not annotated (for now, output nodes of either type can be both inserted and removed from this list of leaf nodes). Note that output nodes appear both in the insert-only node pos, together with their sub-patterns, and in the unconstrained node out, as simple leaves.

Simple-output nodes. The case of simple-output nodes is similar (Figure 7(b)). Transforming a subtree-output node into a simple-output one (i.e., moving from Figure 7(a) to Figure 7(b)) amounts to modifying the type of the one unconstrained node (out) into delete-only. After this, it is no longer possible to add new output nodes (only non-output ones can still be added), yet removing existing ones can still be done.

Negative nodes. Negative parts are easier then the positive ones, since no modifications are allowed on them. Hence, negative nodes will all be immutable. No intermediary annotated nodes are needed. Wildcard. This can be easily supported by an overall insert-only list which keeps node/label associations. A node can appear at most once in this list, and one which is not in the list is assumed labeled by wildcard.

Descendant axis. Regarding descendant axis, we need to capture the fact that a //-edge can be transformed into any (more refined) linear path. We can support such transformations as follows:

• for each pair of nodes na, n d such that na is an ancestor of n d , n d will be among the children of na in the annotated tree (i.e., in the pos and eventually out branches). This means that the annotated tree will degenerate in a DAG. By default, all the edges will now be considered //-edges.

• when we want to express a /-edge or transform a //edge into a /-edge, we can for instance insert the (parent, child) pair in an insert-only list for the entire tree.

• when a //-edge is expanded, for instance into a longer path, new descendants/ancestors will appear for some of the nodes. This will have to be reflected in their corresponding annotated nodes.

Finally, we stress that we are concerned only with valid query instances; so we ignore transformations that would result in meaningless queries which can be easily detected by analyzing the encoding. We conclude this section by noting that richer query features, such as joins, disjunction or optional edges, may be controlled similarly.

CONCLUSION AND RELATED WORK

We considered in this paper the privacy issues which are raised in distributed access control. When access policies are distributed and may depend on private details concerning the various actors involved, previous approaches fail to protect privacy. In particular, information leaks may occur during access control enforcement. Starting from homomorphic set-signing techniques, we suggested a possible implementation for both relational and semi-structured data. We focused primarily on techniques for digitally signing modifiable user queries. Future work includes the implementation and experimental evaluation of these techniques. Cryptographic signatures for sets may also prove useful in a postquery processing phase, for instance when filtering private data from answers. This is the subject of future research.

Privacy in access control has been mainly studied from a different angle, in which the user may not want to disclose her identity and her queries to the source. This is the case in private information retrieval [START_REF] Kushilevitz | Replication is NOT needed: SINGLE database, computationally-private information retrieval[END_REF][START_REF] Chor | Private information retrieval[END_REF] and in the databaseas-service paradigm [START_REF] Hacigumus | Providing database as a service[END_REF][START_REF] Damiani | Balancing confidentiality and efficiency in untrusted relational dbmss[END_REF]. A good introduction to access control models for XML and tree-like data can be found in [START_REF] Fundulaki | Specifying access control policies for XML documents with XPath[END_REF]. So far, most approaches on XML access control, such as [START_REF] Bertino | Secure and Selective Dissemination of XML Documents[END_REF][START_REF] Damiani | A Fine-Grained Access Control System for XML Documents[END_REF], consider a setting where information and access management are highly centralized. While they offer great flexibility in terms of the definition and the enforcement of access rules, they do not provide means to handle non-centralized access policies and multi-party enforcement. Many works (e.g., [START_REF] Fan | Secure XML querying with security views[END_REF][START_REF] Cho | Optimizing the Secure Evaluation of Twig Queries[END_REF]) considered query rewriting as a solution for enforcing access control over XML data. Also, the secure exchange of modifiable information has been considered before. In [START_REF] Bull | Content extraction signatures using XML digital signatures and custom transforms on-demand[END_REF], the authors introduce a framework for signing XML documents that have also predefined extraction operations. Anyone can filter out information, being able to derive a signature for selected parts of the document (by blinding the rest). Frameworks for secure data exchange in the presence of updates are presented in [START_REF] Bertino | An infrastructure for managing secure update operations on XML data[END_REF][START_REF] Koglin | An update protocol for XML documents in distributed and cooperative systems[END_REF], with the flow of data (partially) defined in advance. For instance, the limited scenario of Figure 3(a) could be supported by them. None of the works above deals with hiding the performed modifications. Data structures that don't yield anything about the history of operations performed on them have been considered in [START_REF] Naor | Anti-persistence: History independent data structures[END_REF].

by all the ACAs)Figure 2 :

 2 Figure 2: Decoupling access control and resources.

Figure 3 :

 3 Figure 3: Partially supporting the requirements.

Example 4 . 1 .

 41 Consider the following MedicalRecord relational schema: patient(ssn, name, address), visit(vID, ssn, date, wardNo, diagnosis), treatment(tID,vID, treatment, comments), diagnosis(name, type) Consider the following user query Q, which asks for "Social security number, diagnosis, treatment and other comments for patients who were treated on 21/01/2001": (Q) q(S, D, T, C) : -patient(S, N, A), S = S ′ visit(V, S ′ , "21/01/2001", W, D), treatment(I, V ′ , T, C), V = V ′

Example 4 . 2 .

 42 Revisiting Example 4.1, the restrictions can be seen as: (a) removing the C-variable from collection C6, (b) adding the diagnosis term and its variables to C1, C2 and C3 respectively, (c) adding the equality D = D ′ to C4 and (d) adding the non-equality T ′ = "bloodRelated" to C5.

Figure 5 :

 5 Figure 5: A DTD for medical records.

  The initial query (Q) (b) The restricted query (Q')

Figure 6 :

 6 Figure 6: A tree pattern query, its results, and a restricted version of this query.

Figure 7 :

 7 Figure 7: Translating queries into annotated trees

We omit here the straightforward cryptographic details needed for a full-fledged, secure protocol for these tasks.

The main idea is to use the delete-only technique to enforce a write-once memory (i.e., a bit vector). Adding an element to a collection amounts to writing it in the associated bit vector, which in turn amounts to removing some positions from the set of free vector positions.

Acknowledgments. The author would like to thank Tova Milo and Serge Abiteboul for helpful comments.

APPENDIX

Signing annotated trees. First, one can view an annotated tree as a collection of edges, i.e., pairs (parent, child). So, the same signing technique may be used for trees with homogeneous node types. For trees that mix delete-only and insert-only nodes, one could separate the delete-only regions and insert-only ones and sign each separately. A difficulty is the region frontiers, i.e. those nodes that connect a delete-only region to a insert-only one (parent and child have different types).

To deal with the above situation, a frontier node will "carry" the signature for the collection of edges forming the maximal subtree with the same update type. Hence, we need to make persistent (as long as the node exists, since it may be removable) the signing parameters (e.g. the public key) used for that collection. This means that a frontier node n will be represented as a pair (n, P Kn), and be annotated by a signature (verifiable by P Kn).

Observe that the case of an insert-only region T1 below a delete-only region T2 needs no specific handling, since the two regions must have been created by the same peer and are thus signed by the same secret function (one signature for each region).

The opposite situation (a delete-only region T1 below an insert-only region T2) needs more attention. The signing functions of the two may be different if the root of T1 has been inserted by a different party than the one who created the root of T2. When we insert T1, we insert the public-key of its signature function in the no-remove region, so that it can't be removed. We thus guarantee it cannot be removed unless T2 itself disappears. Now consider immutable nodes. They can be viewed as insert-only nodes with an extra attribute that gives the number of its children, i.e., its cardinality. Since this attribute cannot be deleted, one cannot change the cardinality. We conclude the analysis of the four possible types with unconstrained nodes. Since they can be modified at will, they are simply not taken into account when computing signatures.

Finally, consider type changes, from insert-only or deleteonly into immutable. The former case is simple. To change a insert-only node to immutable, it suffices to insert a cardinality attribute. One cannot use this trick to turn a deleteonly node to immutable, since insertion is not allowed. In this case, one can prepare this change by including in the no insert collection, besides usual elements, pairs (node, cardinality) for all possible cardinalities (there is a limited number of them for each delete-only node). We can than remove all but one (corresponding the definitive number of children) to make the collection immutable. However, by the above approach, we do not hide the previous type of the now immutable node.