Igor V Bartish
email: igor.bartish@ibot.cas.cz

Wim A Ozinga

Mark I Bartish

G W Wieger Wamelink

Stephan M Hennekens

Andreas Prinzing

Different habitats within a region contain evolutionary heritage from different epochs depending on the abiotic environment

Keywords: epoch-specific net diversification, dated phylogeny, macroevolutionary ecology, museums and cradles of diversity, paleoecology

Aim Biodiversity hot-spots are regions containing evolutionary heritage from ancient or recent geological epochs, i.e. evolutionary ʻmuseums' or ʻcradles', respectively. We hypothesize (i) there are ʻmuseums' and ʻcradles' also within regions: some species pools of particular habitat types contain angiosperm (flowering plants) lineages from ancient geological epochs, others from recent epochs; (ii) habitat-specific abiotic factors control numbers of angiosperm lineages contained from a given epoch in a

given habitat species pool.

Location The flora of the Netherlands

Methods We studied the world's largest vegetation-plot database and a new, uniquely resolved dated angiosperm phylogeny available for the Netherlands. We characterized species pools of habitat types by a novel concept: epoch-specific lineage diversities.

Results

We found that species pools of most habitat types were characterized by overor underrepresentation of lineages from at least one epoch, dating back until the origin of angiosperms. These patterns are not captured by mean lineage ages. Abiotic environments explained on average 56% and up to 75% of the variance in numbers of lineages per epoch, but with opposing effects of the same factor for different epochs.

Specifically, warm and dry habitats tend to contain lineages dating back to warm and dry epochs. Identifying lineages from sets of random time intervals rather than from a set of geological epochs significantly reduced relationships with the environment.

Main conclusions Within a region, habitat types differ significantly in the evolutionary heritage they contain from different geological epochs, and the environment controls these differences.

INTRODUCTION

Life has passed through different geological time periods (epochs) of very different dominant environments. Lineages (continuous lines of descent of species) that diversified during a particular epoch might be particularly adapted to live under the environmental conditions dominant during that epoch. An obvious example is found in lineages of succulent plants that diversified in epochs of increased aridity [START_REF] Arakaki | Contemporaneous and recent radiations of the world's major succulent plant lineages[END_REF]. Today in the expanding desert environments succulents are more apt to survive and more abundant than, for instance ferns or lycophytes, that mostly diversified in epochs dominated by moister environments [START_REF] Dimichele | Long-term stasis in ecological assemblages: Evidence from the fossil record[END_REF]. Following Stebbins' [START_REF] Stebbins | Flowering plants: evolution above the species level[END_REF] metaphor, it has been suggested that floras in certain regions may function as 'museums' of diversification of biota, containing lineages from ancient epochs, or as 'cradles' containing lineages from recent epochs. These regions are characterised respectively by a high number of either ancient or recent lineages (Hawkins et al., 2006). Such phylogenetic age structures of floras and faunas from these regions depict strong increments of the diversity of (sub) lineages that date back to the beginning or the end of the time axis, respectively. Recently, some regions were suggested to function as 'hotspots' serving both as museums and cradles of biodiversity [START_REF] Mckenna | Tropical forests are both evolutionary cradles and museums of leaf beetle diversity[END_REF][START_REF] Lopez-Pujol | Centres of plant endemism in China: Places for survival or for speciation[END_REF].

Similarly to species pools of different regions, species pools of different biomes and habitat types within a region, i.e. species present across all patches of that biome/habitat, might vary in the identity of phylogenetic lineages they represent (Prinzing et al., 2001;[START_REF] Crisp | Phylogenetic biome conservatism on a global scale[END_REF][START_REF] Bartish | Species pools along contemporary environmental gradients represent different levels of diversification[END_REF][START_REF] Kozak | Niche conservatism drives elevational diversity patterns in appalachian salamanders[END_REF]. We demonstrate in supplementary on-line material Appendix S1 that differences in lineage composition among species pools of habitat types of angiosperms (flowering plants) might well exist even within a relatively small and geologically young region under strong impact of recent anthropogenic environmental changes (see also [START_REF] Bartish | Species pools along contemporary environmental gradients represent different levels of diversification[END_REF]. Specifically, (i) different habitats within a given region may in many respects represent a similarly wide range of environments as different regions;

(ii) species often use similar habitats on different continents; (iii) lineages rarely shift habitats (ʻphylogenetic signal'); (iv) stochastic or transient ecological factors that may control the composition of local patches of habitat types might average out at the scale considered here, i.e. the entire species pools of habitat types across all local patches. However, it has never been studied whether habitat types differ in the phylogenetic age structures of the species pools they contain. For instance, do within a given region some habitat types serve as 'museums' by containing lineages that date back to earliest geological epochs, while others serve as 'cradles' containing youngest lineages? We hypothesize that this is the case. Specifically, we predict that within a given region, angiosperm lineages from a given geological epoch are overrepresented in the species pools of some habitat types and underrepresented in others. We predict also that within a given habitat type lineages from some geological epochs are overrepresented, while lineages from the other epochs are underrepresented. We stress that a habitat type within a region containing a large number of lineages from a given epoch does not equal lineages during that epoch originating in that habitat type. However, it does mean that today within this region this habitat type serves a function in maintaining the lineages from that epoch.

The presence of 'museums' or 'cradles' at the regional scale has usually been explained by their environment, such as temperature and moisture, or more generally latitude (Hawkins et al., 2006[START_REF] Svenning | High tropical net diversification drives the New World latitudinal gradient in palm (Arecaceae) species richness[END_REF]. Specific environments, such as high temperature and moisture in the tropics, have been suggested to either decrease extinction in the case of 'museum' environments (Hawkins et al., 2006;[START_REF] Kissling | Cenozoic imprints on the phylogenetic structure of palm species assemblages worldwide[END_REF][START_REF] Rolland | Faster speciation and reduced extinction in the tropics contribute to the mammalian latitudinal diversity gradient[END_REF], or increase speciation in the case of 'cradle' environments [START_REF] Weir | The latitudinal gradient in recent speciation and extinction rates of birds and mammals[END_REF][START_REF] Jansson | Global variation in diversification rates of flowering plants: Energy vs. climate change[END_REF][START_REF] Rolland | Faster speciation and reduced extinction in the tropics contribute to the mammalian latitudinal diversity gradient[END_REF]. However, a region might also be a 'museum ' (or 'cradle') because it represents an environment in which lineages from one particularly early (or recent) epoch have originated or survived. For instance, in the above example of succulent lineages their present occurrence in dry regions may correspond to origin and survival during particularly dry epochs. Dry regions hence maintain high diversity of lineages from these but not from other epochs. Here we hypothesize that also within a region differences in 'cradle'/'museum' nature of habitat types reflect differences in the abiotic environments in these habitats. More specifically, we hypothesize that the same abiotic environment, such as low soil moisture, can have a positive effect on numbers of lineages a habitat type contains from some epochs, but no effect or a negative effect on numbers of lineages contained from other epochs.

A useful test of our hypotheses can only be achieved by studying a major and phylogenetically well analysed taxon across a region of diverse habitat types being well characterised in terms of species pools. We used the currently world's largest vegetation-plot database [START_REF] Schaminée | The Dutch National Vegetation Database[END_REF] characterising a region with a high diversity of habitat types under major human impacts, i.e. the Netherlands. To test our above predictions we pooled species compositions from local habitat patches into regional species pools for different types of habitats and then quantified for each species pool the diversity of angiosperm lineages dating back to different geological epochs. We tested the relationships between abiotic characteristics of habitats and lineage diversities from the different geological epochs and from random sets of time intervals.

METHODS

Defining and characterizing habitat types

The Dutch National Vegetation Database is currently the largest database of its kind in the world, covering the whole range of vegetation types in the country [START_REF] Schaminée | The Dutch National Vegetation Database[END_REF]; http://www.synbiosys.alterra.nl). The database is registered in the Global Index of Vegetation-Plot Databases (http://www.givd.info/; ID: EU-NL-001), from which the metadata are available. The database we used contains records of 1,283 currently accepted species of angiosperms in the region after exclusion of hybrid species and subspecies from the total list of Dutch angiosperms. Exotic species were also excluded to avoid distortions of phylogenetic structure by representatives of geographically distant and evolutionarily very different floras (exotics are those that colonized the region after 1500 AD, a list can be found at http://www.milieuennatuurcompendium.nl/tabellen/nl139802a.html, they account for 16% of the total sample of species). We referenced names against the checklist of the Integrated Taxonomic Informational System: http://www.itis.gov/).

In the Dutch vegetation database, vegetation types have been hierarchically classified based on cluster analyses of species compositions of vegetation plots, a powerful way of objectively identifying habitats for plants within a region (Schaminée et al., 1995(Schaminée et al., -1999)), and independent of any phylogenetic relationships among species. The classification covers all plant habitats (including major gradients in light and nutrient availability, moisture and soil reaction) given that vegetation scientists have purposefully studied even the rarest habitats within the region rather than only the abundant ʻtypically Dutch' habitats. Specifically, we considered the level of vegetation classes, with 43 classes providing an informative but still manageable resolution of the entire spectrum of habitats representing all ecological and environmental conditions for this region. (Note that the much used habitat classification of Natura-2000 European habitat directive identifies only particularly rare habitats; these rare European Natura-2000 habitat types can be cross-linked to the complete Dutch habitat typology we used.) We used a stratified-by-habitat selection of 36,328 plots available from Turboveg (Hennekens & Schaminée, 2001). We defined the species pool of a habitat type as all species in all plots belonging to a particular habitat type following [START_REF] Bartish | Species pools along contemporary environmental gradients represent different levels of diversification[END_REF].

Justification of this approach for regional species pools has been developed in [START_REF] Zobel | Plant species coexistence: the role of historical, evolutionary and ecological factors[END_REF].

See also [START_REF] Lessard | Inferring local ecological processes amid species pool influences[END_REF] [START_REF] Cornell | What are species pools and when are they important? Annual Review of Ecology[END_REF] for recent overviews of the species pool concepts.

We also characterized each habitat type by its ground water level, light, soil reaction, soil phosphorus, and temperature conditions. As measuring abiotic environment in each plot is infeasible, we used species indicator values to infer environmental conditions, averaged across species in plots within habitats. Species indicator values have been shown to permit reliable inferences on the environmental conditions at a locality [START_REF] Ertsen | Calibrating Ellenberg indicator values for moisture, acidity, nutrient availability and salinity in the Netherlands[END_REF]Hennekens & Schaminée, 2001;[START_REF] Wamelink | Validity of Ellenberg indicator values judged from physico-chemical field measurements[END_REF]. For details of estimation of species indicator values see Appendix S2. The database used in our analyses has been registered in the Global Index of Vegetation-Plot Databases (ID: EU-00-006). We finally quantified for each habitat type the total surface of plots sampled. Specific values per habitat type are reported in Appendix S2.

Estimation of mean lineage ages of species pools of habitat types

We used the dated tree of all 1,283 Dutch angiosperm species (excluding hybrids, subspecies, and exotics) available from TreeBase ID: S13572, resolved at genus level or finer (Hermant et al., 2012) and polytomies were further resolved by phylogenetic analysis for some old genera, as explained in Appendix S3. The following analyses were conducted based on this tree. This tree still contained some polytomies and we explored their possible impact on the results by creating 100 randomly resolved trees (see Appendix S3 for details) and calculating the different dependent variables for each of these trees and correspondingly redoing the analyses 100 times. We constructed dated phylogenies for each habitat species pool and then calculated Mean Phylogenetic Distance between pairs of species in the pool using calculation in Phylocom 4.1 [START_REF] Webb | Phylocom: software for the analysis of phylogenetic community structure and trait evolution[END_REF]. Observed Mean Lineage Ages (MLA, which is Mean Phylogenetic Distance, divided by 2) of a given habitat species pool were standardized by a null expectation (ʻPhylogeny shuffle' in Phylocom 4.1) created by randomly sampling 999 times the same number of terminals from the tree of all species in the sample as: (observed age -mean null-expected age) / standard deviation of null expected age. We note that application of other null expectations available in Phylocom 4.1 resulted in similar values of our standardized parameters (results are not shown). All further analyses were based on such standardized Mean Lineage Ages (stMLA). We also estimated the significance of the observed mean lineage ages by determining their percentile position within the null expectation. In addition, we calculated stMLAs per habitat type for each of the 100 randomly resolved trees and then averaged these values within habitat types.

We note that we also explored the use of Faith's Phylogenetic Diversity PD [START_REF] Faith | Conservation evaluation and phylogenetic diversity[END_REF], calculated using ʻpd' command in Phylocom 4.1. PD was related to roughly similar present environments as stMLA (notably phosphorus), but much less so (R²=0.03), and PD required accounting for species richness as co-variable (e.g. [START_REF] Davies | Environmental predictors of global parrot (Aves: Psittaciformes) species richness and phylogenetic diversity[END_REF]. PD was hence not considered.

Lineages-through-time plots

Age structure within phylogenetic trees can be summarized as Lineages-Through-Time (LTT) plots. Log 2 -transformed numbers of lineages (branches) from a tree are calculated for specified age intervals and plotted against mean ages of these intervals. We did so for subtrees of the tree of regional species pool, each sub-tree was representing only the species present in particular habitat species pool. We reconstructed LTT plots for all 43 habitat species pools (Appendix S4) using LTTR module of Phylocom 4.1 [START_REF] Webb | Phylocom: software for the analysis of phylogenetic community structure and trait evolution[END_REF]. This module permits specifying the width of age intervals across a given dated tree and any subtree, generated from this tree by Phylocom 4.1.

Diversities of lineages of Dutch angiosperms dating back to a given epoch and contained by different habitat types

We again used the sub-trees per habitat type and selected time intervals for estimation of lineage diversities, accounting for existing knowledge about ages of geological epochs. We used ages of geological epochs from geological time scale [START_REF] Walker | Geologic time scale[END_REF] and pooled or split some of these epochs where paleoclimatic reconstructions suggested similarity between or major difference within geological epochs [START_REF] Zachos | Trends, rhythms, and aberrations in global climate 65 Ma to present[END_REF][START_REF] Dupont-Nivet | Tibetan plateau aridification linked to global cooling at the Eocene-Oligocene transition[END_REF]. We hence selected the following seven epochs: from the age of the crown node of the total tree of regional flora (164 Ma) to 126 Ma, which corresponds to diversification of angiosperms from the Late Jurassic until the middle of the Early Cretaceous; 126 Ma -100 Ma, which corresponds to the Barremian/Aptian Ages boundary until the end of the Early Cretaceous; 100 Ma -66 Ma (the Late Cretaceous); 66 Ma -33.9 Ma (the Paleocene and the Eocene); 33.9 Ma -23 Ma (the Oligocene); 23 Ma -5.3 Ma (the Miocene); 5.3 Ma -present (the Pliocene, the Pleistocene, and the Holocene). We supplemented these analyses based on seven geological epochs and their paleoenvironments by analyses of time intervals between 164 Ma and present, defined independently of geological epochs: (i) as 100 sets of seven random time intervals; (ii) as seven equal-sized time intervals (i.e. 24.3 Ma).

For each epoch and each habitat type we calculated Epoch-specific Lineage Diversities (ELDs), defined as diversity of lineages dating back to a given geological epoch within a

given habitat species pool. The index measures the proportional increase in numbers of lineages-through-time, i.e. log 2 numbers of phylogenetic branches dating back to a given epoch (log 2 number of branches at the end of the epoch minus log 2 numbers of branches at the end of the preceding epoch).

We standardized our estimates of ELDs by null-expectations for species pools of given sizes from a regional species pool. Null-expectations (ʻPhylogeny shuffle' option in Phylocom 4.1) of ELDs were computed for all species pools and all age intervals as means across 999 random samples of a given number of species from the total tree of Dutch Angiosperms. We performed these calculations using a modified version of LTTR module of Phylocom 4.1 (the code is available from MIB and will be implemented in one of further versions of Phylocom).

For each time interval in each habitat species pool we calculated differences between observed and means of null-expected ELDs, divided by standard deviation of the nullexpected ELDs. All analyses presented in the Results were based on such standardized, unbiased stELD values. We also estimated the significance of the observed ELDs for each time interval and habitat type by determining their percentile position within the null expectation. We note that, despite being standardized for species richness, high stELDs for a given epoch in general correspond to high present species richness (simultaneously accounting for all epochs and surface sampled, and excluding two outliers, results not shown). This observation further suggests that stELDs are informative about historical footprints in present diversity. We finally calculated stELDs per habitat type and epoch for each of the 100 randomly resolved trees and then averaged these values within epochs per habitat type.

Relating phylogenetic structures to the abiotic environment within habitat types

We analyzed the effects of abiotic environmental characteristics of habitat types on stMLA of the corresponding species pools. We applied multiple linear regression using as predictive variables all five environmental variables simultaneously (STATISTICA version 8; Statsoft Inc. Maisons-Alfort, France). Surface area per habitat type was used as a co-variable in all multiple regression analyses to control for possible sample size bias [START_REF] Rosenzweig | Species diversity in space and time[END_REF][START_REF] Bartish | Species pools along contemporary environmental gradients represent different levels of diversification[END_REF]. We graphically verified the assumptions of the analyses on residual distributions using predicted vs. residual and normal probability plots and found that residual distributions approached homogeneity and normality. In order to reduce multi-collinearity among predictive variables we conducted a best-subset search, using adjusted R² as a search criterion. Adjusted R² resembles the Akaike or Mallow criteria but has a goal to maximize the explained variance while accounting for the remaining degrees of freedom, not to identify a minimum set of predictor variables. We then repeated this approach and analyzed effects of abiotic characteristics of habitats on their stELDs from a given epoch. In other words, we identified how present abiotic characteristics of habitats affect the function of the corresponding habitat species pools in maintaining the diversities of lineages dating back to the given epoch. We repeated this analysis for each epoch. To summarize how much variance of stELDs can be explained by abiotic environments, we averaged the R² values from all seven epochs. We compared this to averages of the R² calculated (i) across each set of seven random time intervals, and (ii) across the seven equal sized time intervals.

RESULTS

We found that unstandardized mean lineage ages (MLA) vary among habitat species pools between 111 Ma and 131 Ma (Fig. 1(a), unstandardized values). This relatively small range might correspond to strong representation of both monocots and core-eudicots (the two most speciose clades of angiosperms) in all habitat types. Despite this relatively small range, many of the standardized MLA (stMLA) deviate from what would be expected by random for a given species richness. In most habitats, stMLA are significantly younger than expected from random distribution of MLA for a given species richness, notably in 'Bramble underscrub of woodland edges and clearings' (Fig. 1(a), standardized values, habitat type 35). In some habitat species pools stMLA are significantly older than expected by random, notably in 'Free floating Duckweeds' and 'Floating or submerged rooted plants in fresh waters' (Fig. 1(a), habitat types 1 and 5). We also found that randomly resolving the trees yielded stMLAs (averaged across all 100 randomly resolved trees) that were nearly identical to those of the non-resolved trees (r² = 0.999, see Appendix S5 for raw values). Polytomies hence did not introduce a bias.

In multiple regression analysis stMLAs of habitat species pools were strongly related with the abiotic characteristics of these habitat types (R=0.86, F=26.98, P<0.001). High stMLA of habitat types corresponded to high ground water level (t=5.30, P<0.001), high phosphorus availability (t=3.88, P<0.001), low soil pH (t=-2.40, P=0.021) and low temperature (which however was non-significant at t=-1.01, P=0.317).

The standardized diversities of lineages dating back to a particular epoch (stELD) varied strongly among habitat species pools for most geological epochs, with the only exception being a low variation for the Late Cretaceous (100 -66 Ma; Fig. 1(b)). Again, estimates of stELDs were not biased by polytomies and were very strongly correlated to averages across 100 trees that had been randomly dichotomized for all epochs, with the only exception being the last 5 Ma (r² = 0.968-0.999 for six oldest epochs, r² = 0.548 for the last 5 Ma; see Appendix S6 for stELDs values).

The overall phylogenetic age structures are much more complex than can be inferred from mean lineage ages. For instance, a habitat type can contain a species pool with significantly high diversities of lineages dating back to both ancient and recent epochs (Fig. 1 The function of a habitat to contain high diversities of lineages dating back to a particular epoch can be explained by the abiotic environmental conditions in this habitat type. We used two approaches. First, we visually compared LTT plots for the ten most dry and ten most wet habitat types (Fig. 2(a), results for all habitat types are given in Appendix S4; moisture of In the second approach, we regressed, for each epoch, lineage diversities contained by the different habitat types (stELDs, as in Fig. 1(b)) against abiotic characteristics of these habitat types. In simple regression analysis we confirmed relationships to soil moisture found in the first approach and showed that these are highly linear and hence do not only reflect the extreme effect of a few particularly old mesangiosperm lineages in aquatic habitats (Fig.

2(c))

. For lineage diversities dating back to 126 Ma and older we again found an increase with present habitat moisture, for lineage diversities dating back to 100 -126 Ma we found a decrease (Fig. 2(c)). In multiple regression analyses we included four further environmental factors (light, soil phosphorus, soil pH, temperature). Again, we found that the same environmental factor may be associated with high diversities of lineages dating back to both ancient and recent but not intermediate epochs (Table 1; note that these results were also robust to randomly resolving polytomies as reported in Appendix S9). This explains existence of habitat types that are both 'museum ' and 'cradle' in Fig. 1(b). Environmental factors were much less strongly related to lineage diversities when these were quantified per random or 'naïve', equal-sized age intervals and not based on distinct geological epochs characterized by distinct paleoenvironments (Appendix S10; references used in Supplementary Materials are cited in Appendix 1).

DISCUSSION

In this study we tested for differences in phylogenetic age structure of species pools of present habitat types from a regional flora, applying phylogenetically and ecologically highly resolved data. Our results confirm the 'museum'/'cradle' hypothesis: just like species pools of biogeographic regions, much smaller species pools of different habitat types within a region significantly differ in their phylogenetic mean ages. However, our results also show that functions of habitats go beyond the dichotomy of 'museums' and 'cradles': lineages dating back to a given geological epoch are today contained in distinct habitat types. Mean ages of incumbent lineages do not reflect these differences in representation of distinct epochs, mean age is hence not representative of the age distribution. We stress that any extant Angiosperm has an ancestor in any of the epochs considered. High diversity of lineages dating back to a particular epoch is hence not simply the result of presence of one particularly basal or recent branch of the Angiosperm tree. Instead, there are in each habitat type multiple of these major branches, each characterised by an increased number of lineages from the particular epoch.

Finding a pattern in lineage diversities that are specific to geological epochs is not surprising.

Epochs were defined by geologists among others based on speciations and extinctions, i.e. on the two processes controlling diversification. Past epochs, hence, must leave some trace in the shape of the overall phylogeny of a lineage. However, our study does not focus on the overall phylogeny. It shows that different epochs from this phylogeny are very differently represented within different habitats. Existence of such differences and explanations cannot simply result from the way epochs were defined. Finally, our results also confirm the hypothesis that present-day abiotic environments control the diversity of lineages dating back to a given geological epoch. Relationships between moisture of all 43 habitat types to diversities of lineages dating back to epochs I and II (i.e. the above lineage diversity increments standardized by present species richness, 'stELD' parameter). Habitat types belonging to the moist and dry groups presented in (a) are identified as blue/light grey and red/dark grey, respectively, intermediate habitat types (not presented in (a)) are in white. See Table 1 for multiple analyses accounting for multiple environmental variables in addition to moisture. independent of the natural or anthropogenic drivers of these constraints. In fact this similarity between past and present abiotic constraints is the ultimate cause of phylogenetic signal observed for Dutch angiosperms in their response to these abiotic constraints (Prinzing et al., 2001) We have two types of evidence that phylogenetic age structures in contemporary habitats may reflect past diversifications in similar abiotic environments. First, we found that relationships between present-day abiotic environment and the diversity of lineages dating back to particular periods became significantly less pronounced when these periods were defined as random or as 'naïve'( equal-sized) age intervals and not based on distinct geological epochs characterized by distinct environments (Appendix S10). Second, we explored whether warm or cool habitat types tended to contain lineages with high diversities dating back to globally warm or cool epochs, respectively, and whether dry or moist habitat types tended to contain high diversities of lineages dating back to globally dry or moist epochs, respectively. For this purpose we used pertinent recent paleoclimatic reconstructions available for the more recent part of the time period considered, the Cenozoic (from 66 Ma to present, [START_REF] Zachos | Trends, rhythms, and aberrations in global climate 65 Ma to present[END_REF][START_REF] Dupont-Nivet | Tibetan plateau aridification linked to global cooling at the Eocene-Oligocene transition[END_REF], and compared them with results of our regression analyses (Fig. 3). We found that our observation that warm habitat types contain high lineage diversities dating back to the Miocene indeed corresponds to warm paleoclimates during this epoch.

Moreover, the high lineage diversities dating back to the last five million years contained in cold habitats correspond to a period of considerable global cooling and extensive continental glaciations. Also, high lineage diversities contained in dark and moist habitats and dating back to the Paleocene/Eocene correspond to a period of moist climate and boreotropical vegetation in the Northern Hemisphere [START_REF] Reid | The London Clay Flora[END_REF]. In a sharp contrast, high diversities of lineages dating back to the several latest epochs (the last 34 million years),

today contained in open and dry habitats, correspond to a period of major aridification of temperate regions [START_REF] Jacobs | The origin of grass-dominated ecosystems[END_REF][START_REF] Dupont-Nivet | Tibetan plateau aridification linked to global cooling at the Eocene-Oligocene transition[END_REF].

We stress that the above considerations linking numbers of lineages from different epochs in different habitats to paleoenvironments, and mechanisms of diversification remain speculative. In particular, a relationship of present warm (or moist) environments to high diversity of lineages from warm (or moist) epochs may result from (i) increased speciation rates in warm (or moist) environments during these early epochs, (ii) increased extinction rates in later, cool (or dry) environments during the more recent epochs. The latter explanation has indeed been suggested based on paleobotanical data [START_REF] Latham | Global patterns of tree species richness in moist forests -energy-diversity theory does not account for variation in species richness[END_REF][START_REF] Willis | The role of Quaternary environmental change in plant macroevolution: the exception or the rule?[END_REF]. Acknowledging this uncertainty, we note that it is common to many studies on net diversification rates [START_REF] Quental | Diversity dynamics: molecular phylogenies need the fossil record[END_REF]. A possible solution might be to obtain data on relative speciation and extinction rates based on complete and well-resolved phylogenies, rich fossil record, and well-characterized paleoecological environments from different places across the globe [START_REF] Pennington | Introduction and synthesis: plant phylogeny and the origin of major biomes[END_REF] The data should focus not only on climatic, but also on soil characteristics of paleoenvironments, and account for different ranges and dispersal capacities of species within regions. We are not aware of such data for angiosperms. However, this uncertainty does not influence our conclusion that particular current habitat environments can maintain lineages dating back to epochs of particular paleoenvironments.

Identification of 'museums'/'cradles' among habitat types within a region can help in prioritizing conservation efforts given the limited resources available and our failure to meet the international 'biodiversity 2010' target [START_REF] Mace | Biodiversity targets after 2010[END_REF]. Habitats containing evolutionary heritage from oldest geological epochs might be considered particularly valuable and their decline would be particularly alarming. Such an approach would resemble that of phylogenetic endemism which accounts for geographic rarity of the lineages [START_REF] Rosauer | Phylogenetic endemism: a new approach for identifying geographical concentrations of evolutionary history[END_REF][START_REF] Mishler | Phylogenetic measures of biodiversity and neo-and paleo-endemism in Australian Acacia[END_REF], but requires a geographically much larger sample to be properly calibrated. Obviously, it has to be verified in each region which habitat types are to be classified as 'museums', 'cradles', or both. Habitats containing lineages that diversified in warmer epochs might today serve as a pool of species potentially still carrying adaptations to such warmer climates. Conservation of these habitats might represent an 'ecological insurance'. Although in some extreme cases such as succulent plants in dry habitats this was always obvious, in most cases we had until now no means of testing this prediction. In other habitats component lineages might be especially sensitive to climate change and face the risk of 'running out of climate space' (cf. [START_REF] Ohlemuller | Running out of climate space[END_REF]. Although speculative, this approach is equivalent to what is established practice in the conservation of the genetic heritage of wild relatives of crop species, where under a warming climate wild relatives in warm habitats have particularly high conservation value (Kremer et al., 2013). [START_REF] Zachos | Trends, rhythms, and aberrations in global climate 65 Ma to present[END_REF] and periods of moist and of arid paleoclimates in temperate regions [START_REF] Reid | The London Clay Flora[END_REF][START_REF] Dupont-Nivet | Tibetan plateau aridification linked to global cooling at the Eocene-Oligocene transition[END_REF] throughout the Cenozoic (66 Ma to present). Dashed lines depict epochs analyzed in Fig. 1 and Table 1. Note that climates from even older epochs are much less well known and hence not presented. (b) Relationships between present temperature or soil moisture of habitat types (upper and lower graph, respectively), and diversities of lineages dating back to each of the four epochs identified in (a). Relationships correspond to t-and P-values in the regression analyses reported in Table 1. Note that lineages dating back to warm or dry epochs tend to be preferentially contained in warm or dry habitat types.

CONCLUSIONS

Our findings indicate that within a given region habitats can function as 'museums' (particularly in wet habitats) or as 'cradles' (particularly in dry habitats), containing older or younger lineages, respectively. However, the classical 'museum'/'cradle' dichotomy is often far too simple and linear to realistically describe the phylogenetic structure represented in different environments within a region, and a habitat can contain lineages from very different epochs. Specifically, the results suggest that within our study region habitat types with warm or dry environments seem to contain high lineage diversity from globally warm or dry epochs during the Cenozoic. Such a function of habitats was to our knowledge not appreciated so far.

It is all the more impressive that such a function can be observed even within a region that is close to cool and moist limits of many plant lineages. The generality of this finding needs to be tested for other regions. Moreover, further research is needed to verify whether presence of lineages from the most recent epoch in some habitats corresponds to an increased ongoing production of new species.

  (b), see Appendix S7 for details). Habitat types hence can act as museums, or as cradles of evolutionary history, or as both, i.e. they contain species pools with significantly increased diversities of lineages dating back to either of the Mesozoic epochs, to either of the Neogene epochs, or to both, respectively (see examples in Fig. 1(b) and Appendix S8).

Figure 1

 1 Figure 1 Present habitat types contain different levels of evolutionary heritage (43 habitat types grouped into seven main types; habitat types are named and defined in Appendix S2). (a) Habitat types differ in mean lineage ages (MLA). Ages are unstandardized for species richness (given in Ma, on left axis, and as open vertical bars) or are richness-standardized (given as effect sizes on the right axis, and as grey vertical bars), corresponding respectively to MLA and standardized MLA (stMLA) in the text (see Methods). The horizontal grey area indicates 95% confidence interval of a null model (further details in Appendix S5). (b) Habitat types differ in diversities of lineages dating back to different epochs. Diversities are standardized by species richness ('standardized epoch-specific lineage diversity' , or stELD in the text; see Methods and further details in Appendix S6) and are represented as grey vertical bars. Epochs are defined in Ma and are indicated above each of the corresponding panels. Horizontal grey areas indicate 95% confidence intervals of epoch-specific null models. Note that diversities of lineages dating back to a given epoch are beyond null-expectations in most of the habitat types. Habitat types may act as 'museums' by containing high lineage diversities dating back to ancient epochs (defined as Mesozoic, i.e. > 66 Ma). Habitat types may act also as 'cradles' by containing high lineage diversities dating back to relatively recent epochs (Neogene and Quaternary, i.e. < 23 Ma). Multiple habitats act as both, some as neither; illustrated examples are indicated by open and coloured/shaded vertical bars (further details in Appendix S8).

Figure 2

 2 Figure2The soil moisture of habitat types is associated with a high diversity of lineages dating back to the oldest epochs. (a) Log2-transformed lineages-through-time plots for species pools from the 10 wettest habitat types (blue/light grey curves) and the 10 driest habitat types (red/dark grey curves), with moisture being inferred from ground water level. I and II indicate the most ancient and the second most ancient epochs in the evolution of angiosperms (I, between the root in the Jurassic to the Barremian/Aptian Ages boundary in the Early Cretaceous; II, until the Early/Late Cretaceous boundary). (b) Increments of log 2 richness of lineages dating back to the ends versus the beginnings of epochs I and II, richness being averaged separately across species pools of the wettest and driest habitat types. (c) Relationships between moisture of all 43 habitat types to diversities of lineages dating back to epochs I and II (i.e. the above lineage diversity increments standardized by present species richness, 'stELD' parameter). Habitat types belonging to the moist and dry groups presented in (a) are identified as blue/light grey and red/dark grey, respectively, intermediate habitat types (not presented in (a)) are in white. See Table1for multiple analyses accounting for multiple environmental variables in addition to moisture.

Figure 3

 3 Figure 3 The paleoenvironment during a given epoch matches the environment that today contains high diversity of lineages from that epoch. (a) Global paleotemperatures (as deviation from present temperatures, Zachos et al., 2001) and periods of moist and of arid

Table 1 .

 1 Relationships between diversities of lineages of habitat types dating back to a given epoch (standardized, ʻstELD' parameter), and the abiotic characteristics of these habitat types:Our results beg the question: Do phylogenetic age structures represented today in habitats of different abiotic environmental conditions reflect past diversifications in equivalent abiotic environments? Such a link may be unexpected given the recent drastic changes of habitats due to Quaternary climatic fluctuations and human impact. On the other hand, the key abiotic constraints on plant performance in present habitat types (i.e. light and nutrient availability, moisture, pH) are probably similar to those that have existed already in earlier epochs,

	light availability, temperature, ground water level, soil pH, and soil phosphorus availability
	(one of the main drivers of soil fertility). The relationships were analyzed for each of the
	seven epochs using linear multiple regressions with best subset search. Each line represents
	hence a single analysis. (See Fig. 2(c) for exemplary simple regression analyses.) Numbers
	are t-values for each independent variable included into the model; ʻ---' indicates a variable
	has been excluded from the model; R 2 indicates explained variance of the multiple regression
	model. Levels of significance: P<0.1 -#, P<0.05 -*; P<0.01 -**; P<0.001 -***. Significant
	(P<0.05) associations are in bold.
	Epoch	Effect on diversities of lineages dating back to that epoch (t, P) Total model
	(Ma)						R 2 , P
		Light	Tempe-	Ground	Soil pH Soil
			rature	water level		phosphorus
	164 -126	---	-1.32	4.64***	-1.07	4.04***	0.75***
	126 -100	---	1.38	-5.93***	---	-1.36	0.68***
	100 -66	2.50*	---	---	-2.39*	---	0.22*
	66 -33.9	-4.59***	---	4.96***	---	-4.61***	0.41***
	33.9 -23	2.23*	---	-1.81#	2.50*	-1.65	0.59***
	23 -5.3	---	3.05**	-2.81**	2.11*	---	0.60***
	5.3 -0	7.18***	-1.99#	-4.98***	1.64	---	0.64***

ACKNOWLEDGMENTS I.V.B. was supported by J. E. Purkyně Fellowship of Czech Republic, W.A.O. by the Dutch Science Foundation (NWO Biodiversity Works) and the European Science Foundation (ASSEMBLE), and A.P. by an 'ATIP' grant from the Centre National de la Recherche Scientifique. I.V.B., W.A.O. and A.P. were supported by an sDiv grant for the German Center of Integrative Biodiversity Research (iDiv). Hans de Kroon, Conrad Labandeira and John Wiens provided useful comments on the manuscript.


Nesrine Kaaniche
email: nesrine.kaaniche@telecom-sudparis.eu

Maryline Laurent
email: maryline.laurent@telecom-sudparis.eu

SHoPS: Set Homomorphic Proof of Data Possession Scheme in Cloud Storage Applications

The prospect of outsourcing an increasing amount of data to a third party and the abstract nature of the cloud promote the proliferation of security and privacy challenges, namely, the remote data possession checking. This paper addresses this security concern, while supporting the verification of several data blocks outsourced across multiple storing nodes. We propose a new set homomorphic proof of data possession, called SHoPS, supporting the verification of aggregated proofs. It proposes a deterministic Proof of Data Possession (PDP) scheme based on interactive proof protocols. Our approach has several advantages. First, it supports public verifiability where the data owner delegates the verification process to another entity, thus releasing him from the burden of periodical verifications. Second, it allows the aggregation of several proofs and the verification of a subset of data files' proofs while providing an attractive communication overhead.

I. INTRODUCTION

The explosive growth of data continues to rise the demand for new storage and network capacities, along with an increasing need for more cost effective architectures [START_REF] Gantz | The digital universe in 2020: Big data, bigger digital shadows, and biggest growth in the far east[END_REF]. As such, recent years have witnessed the trend of leveraging cloud data storage, since it provides efficient remote storage services in a pay per use business model. However, these promising data storage services bring many challenging design issues, considerably due to the loss of control on outsourced data. That is, cloud data are often subject to a large number of attack vectors and the responsibility of securely managing these outsourced data is splitting across multiple storage capacities. Nonetheless, in order to reduce operating costs and save storage capacities, dishonest providers might intentionally slight these replication procedures, resulting in unrecoverable data errors or even data loss. Even when cloud providers implement a fault tolerant policy, clients have no technical means of verifying that their files are not vulnerable, for instance, to drive-crashes. There is an implementation of remote data checking at the three following levels:

(1) between a client and a CSP -a cloud client should have an efficient way to perform periodical integrity verifications, without keeping the data locally. This client's concern is magnified by his constrained storage and computation capabilities and the large size of outsourced data.

(2) within a CSP -for the CSP to check the integrity of data blocks stored across multiple storage nodes, in order to mitigate byzantine failures and drive-crashes.

(3) between two CSPs -in the case of the cloud of clouds scenarios, where data are divided on different cloud infrastructures. Therefore, a CSP, through its cloud gate, should periodically verify the authenticity of data blocks hosted by another cloud platform. Many approaches have been proposed, in order to ensure remote data checking [START_REF] Ateniese | Provable data possession at untrusted stores[END_REF], [START_REF] Ateniese | Remote data checking using provable data possession[END_REF], [START_REF] Juels | Pors: proofs of retrievability for large files[END_REF], [START_REF] Ateniese | Proofs of storage from homomorphic identification protocols[END_REF], [START_REF] Dodis | Proofs of retrievability via hardness amplification[END_REF], [START_REF] Bowers | How to tell if your cloud files are vulnerable to drive crashes[END_REF], [START_REF] Van Dijk | Hourglass schemes: how to prove that cloud files are encrypted[END_REF]. These schemes are called Provable Data Possession PDP schemes. Under different security models, several schemes ensure integrity verifications of stored data on untrusted remote servers. They are designed to guarantee several requirements, namely lightweight and robust verification, computation efficiency and constant communication cost. These PDP techniques are widely analyzed into two categories, according to the role of the verifier: private verifiability, where only the data owner can verify the server's data possession, and public verifiability, where any authorized entity can perform the verification procedure.

In this paper, we present SHoPS, a novel Set-Homomorphic Proof of data possession Scheme, supporting the 3 levels of data verification. That is, stored across multiple storage nodes, SHoPS takes advantage of the computation and storage capabilities of the storage nodes. Each node has to provide proofs of local data block sets. Then, the cloud gate is responsible for performing operations on received proofs, while preserving the authenticity of the resulting proof. Indeed, we introduce the set homomorphism property, as our scheme allows verifying sets in a way that any authorized verifier can check the union of two proof sets, while considering the whole data file, or the intersection between two data blocks, while checking integrity proofs over versions of logging files, as conversations on social networks. In addition, in the key role of public verifiability and the privacy preservation support, our proposed scheme addresses the issue of provable data possession in cloud storage environments, following three substantial aspects: security level, public verifiability and performances. The remainder of this paper is organized as follows. First, Section II describes the state of the art of existing PDP schemes. Then, Section III gives a SHoPS overview and provides the security assumptions. Section IV presents our contribution and Section V gives a brief security analysis. Finally, a performance evaluation of the proposed scheme is given before concluding in Section VII.

II. REQUIREMENT ANALYSIS & RELATED WORK

The Proof of Data Possession is a challenge response protocol enabling a client to check whether a file data D stored on a remote cloud server is available in its original form. The simplest solution to design a PDP scheme is based on a hash function H. That is, the client pre-calculates k random challenges c i , i ∈ {1, k} and computes the corresponding proofs, p i = H(c i ||D). During the challenging procedure, the client sends c i to the server which computes p i = H(c i ||D). If the comparison holds, the client assumes that the server preserves the correct data file. This solution is concretely unfeasible because the client can verify the authenticity of the files on the server only k times. Additionally, stored across multiple storage nodes, each node has to compute the related possession proof, based on a received challenge. As such, the aggregation process results in the removal of some redundant proofs transmitted from different nodes, in order to minimize the communication latency. Generally, the processing overhead at the client side is also reduced, but the new proof is longer than the original generated proofs. As such, to guarantee the authenticity of the resulting proof while avoiding the shortcuts of the classical forwarding, we propose a new aggregate proof scheme, using set-homomorphic properties.

A. Requirement Analysis

The design of our protocol is motivated by providing support of both robustness and efficiency. SHoPS has to fulfill the following requirements:

• Public verifiabilitythe public verification is an important requirement, allowing an authorized entity to verify the correctness of data. Thus, the data owner is relieved from the burden of storage and computation. • Unlimited challengesthe number of challenges should be unlimited. This condition is considered as important to the efficiency of a PDP scheme. • Low computation complexityon one hand, for scalability reasons, the amount of computation at the cloud server should be minimized, as it may be involved in concurrent interactions. On the other hand, the proposed scheme should also have low processing complexity, at the client side. • Low communication overheadan efficient PDP should minimize the usage of bandwidth. • Low storage costthe limited storage capacities of the user devices has a critical importance in designing our solution. As such, low storage cost at the client side is highly recommended.

B. Related Work

The notion of PDP has been introduced by Ateniese et al. in [START_REF] Ateniese | Provable data possession at untrusted stores[END_REF]. That is, the client divides the file data D into blocks and creates one tag for each block b i as T i,bi = (H(W i )g bi ) d )modN , where N is an RSA modulus, g is a public parameter, d is the secret key of the data owner and H(W i ) is a random value. The scheme is efficient as there is no need to retrieve data for the verification of data possession. The main drawbacks are computation complexity due to the usage of RSA numbers and the private verifiability feature. In [START_REF] Ateniese | Remote data checking using provable data possession[END_REF], Ateniese et al. propose a publicly verifiable version, which allows any entity to challenge the cloud server. However, [START_REF] Ateniese | Remote data checking using provable data possession[END_REF] is insecure against replay attacks in dynamic scenarios because of the dependencies of index blocks in proof generation and the lack of homomorphism property in the verification procedure. Juels et al. [START_REF] Juels | Pors: proofs of retrievability for large files[END_REF] introduce a method to detect unauthorized changes of stored data by adding sentinels in the original data. Their scheme, called Proof Of Retrievability (POR), does not support public verifiability. In addition, only a fixed number of challenges is allowed. On the basis of [START_REF] Juels | Pors: proofs of retrievability for large files[END_REF], Shacham et al. [START_REF] Shacham | Compact proofs of retrievability[END_REF] propose an improved scheme to realize public data possession verification based on bilinear signature. However, the number of authentication is proportional to the number of data blocks, and the proposed technique does not prevent from leakage of data blocks. Recently, in [START_REF] Bowers | How to tell if your cloud files are vulnerable to drive crashes[END_REF], Bowers et al. provide a different formulation of the threats that cloud users face. That is, RAFT proposes an approach confirming data redundancy on storage systems, based on a time measure function. The main disadvantages of this scheme are the communication cost depending on the number of blocks in the challenging request, and the important storage cost. The authors exposed two verification approaches. First, they propose a private verification scheme to check the exactitude of server responses based on a local copy of data. While this option may efficiently work for some scenarios, it is restrictive in many cases as it undermines much of the benefits of cloud outsourcing. Second, to improve storage capacity, they refer to the Merkle Tree signature. Thus, this technique also requires the use of a secret for each data file. To theoretically evaluate the performances of SHoPS, we compare, in Table I, our protocol with four of the most closelyrelated schemes [START_REF] Ateniese | Provable data possession at untrusted stores[END_REF], [START_REF] Dodis | Proofs of retrievability via hardness amplification[END_REF], [START_REF] Shacham | Compact proofs of retrievability[END_REF], [START_REF] Erway | Dynamic provable data possession[END_REF], to our context, in terms of bandwidth, computation and storage costs. Table I shows that none of the presented schemes does cover the totality of the fixed requirements, in Section II-A.

Metrics [1] [7] [14] [8] SHoPS Nb. of chall. fixed ∞ ∞ ∞ ∞ Public verif Yes No Yes No Yes CSP CPU cost O(1) O(n) O(n) O(logn) O(logn) User CPU cost O(1) O(n) O(n) O(logn) O(nlogn) Band. cost O(1) O(1) O(l) O(l) O(n) Storage cost O(1) O(1) O(1) O(1) O(1)

III. MODEL DESCRIPTION A. SHoPS Overview

SHoPS introduces three participating entities: the client, the authorized user and the cloud service provider. SHoPS considers that each data file is divided into blocks, and each block B into q subblocks, where q is a system parameter. Each subblock is represented by a single element of the multiplicative group G 2 . Our single data block proof scheme is made up of five algorithms, on the basis of two phases. During the first phase, the system initialization procedures are executed. This phase is performed once when the file is uploaded.

• gen : {1} λ → K pub 2 × K pr × G 2 2q-1
-given a security parameter λ, this algorithm outputs the data owner public and secret keys (pk, pk, sk), and a set of public credentials, with respect to the Diffie-Hellman Exponent assumption.

• stp : 2 M ×G 2 q → G 2 -given a data block B i ∈ {0, 1} * and the public key pk, the setup algorithm generates the corresponding accumulator {B i , i }, where i ∈ {1, • • • , n}, and n is the number of blocks of a given data file. The second phase occurs when the verifier wants to check the authenticity of a given data block file.

• clg : Z p * × Z p * → C
-this algorithm is computed by the verifier and takes as input the number of data blocks q. It generates a challenge c ∈ C consisting on a random block index and the public key element pk hidden with a random nonce η as c = (i, pk η ).

• prf : K pub ×2 M ×C → P -the prf algorithm computes the server's response P = (σ 1 , σ 2 ) to a challenge, using the encoded file blocks stored on the server disks.

In the following, we denote the algorithm that calculates the second element of the proof σ 2 , by prf 2 . That is, we have P = prf(pk, B, c) = {σ 1 , prf 2 (B, c)}, where B is the related data block and c represents the challenge. • vrf : P × K pub 2 → {0, 1} -a verification function for the cloud server's response P , where 1 denotes accept, i.e., the client has successfully verified correct storage by the server. Conversely, 0 denotes reject. The difference between SHoPS and traditional proof schemes is that the generation of the possession proof operates on sets of data blocks in 2 M , instead of operating in data blocks in M. Our choice is mainly motivated by proofs' authenticity, malleability concerns and energy efficiency while applying proof aggregation, as described in Section II. For instance, taking advantage of the storage and processing capabilities of the storing nodes, SHoPS saves energy within the CSP by distributing the computation over multiple nodes. In fact, each node provides proofs of local data block sets. This is to make applicable, a resulting proof over sets of data blocks, satisfying several needs, such as, proofs aggregation. Supporting the public verifiability, SHoPS allows an implementation of remote data checking at the three networking interfaces, namely, the client-CSP interface, the CSP-storing nodes interface and between two CSPs interface. This ensures the flexibility of SHoPS application and enables fulfilling each verifier request. This verifier can be:

(1) a data owner, or an authorized verifier, challenging his provider for a data possession proof. The proof aggregation, presented by the union of several data blocks proofs, is an interesting feature, as it allows a unique verification per file and ensures energy efficiency at the client side.

(2) a CSP gate challenging the storing nodes. As the operations on proof' sets are not limited to the aggregation of proofs, the intersection is important to detect byzantine failures at the storing nodes.

(3) a CSP challenging another CSP, in the case of interleaved clouds. The CSP may ask the hosting cloud to provide an aggregated proof or the intersection between two history log files of complex trade systems. In addition, the subset operator may interest the CSP verifier to check the correctness of replicated data hosted on remote servers. In the following, we refer to the proof aggregation, every set-operation over multiple proofs, namely, the union, the intersection and the inclusion operator.

Definition 3.1: Set-Homomorphic based Proof -We consider a message space M, a proof space P, a private key space K pr and a public key space K pub . A set homomorphic based proof scheme is defined as follows. There exist two operations such as: : P × P → P and : K pub × K pub → K pub , that satisfy the homomorphism and the correctness properties, for a set operation • for any messages B i and B j in 2 M . -Homomorphism:

prf 2 (B i • B j , c) = prf 2 (B i , c) prf 2 (B j , c) (1)
-Correctness:

vrf(prf(B i • B j , c), pk, pk) = vrf(prf(B i , c), pk, pk) ∧ vrf(prf(B j , c), pk, pk) (2)
We define SHoPS = {gen, stp, clg, prf, vrf, agg}, where the algorithm agg : P × P → P returns an aggregate proof as:

agg(prf 2 (B i , c); prf 2 (B j , c)) = prf 2 (B i , c) prf 2 (B j , c) (3)

B. Complexity Assumptions

Let G 1 and G 2 be two cyclic multiplicative groups of the same prime order p. An admissible symmetric pairing function ê from G 1 × G 1 in G 2 has to be bilinear, non degenerate and efficiently computable [START_REF] Regan | Minimum-complexity pairing functions[END_REF], [START_REF] Ratna | Pairing-based cryptographic protocols : A survey[END_REF].

q-Diffie Hellman Exponent Problem (q-DHE) -Let G be a group of a prime order p, and g is a generator of G. The q-DHE problem is, given a tuple of elements

(g, g 1 , • • • , g q , g q+2 , • • • , g 2q ), such that g i = g α i , where i ∈ {1, • • • , q, q+2, • • • , 2q} and α R ← -Z p ,
there is no efficient probabilistic algorithm A qDHE that can compute the missing group element g q+1 = g α q+1 . Computational Diffie Hellman Assumption (CDH) -Let G be a group of a prime order p, and g is a generator of G. The CDH problem is, given the tuple of elements (g, g a , g b ), where {a, b} R ← -Z p , there is no efficient probabilistic algorithm A CDH that computes g ab .

In the following, we denote by two elements multiplication belonging to a multiplicative group.

IV. SHOPS: A NEW SET HOMOMORPHIC PDP SCHEME

SHoPS is based on techniques closely related to the wellknown Pederson commitment scheme [START_REF] Pedersen | Non-interactive and information-theoretic secure verifiable secret sharing[END_REF]. That is, we extend the Pederson scheme to obtain a kind of a generalized commitment, in a subblock-index manner, providing fault-tolerance stateless verification. As such, for each verification session, the verifier generates a new pseudo random value and new index challenge position of the considered data file block, thus making messages personalized for each session. Additionally, we propose two verification processes. The first scheme restricts the verification to the data owner using only his private key. The second applies when the verification is performed using public credentials. This is inspired by the Boneh-Gentry-Waters (BGW) broadcast encryption system [START_REF] Boneh | Collusion resistant broadcast encryption with short ciphertexts and private keys[END_REF]. The public key consists on a sequence of group elements (g,

g 1 , • • • , g q , g q+2 , • • • , g 2q ), where g i = g α i
, defined upon the bilinear Diffie-Hellman exponent assumption.

A. Single Data Block SHoPS

The single data block proof is a PDP scheme restricted to a single block. The proofs correspond to all subblocks of a data block. In the following, we provide a detailed description of the steps, introduced in Section III, that are conducted in each of the two aforementioned phases. The gen and stp Algorithm 1 gen procedure 1: Input: system security parameter (ξ) 2: Output: public keys (pk, pk), master secret key pr and public parameters param = {g i } 1≤i≤2q;i =q+1 2) prf procedure: The prf, executed by the server, has to generate a valid proof of data possession of a given data block B i . That is, in his response, the server has to provide a new valid accumulator using the random η sent by the client. In our construction, the prf is presented by Algorithm 3. For the sake of consistency, we suppose that the server possesses a version of the data block file which is potentially altered. Hereafter, this version is denoted by Bi .

Algorithm 3 prf procedure 1: Input: File data block (B i ), public keys (pk, pk), the public parameters param and the challenge c = (k, pk η ) 2: Output:

Proof P = (σ 1 , σ 2 ) 3: σ 1 ← ( pk η ) π i,k ; 4: ˆ i = 1; 5: for all j ∈ [1 . . . q] do 6: if j = k then 7: ˆ i ← ˆ i * g πi,j q+1-j+k ; 8:
end if 9: end for 10: σ 2 ← ˆ i ; 11: return (σ 1 , σ 2 )

3) vrf procedure: In this section, we first present the public verification correctness. Then, we introduce the private verification process, which restricts the verification to the data owner.

Public Single Data Block Verification-: An authorized verifier checks the correctness of the server response, based on public parameters. It is worth noticing that the client does not store any additional information for the proof verification. That is, the verification procedure makes only use of param. The verifier checks the following equality, using the random secret η, the challenge c, and the server response P = (σ 1 , σ 2 ), as presented in Equation 4.

[ê(g k , i )ê(pk, σ 2 ) -1 ] η ê(g, σ 1 ) -1 = 1 (4)
If the equality holds, the verifier has a proof that the data block B i exists and that it has not been altered. Proof: Having received (σ 1 , σ 2 ) from the cloud, the verifier first calculates ê(pk, σ 2 ), using the public key of the data owner pk. Then, he computes ê(g k , i ). Hereafter, based on the random nonce η, the verifier checks that [ê(g k , i )ê(pk, σ 2 )

-1 ] η is equal to ê(g, σ 1 ) as:

[ê(g k , i )ê(pk, σ 2 ) -1 ] η = [ê(g α k , q j=1 g πi,j q+1-j s ) ê(g s , q j=1;j =k g πi,j q+1-j+k ) -1 ] η = [ê(g α k , g q j=1
πi,j * α q+1-j s ) ê(g s , g q j=1;j =k πi,j * α q+1-j+k

) -1 ] η = [ ê(g α k ,g q j=1 π i,j * α q+1-j s ) ê(g s ,g q j=1;j =k π i,j * α q+1-j+k ) ] η = [ ê(g,g s * q j=1 π i,j * α q+1-j+k ) ê(g,g s * q j=1;j =k π i,j * α q+1-j+k ) ] η = [ ê(g,gq+1 s * π i,k g s * q j=1,j =k π i,j * α q+1-j+k ) ê(g,g s * q j=1;j =k π i,j * α q+1-j+k ) ] η = [ ê(g,g s * q j=1,j =k π i,j * α q+1-j+k )ê(g,gq+1 s * π i,k ) ê(g,g s * q j=1;j =k π i,j * α q+1-j+k ) ] η = ê(g, g q+1 s * π i,k ) η = ê(g, g q+1 s * η * π i,k ) = ê(g, σ 1 )
This proves the correctness of the verification step (i.e., Bi = B i ). The non-singularity of the pairing function allows to state that Equation 4 is true if, and only if Bi = B i . Private Single Data Block Verification-: SHoPS proposes a lightweight private verification variant, relying on the private key of the data owner. For this purpose, we squeeze the proposed checking algorithm, presented in Equation 4, in order to support only two pairing functions computation. As such the private verification of a single data block B i is as follows:

ê(g k η , i ) ê(g, σ 1 σ 2 sη ) -1 = 1 (5)
Similarly, we prove the correctness of private single data block verification.

B. Set-Homomorphic Properties of the proposed Scheme

In this section, we extend the design of the data block elementary checking, in order to support subsets of data blocks. That is, the verifier requests the cloud for data correctness proofs, while considering a sequence of set-homomorphism properties. For ease of presentation, we prove the different properties, using two different data blocks B i and B j . Our operations can be extended easily to support multiple data blocks checking.

1) Set-Union Operator: In order to prove that our scheme is set-homomorphic with regard to the union operator, we use the received proofs prf(c, B i ) and prf(c, B j ) corresponding to B i and B j , respectively, to express prf(c, B i ∪ B j ), based on the same challenge c. Lemma 4.2: For every data block B i and B j , the union operator is defined as:

B i ∪ B j = B i + B j -B i ∩ B j
To this purpose, we first express Bi∪Bj , using Bi and Bj , as follows.

Lemma 4.3: For every data blocks B i = {π i,1 , • • • , π i,q } and B j = {π j,1 , • • • , π j,q }, where π i,k ∈ 2 M and 1 ≤ k ≤ q; and given the accumulators presented in Algorithm 3, the union accumulator is such that : Bi∪Bj = lcm( Bi , Bj )

Proof: The computation of Bi∪Bj , is performed as follows:

Bi∪Bj = π k,l ∈Bi∪Bj ;l∈[1,q];k∈{i,j} g π k,l q+1-l pr = lcm( π i,l ∈Bi;l∈[1,q] g pr * π i,l q+1-l , π j,l ∈Bj ;l∈[1,q] g pr * π j,l q+1-l ) = lcm( Bi , Bj )
To compute the least common multiple of B i and B j , we use the relation between gcd and lcm, as: gcd( Bi , Bj ) * lcm( Bi , Bj ) = Bi Bj . In the sequel, we have:

Bi∪Bj = lcm( Bi , Bj ) = Bi Bj gcd( Bi , Bj ) (6)
For instance, using the Bézout's lemma, there exist unique integers a and b, such that:

a Bi + b Bj = gcd( Bi , Bj ) (7)
As such, using the Equation 6and Equation 7, we find the lcm of the two data blocks B i and B j as follows:

Bi∪Bj = lcm( Bi , Bj ) = Bi Bj a Bi + b Bj (8)
Therefore, we obtain the proof of the lemma 4.3. Theorem 4.4: Set-Homomorphism Property -Union Operator SHoPS considers the algorithms clg, prf and vrf defined above. Let agg be the algorithm, presented in Equation 1, such that • is the set union operator, as follows.

prf 2 (B i • B j , c) = prf 2 (B i , c) prf 2 (B j , c) = prf 2 (B i , c) prf 2 (B j , c)(a * prf 2 (B i , c) + b * prf 2 (B j , c)) -1
(9) where a and b satisfy :

aprf 2 (B i , c) + bprf 2 (B j , c) = gcd(prf 2 (B i , c), prf 2 (B j , c))
Proof: We prove that SHoPS fulfills the homomorphism and correctness properties.

-Proof of Homomorphism :

We know that aprf 2 (B i , c) + bprf 2 (B j , c) = a ˆ Bi + b ˆ Bj . Thus, we can write: b ˆ -1 Bi + a ˆ -1 Bj = ˆ -1
Bi∪Bj . Consequently, using Equation 8, we can write that:

a ˆ Bi + b ˆ Bj = (a ˆ Bi + b ˆ Bj ) ˆ -1 Bi ˆ -1 Bj ˆ -1 Bi ˆ -1 Bj = a ˆ Bi ˆ -1 Bi ˆ -1 Bj + b ˆ Bj ˆ -1 Bi ˆ -1 Bj ˆ -1 Bi ˆ -1 Bj = a ˆ -1 Bj + b ˆ -1 Bi ˆ -1 Bi ˆ -1 Bj = ˆ -1 Bi∪Bj ˆ Bi ˆ Bj
As such, we demonstrate that

ˆ -1 Bi∪Bj = a ˆ B i +b ˆ B j ˆ B i ˆ B j
. This proves that our framework fulfills the homomorphism property.

-Proof of Correctness: We show that an authorized challenger may check the correctness of two different data blocks B i and B j , using an aggregate proof prf 2 (B i ∪ B j , c), based on a challenge c = (k, pk η ). We suppose that π i,k = π j,k . That is, as presented in Equation 2, the correctness of SHoPS is that vrf(prf(pk, B i ∪ B j ), pk, pk) = 1. We have:

ê(g k , Bi∪Bj )ê(pk, σ 2,Bi∪Bj ) -1 = ê(g α k , Bi∪Bj ) ê(g pr , ˆ Bi∪Bj ) = ê(g α k , B i B j gcd( B i , B j ) ) ê(g s , ˆ B i ˆ B j gcd( ˆ B i , ˆ B j ) ) = ê(g, q l=1 g π i,l q+1-l+k s q l=1 g π j,l q+1-l+k s gcd( B i , B j ) α k ) ê(g, q l=1;l =k g sπ i,l q+1-l+k q l=1;l =k g sπ j,l q+1-l+k gcd( ˆ B i , ˆ B j ) s ) = ê(g, g q+1 sπ i,k q l=1;l =k g sπ i,l q+1-l+k g q+1 sπ i,k q l=1;l =k g sπ j,l q+1-l+k gcd( B i , B j ) α k ) ê(g, q l=1;l =k g sπ i,l q+1-l+k q l=1;l =k g sπ j,l q+1-l+k gcd( ˆ B i , ˆ B j ) s ) = ê(g, ˆ s B i ˆ s B i gcd( B i , B j ) α k )ê(g,gq+1 sπ i,k gq+1 sπ j,k ) ê(g, ˆ s B i ˆ s B i gcd( ˆ B i , ˆ B j ) s ) = ê(g, g q+1 sπ i,k g q+1 sπ j,k )
As such, based on the random challenge η, we can write [ê(g k , Bi∪Bj )ê(pk, σ 2,Bi∪Bj )

-1 ] η as follows:

= [ê(g, g q+1 sπ i,k g q+1 sπ j,k )] η = ê(g, g q+1 sπ i,k η g q+1 sπ j,k η ) = ê(g, σ 1,Bi∪Bj )
2) Set-Inclusion Operator: In this section, we prove that SHoPS is homomorphic with respect to the set-inclusion operator.

Theorem 4.5: Set-Homomorphism Property -Subset Operator SHoPS considers the algorithms clg, prf and vrf defined above. Let agg be the algorithm, presented in Equation 1, such that • is the set inclusion operator, as follows.

prf 2 (B i • B j , c) = prf 2 (B i , c) prf 2 (B j , c) = prf 2 (B j , c) prf 2 (B i , c) -1 (10)
where B i and B j are two data blocks of ∈ 2 M , and B i ⊂ B j . We prove the homomorphism and the correctness of SHoPS with respect to the set inclusion operator. Proof: Let B i and B j be two data blocks, where B i ⊂ B j , and k is the index challenge sent by the verifier.

-Proof of Homomorphism: We have prf 2 (B j , c) = ˆ Bj . This can write, where l = k:

ˆ Bj = π j,l ∈Bj ,l∈[1,q] g sπ j,l q+1-l+k = π j,l ∈Bj \Bi,l∈[1,q] g sπ j,l q+1-l+k π i,l ∈Bi,l∈[1,q] g sπ i,l q+1-l+k
As such, we show that π j,l ∈Bj \Bi,l∈ [1,q];l =k g sπ j,l q+1-l+k = π j,l ∈Bj ,l∈ [1,q];l =k g sπ j,l q+1-l+k π i,l ∈Bi,l∈ [1,q];l =k g -sπ i,l l-q-1-k (11) Using Equation 11, we demonstrate that SHoPS is homomorphic with respect to the set-inclusion operator:

prf 2 (B j \ B i , c) = π j,l ∈Bj \Bi,l∈[1,q];l =k g π j,l q+1-l+k = ˆ Bj ˆ -1 Bi = prf 2 (B j , c) prf 2 (B i , c) -1 -Proof of Correctness : The correctness of SHoPS is that vrf(pk, pk, prf 2 (B j \ B i , c)) = 1, where B i ⊂ B j . [ ê(g k , Bj \Bi ) ê(pk, σ 2,Bj \Bi ) ] η = [ ê(g α k , -1 Bi Bj ) ê(g pr , ˆ -1 Bi ˆ Bj ) ] η = [ ê(g, σ 1,Bi η -1 σ 1,Bj η -1 ˆ -s Bi ˆ s Bj ) ê(g, ˆ -s Bi ˆ s Bj ) ] η = [ ê(g, σ 1,Bi η -1 σ 1,Bj η -1 )ê(g, ˆ -s Bi ˆ s Bj ) ê(g, ˆ -s Bi ˆ s Bj ) ] η = ê(g, σ 1,Bi η -1 σ 1,Bj η -1 ) η = ê(g, σ 1,Bj \Bi )
Therefore, we obtain the proof of correctness of Theorem 4.5.

3) Set-Intersection Operator: We proved that SHoPS allows the generation of aggregate proofs with respect to the subset and the union operators. That is, we extend our discussion, using the relations between these two set operators. For instance, based on Theorem 4.4 and Theorem 4.5, we demonstrate that SHoPS is set-homomorphic with respect to the intersection operator. Note that the intersection operation between B i and B j may be expressed in terms of the union and the set difference operators as follows.

B i ∩ B j = (((B i ∪ B j ) \ (B i \ B j )) \ (B j \ B i )) (12)
V. SECURITY DISCUSSION

In this section, we present a brief security discussion of SHoPS, based on two different threat models.

A. Threat Model

For our technique to be efficient in cloud storage applications, we have to consider realistic threat models. We first point out the case of a lazy cloud service provider. In such cases, the storage server wants to reduce its resources consumption. That is, this lazy server claims doing the requested computations to provide responses to the challenger. Second, we consider the case of a malicious verifier that intends to get information about the outsourced data of the data owner. The fact that the verification process can be performed using public elements makes it possible for malicious clients to gain information about files stored on the untrusted servers.

B. Security and Privacy Discussion

We describe the security of SHoPS, using a game that captures the data correctness property. In fact, this game consists in a lazy storage server, as an adversary, that attempts to construct a valid proof without processing the original data block as follows. When the verifier wants to check the server's possession of a data block, he sends a random query (c g , k g ) to the adversary.

• Challenge -the verifier requests the adversary to provide a valid proof of the requested data block, determined by a random challenge c g and the index k g . • ForgeProof -without processing on the original data file, the adversary tries to compute a proof (σ * 1 , σ * 2 ), the challenge c g , and the public credentials params. The adversary wins the data possession game, if the vrf procedure returns 1. According to the standard definition of proof systems, SHoPS has to fulfill two security requirements: completeness and soundness of verification.

-Soundness of Verification -The soundness means that it is infeasible to confound the verifier to accept false proofs (σ * 1 , σ * 2 ). That is, even if a collusion is attempted, the CSP cannot prove its possession. The soundness of our proposition is relatively close to the Data Possession Game. Hence, the soundness meets the correctness of verification (Equation 4 and Equation 5), while considering the non singularity of the pairing functions. This property prevents from forging the soundness of verification of our protocol. In order to prove the nonexistence of a fraudulent server prover, we assume that there is a knowledge extractor algorithm Ψ, which gets the public parameters as input, and then attempts to break the CDH assumption in G 2 . The Ψ algorithm interacts as follows: Learning 1the first learning only relies on the data owner public key pk = g sk as input. Ψ tries to get knowledge of the client secret key sk. That is, the extractor algorithm Ψ picks at random r i ∈ R [0, R[, where i ∈ Z p and computes g ri . For each r i , Ψ checks whether the comparison holds between pk and g ri . Based on our assumption, Ψ cannot extract the secret key of the client with noticeable probability. Learning 2the input of the second learning is the tuple (pk, pk, g). The algorithm attempts to extract the secret key sk by performing following steps: 1) ê(pk, pk) = ê(g s , g q+1 s ) = g q+1 s

2) ê(g, pk) = ê(g, g s ) = g s

3) ê(g, g q+1 s ) = g q+1 s This learning cannot hold, because of the DDH assumption.

In [START_REF] Boneh | The decision diffie-hellman problem[END_REF], Boneh demonstrates that the DDH assumption is far stronger than the CDH.

-Completeness of Verification -In our scheme, the completeness property implies public verifiability property, which allows any entity, not just the client (data owner), to challenge the cloud server for data possession or data integrity without the need for any secret information. That is, public verification elements, needed in the verification process are publicly known. Thereby, any authorized user may challenge the server storage and efficiently verifies the proof of data possession. Hence, SHoPS is a public verifiable protocol. Lemma 5.1: Completeness of verification Given the tuple of public elements (pk, pk, σ 1 , σ 2 , params) and B i = Bi , the completeness of verification condition implies that Equation 4holds in G 2 .

C. Resistance to attacks

In the following analysis, we discuss the resistance of SHoPS to data leakage attacks, when only considering the vulnerabilities over the data file. As such, we suppose a malicious verifier. He attempts to gain knowledge about the outsourced data, based on the public elements of the data owner and multiple interactions with the legitimate storage server. We suppose that the challenger is not considered to perform preservation of computation resources by reusing the same random challenge η from one possession proof session to another. The verifier is assumed to renew the random scalar η to calculate the challenge pk η for each session. We suppose that the goal of the fraudulent verifier is to obtain information about the outsourced data file. That is, the attacker may request the same position index challenge k. As such, using two different sessions ((α), (β)), the attacker computes Equation13 and Equation 14 as follows:

σ 1 (α) σ 1 (β) = pk π i,k η (α) pk π i,k η (β) = pk π i,k (η (α) +η (β) ) (13) σ 1 (α) σ 1 (β) -1 = pk π i,k η (α) pk -π i,k η (β) = pk π i,k (η (α) -η (β) ) (14)
Knowing the challenge k, the attacker cannot reconstruct pieces of the file data, based on the CDH assumption. The prover sends only the pair (σ 1 , σ 2 ) to the verifier. Hence, it is likely impossible to extract information {π i,j } j∈ [1,q] from the server response. Thus, the randomness property is also necessary for the non triviality of the proof.

VI. PERFORMANCE EVALUATION

In this section, we present a theoretical performance evaluation in terms of computation, communication and storage costs

A. Computation Cost Evaluation

As presented in Section III, our single data block proof is made up 5 randomized algorithms: gen, stp, clg, prf and vrf. Among these algorithms, gen and stp are performed by the data owner. To generate the public parameters, the client performs 2q + 1 exponentiations in G. In the stp procedure, this latter executes q exponentiations and multiplications in order to generate the accumulator , which remains linearly dependent on the data size. Note that, this gen algorithm is one-time cost for the data owner and can be performed apart the other procedures. For each proof generation, the server computes the accumulator of a given data block with respect to the position index k, and performs q exponentiations and multiplications in order to generate the couple (σ 1 , σ 2 ). Upon receiving the server proof, the verifier conducts 3 pairing computations. In Section II, we presented a brief comparison between SHoPS and the most closely-related schemes ( [START_REF] Dodis | Proofs of retrievability via hardness amplification[END_REF], [START_REF] Ateniese | Provable data possession at untrusted stores[END_REF], [START_REF] Erway | Dynamic provable data possession[END_REF], [START_REF] Shacham | Compact proofs of retrievability[END_REF]). That is, Table I states the computation cost comparison between our scheme and previous works, at both client and server side. On the server side, SHoPS distributes the processing overhead over the multiple storing nodes. The cloud gate computes only i multiplications, where i is the number of the requested nodes, in an aggregated proof. Therefore, contrary to the other approaches, SHoPS achieves a O(logn) server computation complexity. On the verifier side, we brought additional computation cost, in order to perform a public verifiability. That is, the public verification procedure can also be performed by authorized challengers without the participation of the data owner. As such, this concern can be handled in practical scenarios, compared to the private scheme ( [START_REF] Dodis | Proofs of retrievability via hardness amplification[END_REF], [START_REF] Erway | Dynamic provable data possession[END_REF]) which have to centralize all verification tasks to the data owner. In our scheme, the authorized verifier has to generate two random scalars c ∈]0, R[ and k ∈ [1, q], in order to conduct his challenge request. Then, he checks the received proof from the cloud server, while performing three pairing computations, regardless the number of data blocks. Thus, the public verifiability introduces a O(nlogn) processing cost at the verifier side.

B. Bandwidth Cost Evaluation

In SHoPS, the bandwidth cost comes from the generated challenge message clg algorithm and the proof response in each verification request. On one hand, the exchanging challenge algorithm consists in transmitting one random position index k, where k ∈ R Z q and one element pk η . For a recommended security, we consider a security parameter λ = 80 bits, thus, the total cost of the challenge message is the double size of a group element of a multiplicative G. On the other hand, the proof response consists only in two elements (σ 1 , σ 2 ) ∈ G 2 . Therefore, the total bandwidth cost becomes constant and the bandwidth complexity of our scheme is O(1). As shown in Table I, [START_REF] Dodis | Proofs of retrievability via hardness amplification[END_REF] and [START_REF] Shacham | Compact proofs of retrievability[END_REF] present O(l) bandwidth complexity, where l is the number of elements in each encoded block of data. As a consequence, the bandwidth cost of these algorithms is linear to l. Considering the number of permitted challenges, [START_REF] Ateniese | Provable data possession at untrusted stores[END_REF] suffers from the problem of pre-fixed number of challenges, which is considered as an important requirement to the design of our construction. Nevertheless, their scheme presents a constant bandwidth cost, just like our proposed protocol.

C. Storage Cost Evaluation

On the client side, SHoPS only requires the data owner to keep secret his private key sk. The public elements of a data file consist in the different accumulators of each data block i{ i ∈ [1, n]}, where n is the number of data blocks. Thus, the storage size of each client is |sk|. We must note that |sk| is the size of the secret key of a SHoPS client, which is dependent on the security parameter λ. This storage overhead remains acceptable and attractive for resource constrained devices, mainly as it not dependent on the number of data blocks and the size of data.

VII. CONCLUSION

The growing need for secure cloud storage services and the attractive properties of an interactive proof system, lead us to define an innovative solution for proof of possession. In this paper, we define SHoPS supporting high security level and low processing complexity. Hence, it is shown to resist to data leakage attacks, while considering either a fraudulent prover or a cheating verifier. Additionally, our proposal is deliberately designed to support public verifiability and constant communication and storage cost.

1 )i = 1 ; 4 : 7 :

 1147 clg procedure: The clg procedure is executed by the client and yields a challenge for the cloud server. The client chooses at random a subblock position k ∈ {1, q} and a nonce η. The challenge c ∈ C consists on a random block index and Algorithm 2 stp procedure 1: Input: Data block (B i ), private key pr and param 2: Output: Data block accumulator 3: for all j ∈ [1 . . . q] do return (ID Bi , i ) the public key element pk hidden with a random nonce η as c = (k, pk η ).

Lemma 4 . 1 :

 41 Public Single Data Block Verification Correctness The verification procedure of Equation 4 holds if, and only if the data block file Bi = B i .

  return (pk, pk, pr, {g i } 1≤i≤2q;i =q+1 ) are, respectively, presented by Algorithm 2 and Algorithm 1. That is, each set of subblocks π i,j of B i is presented by an accumulator i =

	8:	param ← param ∪ {g α j }
	9: end for 10: s R ← -Z p ;
	11: pr ← s;
	12: pk ← g s ;
	13: pk ← g s q+1 ;
	14:

3: Choose a multiplicative group G 1 of a prime order q, 4: Select g a generator of G 1 ; 5: α R ← -Z p * ;

6: param = {g} 7: for all j ∈ [1 . . . 2q] do