Alexandra Pope
email: pope@astro.umass.edu

Alfredo Montana

Andrew Battisti

Marceau Limousin

Danilo Marchesini

Grant W Wilson

Stacey Alberts

Itziar Aretxaga

Vladimir Avila-Reese

Jose Ramon Bermejo-Climent

Alfredo Montaña

José Ramón Bermejo-Climent

Gabriel Brammer

Hector Bravo-Alfaro

Daniela Calzetti

Ranga-Ram Chary

Ryan Cybulski

Mauro Giavalisco

David Hughes

Erin Kado-Fong

Erica Keller

Allison Kirkpatrick

Ivo Labbe

Daniel Lange-Vagle

James Lowenthal

Eric Murphy

Pascal Oesch

Daniel Rosa Gonzalez

David Sánchez-Argüelles

Heath Shipley

Mauro Stefanon

Olga Vega

Katherine Whitaker

Christina C Williams

Min Yun

Jorge A Zavala

Milagros Zeballos

Early Science with the Large Millimeter Telescope: Detection of Dust Emission in Multiple Images of a Normal Galaxy at z > 4 Lensed by a Frontier Fields Cluster

Keywords: galaxies, evolution -galaxies, high-redshift -galaxies, star formation -infrared, galaxies -gravitational lensing, strong -ISM, dust, extinction

INTRODUCTION

Over the past 20 years, surveys at rest-frame UV wavelengths have mapped out the history of unobscured star formation from the present day back to z ∼ 8 (Madau & Dickinson 2014). However, the roughly equal brightness of the cosmic infrared and optical backgrounds informs us that half the light from the forma-tion and evolution of galaxies is obscured by dust (Lagache et al. 2005). Surveys with the Spitzer Space Telescope and the Herschel Space Observatory showed that the contribution from infrared-luminous galaxies to the star formation rate density increases dramatically from z = 0-2 (e.g. Caputi et al. 2007;Murphy et al. 2011a;Magnelli et al. 2013). Beyond z ∼ 3, our census of the dust-obscured, and hence total, star formation activity is severely incomplete.

Until recently, surveys of dust-obscured activity at z > 3 detected only the bright ultra-luminous infrared galaxies (ULIRGs, L IR > 10 12 L , Casey et al. 2014). While ULIRGs are prevalent at high redshift and many are not extreme starbursts like their local counterparts, they are not responsible for creating the bulk of the stars in the Universe (Lagache et al. 2005). At z ∼ 2, much of the cosmic star formation activity is occurring in galaxies with L IR < 10 12 L (Murphy et al. 2011a;Magnelli et al. 2013). While these normal1 galaxies can be selected at UV wavelengths, we have yet to directly detect most of their star formation activity as it is obscured by dust. The UV slope can provide an estimate of the dust extinction in the local Universe (Meurer et al. 1999); however, this correction is uncertain at high redshift where star formation is clumpy [START_REF] Guo | [END_REF] and gas and dust are more widely distributed across the galaxy (e.g. Ivison et al. 2011).

With its exceptional sensitivity, ALMA can directly detect dust in normal galaxies out to and beyond z ∼ 3. In ALMA Cycles 0-2, several programs have pushed below the ULIRG limit, detecting dust in half a dozen UV-selected galaxies from z = 4-7.5 (e.g. [START_REF] Capak | [END_REF]Watson et al. 2015;Willott et al. 2015;Dunlop et al. 2017). These studies show mixed results with some sources having significant dust emission while others remain undetected (e.g. Schaerer et al. 2015;Bouwens et al. 2016).

A complementary facility for directly detecting dust in z > 4 galaxies is the Large Millimeter Telescope Alfonso Serrano (LMT, [START_REF] Hughes | Proc. SPIE[END_REF]. With a large aperture and fast mapping capability, the AzTEC camera (Wilson et al. 2008) on the 32m LMT can survey dust in galaxies down to L IR ∼ 6 × 10 11 L regardless of redshift due to the negative K-correction. Gravitational lensing can be used to push even deeper. In this paper, we present the direct detection of dust in a multiplyimaged normal galaxy at z > 4 with AzTEC on LMT.

Throughout this paper we assume a cosmology with H 0 = 70 km s -1 Mpc -1 , Ω M = 0.3, and Ω Λ = 0.7.

2. DATA

Frontier Fields Program

The Frontier Fields (FFs) program 2 started as a large Hubble Space Telescope (HST) survey of low redshift clusters in order to identify and study high redshift background galaxies that are gravitationally lensed. In this paper, we use the 13-band HST data, the Spitzer-IRAC imaging from 3.6 to 8 micron, and K-band imaging from Keck-MOSFIRE (program N097M and N135M, PI: Marchesini, Brammer et al. 2016). The HST data include the F435W, F606W, F814W, F105W, F125W, F140W, and F160W images from the FF program; the F475W, F625W, F775W, and F850LP images from CLASH (Postman et al. 2012); and the F275W and F336W images from the program GO-13389 (PI: Siana). The v2.1 UV-to-IRAC multi-wavelength photometric catalog used in this paper was constructed following Skelton et al. (2014). The final catalog construction accounting for the intra-cluster light and contamination from brightest cluster galaxies will be described in Shipley et al. (2017).

Since our target is a multiply-imaged, strongly-lensed galaxy, interpretation of its intrinsic properties will depend on the lensing model. STScI has released magnification maps as a function of background galaxy redshift for all FF clusters calculated from several independent lensing models 3 . In this paper, we use the updated lensing models from Limousin et al. (2016) and Diego et al. (2015), and we verified that our results are robust with other lensing models from STScI (Johnson et al. 2014;Zitrin et al. 2015). We present our results for two different lensing models to give a sense of how the parameters we are interested in (stellar mass, star formation rate, UV slope) change under different lensing models.

New AzTEC/LMT observations

In November and December 2014, we imaged the FF cluster MACSJ0717.5+3745 with AzTEC during early science with the LMT. During early science operations, we are using the inner 32m of the eventual 50m aperture 4 . AzTEC is a 1.1 mm bolometer array camera, with a beam size of 8.5 arcsec (FWHM) on the 32 m LMT. Data were taken in good weather conditions (τ 225GHz = 0.05-0.12). The on-source integration time was 21.1 hours. Our map covers 25 sq. arcmin field reaching a 2 http://www.stsci.edu/hst/campaigns/frontier-fields/ 3 https://archive.stsci.edu/prepds/frontier/lensmodels/ 4 The LMT is transitioning to a 50m telescope in 2017. mean RMS of 0.24 mJy (central RMS is 0.19 mJy).

The calibration and analysis of the AzTEC data follow the procedure described in Wilson et al. (2008) and Scott et al. (2008). The results on the number counts and source properties from the full LMT FF program5 will be presented in future papers. Here we focus on a unique and rare source detected in our AzTEC map (MACS0717 Az9), which is coincident with an optically-detected, multiply-imaged lensed galaxy (known as 5.1/5.2/5.3, Zitrin et al. 2009). This is the only strongly-lensed, multiply-imaged system detected in our AzTEC survey. Figure 1 left shows AzTEC contours on the HST F160W image; two optical images (labelled 5.2 and 5.1) of the known multiply-imaged system are detected with AzTEC (3.7 and 3.3σ respectively). In Section 3.1, we demonstrate that at least half the millimeter flux detected by AzTEC must be associate with this system. A third > 3σ AzTEC detection is visible in the top-left corner of Figure 1 left, but it is unassociated with the multiply-imaged system that is the focus of this paper.

Robustness of millimeter detections

In order to test the robustness of MACS0717 Az9 both as a millimeter source and as the counterpart to the z > 4 multiply-imaged galaxy, we perform several simulations. We stress that since we have prior information on the positions of a known multiply-imaged galaxy, we have more confidence in lower signal-to-noise detections.

First we determine the chance that our millimeter detections (3.7 and 3.3σ) of the multiple-images 5.2 and 5.1 are spurious. We perform source extraction on 3000 noise maps. As with our original source list, we limit source extraction to regions of the map with noise < 0.4 mJy. We detect an average of 1 and 4 random > 3.7σ and > 3.3σ sources respectively in the noise maps. However, the sources we are interested in are not at random positions and specifically we detect two components of a previously known multiply-imaged system. With this prior information, we find the chance of randomly detecting a > 3.7σ source within 1 AzTEC beam of 5.2 and a > 3σ source within 1 AzTEC beam of 5.1 is < 0.03%. We find the same answer if we vary the position of 5.2 and 5.1 on the map but conserve their relative separation. Therefore, the probability that our millimeter detection of this multiply-imaged system (5.1 and 5.2) is a spurious detection is negligible.

Second, we test the chance that we should detect a multiply-imaged source given the known lensing models and a model for a background population of millimeter sources. We develop 500 simulated maps using the empirical galaxy evolution model of Bethermin et al. (2012) for the input background millimeter galaxies and the lensing models of MACSJ0717 from the CATS group (Limousin et al. 2016). Here we report results using the cored mass model, and verified that there are no measurable difference with the non-cored mass model. We randomly populate simulated maps with millimeter sources down to intrinsic (e.g. non-lensed) 1.1mm fluxes of ≥ 0.01 mJy. Redshifts are assigned to each millimeter source from the Bethermin et al. (2012) model. Then we run the background population through the cluster using the mass model in LENSTOOL (Kneib et al. 1996;Jullo et al. 2007) to find the observed population of millimeter sources and ask how often the millimeter sources are multiply-imaged. With no observed flux limit, multipleimage systems are found in all (99.4%) of our simulated maps, with an average of 6-7 systems per map. When we impose an observed flux limit of 0.7 mJy (i.e. > 3.5σ), we find that 30% of these multiple systems have at least one image detectable in our simulated maps. Coupled with our estimated completeness limit of 50% at this low flux level (Montaña et al. in prep.), our simulations predict that we will detect 1 multiply-imaged system in our AzTEC map of MACS0717. Besides MACS0717 Az9, there are no other known multiply-imaged sources in MACS0717 (using catalogs of known multiply-imaged systems, e.g Limousin et al. 2016) that are individually detected in our AzTEC maps. We take the full list of multiply-imaged sources including their magnification values and we stack the intrinsic millimeter flux for each multiply-imaged source. We do not find that any other systems are detected even when averaging the individual components in this way. Furthermore, none of the other AzTEC detections are in regions of strong magnification. Therefore, our simulations predict that we should detect one multiply-imaged systems like MACS0717 Az9.

Finally, we can further test the robustness of this millimeter detection by showing that the millimeter fluxes that we measure for 5.1, 5.2 and 5.3 are consistent with each other given their known magnifications (see Section 3.1). The results of all three of these simulations and tests show that we have unambiguously detected dust emission in this multiply-imaged system.

ANALYSIS

Counterpart of MACS0717 Az9

Before we can discuss the nature of this millimeter source, we need to demonstrate that the multiplyimaged system is the correct optical counterpart. From our simulations (Montaña et al. in prep.), we find a positional accuracy for this system of 3.1 arcsec with 90% confidence. Within the search radius of MACS0717 Az9, we find two multiply-imaged systems (Figure 1 right): 5.2 (z > 4) and 12.2 (z = 1.71). But our AzTEC map also covers the other multiple images of these systems: 5.1/5.3 and 12.1/12.3 (Figure 1 left). We detect 5.1 in our AzTEC map at 3.3σ. Source 5.3 has a lower magnification; as a result, the measured AzTEC flux is only 1.4σ (Table 1). Both 12.1 and 12.3 are undetected in our AzTEC map. In this Section, we show that the counterpart to MACS0717 Az9 must be 5.2.

The magnifications (µ) are known for all components of systems 5 and 12 (Limousin et al. 2016;Diego et al. 2015), and so we test if the observed fluxes of each component are consistent with the predicted fluxes. Figure 2 left shows the observed fluxes of all three images of system 5 as the solid circles. If we assign some fraction F of the MACS0717 Az9 flux to 5.2 (S 5.2,obs = S Az9 * F ) and the remainder of the flux to 12.2, then we can predict the flux of 5.1 and 5.3 as follows:

S 5.1,pred = (S 5.2,obs /µ 5.2 ) × µ 5.1
(1)

S 5.3,pred = (S 5.2,obs /µ 5.2 ) × µ 5.3 (2)
where µ 5.2 , µ 5.1 and µ 5.3 denote the known magnifications of 5.2, 5.1 and 5.3. The triangles and squares in Figure 2 left show the predicted fluxes from two different lensing models assuming F = 1, which are remarkably consistent with the observed fluxes of 5.1 and 5.3. If instead we perform this calculation assuming the millimeter emission comes from 12.2 (Figure 2 right), we find that the observed fluxes of 12.1 and 12.3 are inconsistent with the expected fluxes under each of the two lensing models. Next, we calculate the P -value for all values of F from 0-1 under the hypothesis that the predicted fluxes equal the observed fluxes:

S 5.1,obs -S 5.1,pred ∼ N(0, σ 2 5.1,obs + σ 2 5.1,pred ) (3) S 5.3,obs -S 5.3,pred ∼ N(0, σ 2 5.3,obs + σ 2 5.3,pred ) (4)
where N is a normal distribution. σ 5.1,pred and σ 5.3,pred include the uncertainties from all quantities in Equations 1 and 2; the flux measurement of 5.2, the magnification of 5.2 and the magnification of 5.1 and 5.3, respectively. We perform this hypothesis test for 5.1, 5.3, 12.1 and 12.3 and combine the P -values using Fisher's method [START_REF] Fisher | Statistical Methods for Research Workers, Oliver and Boyd[END_REF]). The combined P -value as a function of F is plotted in Figure 3. We can reject the null hypothesis that F ≤ 0.45 at a significance level of 0.05; this means that at least half the flux of MACS0717 Az9 must be associated with 5.2. For the analysis in this paper we assume the most likely scenario: that all of the flux of MACS0717 Az9 is associated with 5.2 (i.e., F = 1). In Section 4.3, we discuss how our main results are affected under the conservative assumption that only half the millimeter flux is associated with 5.2.

Redshift

The multiple images (5.1, 5.2, 5.3) have independent redshift estimates from blind photometric redshift catalogs (Figure 4 right, see also Postman et al. 2012) and from the lensing models (Diego et al. 2015;Limousin et al. 2016, see also Johnson et al. 2014;Zitrin et al. 2015). c Errors include the uncertainty due to the magnification and the photometric uncertainty.

d Errors include the uncertainty due to the SED template (27%, Kirkpatrick et al. 2015), the magnification and the photometric uncertainty.

Table 2 summarizes the redshift estimates for each multiple image. As described in Section 3.3, fitting the optical spectral energy distribution gives photometric redshifts of ∼ 4.4-4.6. The lensing models agree on a redshift of z 4 for this multiply-imaged source, and are consistent with the ±3σ limits from the photometric redshift. Treu et al. (2015) suggest a low redshift solution of z = 0.928 for image 5.1 based on HST grism data. However, we do not see any strong features in the spectrum and this redshift is not compatible with the mass models of MACSJ0717.5+3745.

In this paper, we consider two redshift solutions; 1) z = 4.1±0.2 from the non-cored mass model of Limousin et al. (2016), and 2) z = 4.3 from the lens model of Diego et al. (2015). Table 2 lists the magnifications for each of these solutions. While a spectroscopic redshift for this multiply-imaged system will be important for further studies, the uncertainty in the analysis in this paper is less affected because of the negative K-correction, which makes the relation between millimeter flux and luminosity roughly constant between z = 1-6. . P-value from testing the hypothesis that the observed fluxes of 5.1/5.3 and 12.1/12.3 are consistent with the predicted fluxes as a function of the fraction of the flux from MACS0717 Az9 that is attributed to 5.2. The most likely scenario is that all of the flux from MACS0717 Az9 is associated with 5.2, and we can rule out the scenario where ≤ 45% of the millimeter flux is coming from 5.2.

UV to near-IR properties

Measuring the UV to near-IR photometry for this multiply-imaged system is complicated since the images are extended (Figure 1 right) and resolve into separate entries in our multi-wavelength catalog. We take the weighted mean of these entries to estimate the total flux in each band for 5.1, 5.2 and 5.3. Having three lensed images of the same galaxy provides an independent check on the photometry.

We fit the de-magnified UV to the near-IR photometry using FAST (Kriek et al. 2009) adopting Bruzual & Charlot (2003) stellar populations (BC03), a Chabrier (2003) IMF and a delayed exponentially declining SFH in order to determine the stellar mass. Since we find that this galaxy lies closer to the SMC dust curve (see Section 4.1), we perform the SED fitting using SMC dust attenu-ation and sub-solar metallicity (Z = 0.2×Z ) 6 . The difference in stellar mass between a Chabrier and Kroupa (2001) IMF is negligible (e.g. Speagle et al. 2014). The uncertainty in the stellar masses include the photometric error, the uncertainty in the magnification (including an additional 10% for differential lensing, Section 3.5) and the uncertainty in the SED fitting. The stellar masses and their 68% confidence ranges are given in Table 3. Figure 4 left shows the SED fits for the z = 4.1 lens model; given the large magnification values for each multiple-image, the de-magnified SEDs show very good agreement.

We also fit the de-magnified UV to the near-IR photometry using EAZY (Brammer et al. 2008) to independently determine the photometric redshift. In the right panel of Figure 4, we show the redshift probability distribution for each multiple image and the average of the three. While the redshift solutions from the lensing models are lower, they are consistent within the ±3σ limits of the photometric redshifts from the SED fitting. A spectroscopic redshift for this multiply-imaged source will help further refine the lensing models.

The rest-frame UV spectral slope (β, where f λ ∝ λ β ) is calculated by fitting a power-law to the restframe photometric data between the wavelength range of 1300-3000 Å. Prior to fitting, the lensing magnification is removed from the photometric data and we propagate the magnification uncertainty. The UV luminosity, L 1600 = ν 1600 L ν (1600 Å), is determined using the fitted value for β. Table 3 lists these derived UV properties corrected for magnification for each multiple image and the average of all three.

Star formation rates

Our AzTEC detection at 1.1 mm corresponds to a rest wavelength of < 220 µm at z > 4, which probes near the peak of the infrared dust emission. At this restwavelength, we are most sensitive to the IR luminosity 6 If we instead assumed a Calzetti et al. (2000) dust attenuation law and a range in metallicities (from sub-solar to super-solar), the stellar masses from the best-fit SEDs are slightly larger, but consistent within the uncertainties, than the values in Table 3. (left) Rest-frame, de-magnified optical spectral energy distribution of 5.1 (light gray), 5.2 (medium gray), 5.3 (dark gray) and the mean of all three sources (red), assuming the redshift and magnifications from the Limousin et al. (2016) non-cored lensing model. Given the large differences in magnification factors of the three sources, the de-magnified SEDs are remarkably consistent. (right) Redshift probability distribution from the SED fitting for 5.1 (light gray), 5.2 (medium gray) and 5.3 (dark gray) and for the mean (red). The Limousin et al. (2016) non-cored solution of z=4.1 (vertical dash-dot line) is consistent with the 3σ limits of the optical photometric redshift estimates.

and not the dust mass since we are not in the Rayleigh-Jeans tail of the dust distribution (e.g. λ rest > 250 µm, Scoville et al. 2016). Given the observed faintness of MACS0717 Az9 at 1.1 mm, we do not expect to detected it with Herschel (Rawle et al. 2016). In order to determine the total IR (8-1000 µm) luminosity, L IR , we must extrapolate using the expected SED for this galaxy. Kirkpatrick et al. (2015) derived representative SED templates from a sample of 343 high redshift galaxies with extensive IR data including mid-IR spectroscopy. We fit the intrinsic 1.1 mm flux, after correcting for magnification, to the SED template for a typical high redshift star-forming galaxy (Kirkpatrick et al. 2015). The L IR of each component of system 5 for the two lensing models are listed in Table 1.

We use the formulas from Murphy et al. (2011b) to calculate the SFRs (assuming a Kroupa IMF). From L IR and L FUV , we calculate the obscured SFR IR and unobscured SFR UV , respectively. The total SFR is then calculated by summing the IR and UV SFRs. All star formation rate values are listed in Table 3. We find that even though this galaxy has an intrinsically low SFR, at least 75% of the star formation is obscured. We tested our analysis with different SFR calibrations (e.g. Calzetti 2013); the obscured fraction is only slightly lower (65%) and our conclusions are unchanged.

Differential lensing

We are assuming that the magnifications derived from the optical lensing maps also apply to the longer wavelength millimeter data. For highly magnified sources, differential lensing becomes important, where extended and compact regions of a galaxy can be magnified by different factors. Hezaveh et al. (2012) model the effects of differential lensing for strongly lensed, dusty galaxies. They find that for moderate magnifications similar to MACS0717 Az9 (µ ∼ 7), the distribution of flux ratios between the extended and compact regions of a galaxy is peaked at 1 with a FWHM of ∼ 0.25 (i.e. ∼ 10% uncertainty), suggesting that differential lensing is not a large effect.

In this paper, our main comparison is between the unobscured (UV) and obscured (IR/submm) SFRs. Dusty galaxies have been found to have similar radii of ∼2 kpc as measured in UV and (sub)mm images, while the optical sizes which trace the stellar light are more extended (Swinbank et al. 2010;Hodge et al. 2016). However, the UV and (sub)mm emission is not always co-spatial and Å for these galaxies. b f obscured = SFRIR/SFR total can be offset by up to an arcsec (e.g. [START_REF] Iono | [END_REF]. In order to quantify the range of magnifications that might be applicable to the millimeter emission, we explore a wider area in the non-cored magnification map at z = 4.1. For a lensing magnification of 7.5, 1 arcsecond offset in the source plane corresponds to 2.7 in the image plane. Within a 2.7 arcsec diameter circle around the location of the optical lensed galaxy 5.2 (where µ = 7.5), we find the magnification ranges from 6.0-9.2 with a standard deviation of 0.76. Therefore, if the UV and millimeter emission is not co-spatial and are magnified by different amounts, this would result in an additional uncertainty of ∼ 10% in the magnification, and intrinsic flux, we derive.

Given these two tests of the effects of differential lensing, we conservatively propagate an additional uncertainty of 10% in the lensing magnification factors, which is the best we can do until we are able to spatially resolve the dust emission with ALMA.

DISCUSSION

We have detected dust emission in a strongly-lensed, multiply-imaged galaxy at z > 4. The high magnification (µ = 7.5) predicts that MACS0717 Az9 has an intrinsic L IR < 10 11 L (SFR IR = 14.6 M /yr). Previous detections of dust in multiple images of lensed galaxies have been limited to ULIRGs at z < 3 (Borys et al. 2004;Sheth et al. 2014;Kneib et al. 2015). There are very few galaxies at z > 4 at the low luminosities of MACS0717 Az9 that have been detected in dust emission (e.g. [START_REF] Capak | [END_REF]Schaerer et al. 2015;Watson et al. 2015;Willott et al. 2015), and MACS0717 Az9 provides a unique opportunity to probe the star formation and dust properties in a typical galaxy at this early epoch.

IRX-β

UV surveys rely on the UV slope, β, and its dependence on L UV to estimate the dust extinction since IR observations are typically not deep enough. The measured value of β for MACS0717 Az9 is high relative to the distribution of β found for UV-selected galaxies of similar luminosity at z ∼ 4 (Bouwens et al. 2012: β mean = -2.01, σ = 0.27, see also Bouwens et al. 2016); this means that L UV alone would underestimate the IR luminosity by an order of magnitude.

In Figure 5, we plot the IRX-β relation, which compares the ratio of L IR /L UV to the UV slope β. The solid curve is the established relationship for local starburst galaxies (Meurer et al. 1999) where z ∼ 2 massive UV-selected galaxies are also found (Reddy et al. 2012). The dotted curve shows the milder dust extinction found in the SMC (Pettini et al. 1998). [START_REF] Capak | [END_REF] found UV-selected galaxies at z ∼ 5 to be closer to this SMC dust curve (see also Murphy et al. 2011a;Lee et al. 2012). Recently, Bouwens et al. (2016) found that sub-L * galaxies also show lower values of IRX, even below the SMC. MACS0717 Az9 is shown as the red and orange stars, which are closer to the SMC dust curve than the Meurer relation, even though the dust-obscured emission dominates the SFR.

A lower value in IRX-β relative to the starburst relation is usually interpreted to suggest a lower metallicity. It may seem unusual for such a dust-obscured galaxy (75-80% of star formation is obscured) to have a lower metallicity. Schneider et al. (2016) recently found significant dust emission in a local, metal-poor dwarf galaxy. By comparing to models of chemical evolution, they conclude that dust content may depend more on the density of the interstellar medium (ISM) than the metallicity, Figure 5. IRX-β plot showing the relations for local starburst galaxies (solid curve, Meurer et al. 1999) and the SMC (dotted curve, Pettini et al. 1998). We show MACS0717 Az9 for the z = 4.1 and z = 4.3 lens models as the red and orange stars, respectively. Even though 75-80% of the star formation is coming out in the infrared, we find that MACS0717 Az9 is consistent with the SMC dust curve, similar to the [START_REF] Capak | [END_REF] z ∼ 5 UV-selected galaxies (blue triangles).

and that in-situ grain growth should be especially important in the early Universe. Future observations of lines sensitive to the ISM density and metallicity such as CO, [CII] and HCN in MACS0717 Az9 can be used to test this idea.

Galaxy star formation sequence

At a given epoch, the tight relationship between the star formation rate and stellar mass implies that most normal star-forming galaxies are undergoing steady growth (e.g. Noeske et al. 2007;Daddi et al. 2007). The stellar mass of MACS0717 Az9 is well below the estimated knee in the stellar mass function at z ∼ 4 (Muzzin et al. 2013). In order to determine if MACS0717 Az9 is a normal galaxy for this epoch, we compare the position of this galaxy to the estimated extrapolation of the star formation sequence. In Figure 6, we plot the star formation sequence at z = 3-4 from Tomczak et al. (2016). The z ∼ 5 star-forming galaxies detected in submm continuum with ALMA by [START_REF] Capak | [END_REF] and the extreme submillimeter galaxy, GN20 (Pope et al. 2006;Riechers et al. 2014;Tan et al. 2014), are shown for comparison.

First, we find that MACS0717 Az9 (red and orange stars for two redshift solutions) is consistent with the estimated star formation sequence for this epoch, and that this galaxy resides in a region that is relatively unexplored in the infrared. Given the error bars on MACS0717 Az9 and the uncertainty in the star formation sequence at these low masses, we do not claim MACS0717 Az9 is below the star formation sequence but we can confidently say that the source is not an extreme starburst galaxy like GN20. Second, we show that even though this is a normal star-forming galaxy, its SFR is dominated by the obscured component (SFR IR is at least 75% of the total SFR). This underscores the importance of accurately including this obscured component when accounting for the global SFRD, even at these high redshifts and lower stellar masses, and stresses the need for deep and wide IR/submm surveys.

Two recent papers that surveyed the Hubble Ultra Deep Field with ALMA seem to suggest a smaller number of high redshift galaxies detected in dust emission than expected (Dunlop et al. 2017;Bouwens et al. 2016 3). Error bars are plotted only for the total SFR points for clarity. We overplot the [START_REF] Capak | [END_REF] UV-selected galaxies that are detected in the submm continuum and the intrinsically luminous submillimeter galaxy GN20 (Pope et al. 2006;Riechers et al. 2014;Tan et al. 2014). All measurements are based on a Chabrier or Kroupa IMF which give similar values for SFR and stellar mass (Speagle et al. 2014).

detected in the Dunlop et al. (2017) observations has a slightly lower stellar mass (4 × 10 9 M ) and higher SFR IR = 37 M /yr than MACS0717 Az9, but is similarly dominated by the dust-obscured star formation (f obscured = 0.94). The high levels of dust obscuration observed in a handful of normal galaxies at z > 4 suggests that we cannot easily rule out the importance of dust emission in galaxies at z > 4.

What if 5.2 only has half the millimeter flux?

In the previous sections, we assumed that all of the millimeter flux from MACS0717 Az9 is associated with 5.2 since that is the most likely result from our statistical analysis (Figure 3). Here we explore how our results are affected if only half the flux of MACS0717 Az9 is associated with 5.2. If the millimeter flux is half what we assumed in Table 1, then L IR = 4.9 × 10 10 L , SFR IR = 7.3 M /yr, SFR total = 11.4 M /yr and f obscured = 0.64, assuming the z = 4.1 lens model. Under this assumption, the obscured SFR is slightly lower, but the total SFR is still dominated by the dust-obscured contribution. This places MACS0717 Az9 even lower on both the star formation sequence (Figure 6) and the IRX-β plot (Figure 5). Therefore, the results and implications discussed in this paper are unchanged. Future observations with ALMA will confirm how much millimeter flux is associated with this multiply-imaged source.

SUMMARY

We have directly detected dust emission in an intrinsically lower-luminosity (L IR = 9.7 × 10 10 L ) galaxy at z > 4 with AzTEC on the LMT. Currently, this is the only star forming galaxy at such a low luminosity (sub-LIRG) where multiple images are detected in dust emission. While the SNRs of the individual images are modest, the false detection rate for randomly detecting two multiple images of a known system at the correct flux ratio given the known magnifications is negligible. We calculate the unobscured SFR from the UV and the obscured SFR from the IR and calculate a total intrinsic SFR of 18.7 M /yr, 75-80% of which is obscured. MACS0717 Az9 is a normal star-forming galaxy with an intrinsic stellar mass of 6.9 × 10 9 M and is consistent with the estimated star formation sequence at z ∼ 4. The dust obscuration in MACS0717 Az9 appears to be more like that of the SMC than local starburst galaxies. While we might expect lower metallicities for a lower mass galaxy 1.5 Gyrs after the Big Bang (Rémy-Ruyer et al. 2015), our rest-frame IR observations find a significant dust component. Further observations to constrain the conditions of the the gas and dust in MACS0717 Az9 and future surveys with the 50m LMT (observational limit of L IR ∼ 10 11 L ) will help constrain the buildup of metals and dust in early galaxy evolution.

We thank the referee for constructive comments on this paper. This work would not have been possible without the long-term financial support from the Mexican Science and Technology Funding Agency, CONA-CYT during the construction and early operational phase of the Large Millimeter Telescope Alfonso Serrano, as well as support from the the US National Science Foundation (NSF) via the University Radio Observatory program, INAOE and the University of Massachusetts, Amherst. This work utilizes gravitational lensing models produced by PIs Bradac, Natarajan & Kneib (CATS), Merten & Zitrin, Sharon, and Williams, and the GLAFIC and Diego groups. This lens modeling was partially funded by the HST Frontier Fields program conducted by STScI. STScI is operated by the Association of Universities for Research in Astronomy, Inc. under NASA contract NAS 5-26555. The lens mod-els were obtained from the Mikulski Archive for Space Telescopes (MAST). We also thank J. Diego for information on their lens model. This work is based in part on observations made with the Spitzer Space Telescope, which is operated by the Jet Propulsion Laboratory, California Institute of Technology under a contract with NASA. AP acknowledges valuable discussions with Sandy Faber, George Rieke and Adi Zitrin. ML acknowledges CNRS and CNES for support. IA and DRG

Figure 1 .

 1 Figure1. HST F160W image towards MACSJ0717 with AzTEC/LMT contours (3 and 3.5σ) in red. Our AzTEC map covers a wider region than shown here. The 3σ detection in the top left is unrelated to the multiply-imaged galaxy. We show the two multiply-imaged systems: 5.1/5.2/5.3 at z > 4 (blue circles) and 12.1/12.2/12.3 at z = 1.71 (green squares). The right panel shows a zoom-in of the millimeter detection MACS0717 Az9, which is at the bottom right of the left panel. The size of the image is roughly equal to the FWHM of the beam.

Figure 2 .

 2 Figure2. Demonstration that MACS0717 Az9 is most likely associated with the multiply-imaged galaxy 5.2. (left) Red circles show the observed 1.1 mm fluxes of the 3 multiply-imaged components; 5.1, 5.2 and 5.3, from our AzTEC maps. The dark blue triangles and light blue squares show the predicted millimeter fluxes of 5.1 and 5.3 assuming that MACS0717 Az9 is associated with 5.2 and applying the known lensing magnifications (Table2) from theLimousin et al. (2016) andDiego et al. (2015) lensing models, respectively. The error bars on the blue points include the photometric uncertainty and the magnification uncertainty. (right) Same as the left panel but for the multiply-imaged source 12.1/12.2/12.3 showing the observed fluxes are inconsistent with the predicted fluxes under these two different lensing models.

  Figure3. P-value from testing the hypothesis that the observed fluxes of 5.1/5.3 and 12.1/12.3 are consistent with the predicted fluxes as a function of the fraction of the flux from MACS0717 Az9 that is attributed to 5.2. The most likely scenario is that all of the flux from MACS0717 Az9 is associated with 5.2, and we can rule out the scenario where ≤ 45% of the millimeter flux is coming from 5.2.

Figure 4 .

 4 Figure 4.(left) Rest-frame, de-magnified optical spectral energy distribution of 5.1 (light gray), 5.2 (medium gray), 5.3 (dark gray) and the mean of all three sources (red), assuming the redshift and magnifications from theLimousin et al. (2016) non-cored lensing model. Given the large differences in magnification factors of the three sources, the de-magnified SEDs are remarkably consistent. (right) Redshift probability distribution from the SED fitting for 5.1 (light gray), 5.2 (medium gray) and 5.3 (dark gray) and for the mean (red). TheLimousin et al. (2016) non-cored solution of z=4.1 (vertical dash-dot line) is consistent with the 3σ limits of the optical photometric redshift estimates.

Figure 6 .

 6 Figure6. The star formation sequence at z = 3-4 fromTomczak et al. (2016, solid circles show where the data are mass-complete while open circles are incomplete measurements); the shaded region shows the ±1σ best-fit relation to these data. We show the UV (unobscured), IR (obscured) and total SFRs for MACS0717 Az9 as the red and orange symbols for z = 4.1 and z = 4.3, respectively (Table3). Error bars are plotted only for the total SFR points for clarity. We overplot the[START_REF] Capak | [END_REF] UV-selected galaxies that are detected in the submm continuum and the intrinsically luminous submillimeter galaxy GN20(Pope et al. 2006;Riechers et al. 2014;Tan et al. 2014). All measurements are based on a Chabrier or Kroupa IMF which give similar values for SFR and stellar mass(Speagle et al. 2014).

Table 1 .

 1 Observed properties of dust emission in the multiply-imaged system 5.1/5.2/5.3 in MACSJ0717.5+3745 ID z a Observed S1.1mm b Intrinsic S1.1mm c LIR d We measure the 1.1 mm flux at the known optical position of each multiple image to mitigate the effects of flux boosting.

		(mJy)	(mJy)	(10 10 L )
	5.1	4.1 0.65 ± 0.20	0.096 ± 0.033	9.6 ± 4.2
	5.2 (MACS0717 Az9) 4.1 0.73 ± 0.20	0.097 ± 0.029	9.7 ± 3.9
	5.3	4.1 0.29 ± 0.21	0.097 ± 0.067	9.7 ± 7.2
	5 (average)		0.097 ± 0.026	9.7 ± 3.0
	5.1	4.3 0.65 ± 0.20	0.144 ± 0.048	14.4 ± 6.2
	5.2 (MACS0717 Az9) 4.3 0.73 ± 0.20	0.102 ± 0.032	10.2 ± 4.2
	5.3	4.3 0.29 ± 0.21	0.112 ± 0.079	11.2 ± 8.5
	5 (average)		0.119 ± 0.032	11.9 ± 3.8

a From the

Limousin et al. (2016)

non-cored lensing model (z = 4.1) and the

Diego et al. (2015)

lensing model (z = 4.3). For corresponding magnifications, see Table

2

. b

Table 2 .

 2 Redshift estimates of the multiply-imaged system 5.1/5.2/5.3 in MACSJ0717.5+3745 An additional 10% uncertainty is added in quadrature to account for differential lensing (see Section 3.5).

	ID	RA	DEC	Limousin+16 non-cored lensing model Diego+15 lensing model	SED fitting
				z	magnification a	z b	magnification a	z [1σ lower,1σ upper]
	5.1 07:17:31.178 +37:44:48.70 4.1 ± 0.2	6.8 ± 1.1	4.3	4.5 ± 0.6	4.48 [4.21,4.73]
	5.2 07:17:30.698 +37:44:34.12 4.1 ± 0.2	7.5 ± 1.0	4.3	7.2 ± 1.1	4.64 [4.51,4.78]
	5.3 07:17:36.007 +37:46:02.64 4.1 ± 0.2	3.0 ± 0.3	4.3	2.6 ± 0.4	4.44 [4.24,4.64]

a b Uncertainties on the redshift are not provided for this lensing model.

Table 3 .

 3 Derived intrinsic physical properties From theLimousin et al. (2016) non-cored lensing model (z = 4.1) and theDiego et al. (2015) lensing model (z = 4.3). For corresponding magnifications, see Table2.

	ID	z a	log(M * /[M ])	L 1600	Åb	β	SFRUV	SFRIR	SFR total	f obscured	c
			[1σ lower,1σ upper] (10 10 L )		(M /yr) (M /yr)	(M /yr)
	5.1	4.1 9.87 [9.44,10.13]	2.03 ± 0.24 -0.47 ± 0.39 3.4 ± 0.4 14.4 ± 6.3	17.8 ± 6.3	0.81
	5.2 (MACS0717 Az9) 4.1 9.52 [9.37,9.76]	2.29 ± 0.23 -0.95 ± 0.33 3.8 ± 0.4 14.6 ± 5.8	18.4 ± 5.8	0.79
	5.3	4.1 9.87 [9.52,10.08]	2.95 ± 0.44 -0.67 ± 0.26 4.9 ± 0.7 14.6 ± 10.8 19.5 ± 10.8 0.75
	5 (average)		9.84 [9.58,9.94]	2.43 ± 0.18 -0.70 ± 0.19 4.1 ± 0.3 14.6 ± 4.5	18.7 ± 4.5	0.78
	5.1	4.3 10.16 [9.87,10.47]	3.51 ± 0.29 -0.48 ± 0.26 5.9 ± 0.5 21.6 ± 9.3	27.5 ± 9.3	0.79
	5.2 (MACS0717 Az9) 4.3 9.82 [9.54,9.96]	2.68 ± 0.25 -0.95 ± 0.30 4.5 ± 0.4 15.3 ± 6.3	19.8 ± 6.3	0.77
	5.3	4.3 10.11 [9.72,10.37]	3.76 ± 0.56 -0.59 ± 0.31 6.3 ± 0.9 16.8 ± 12.8 23.1 ± 12.8 0.73
	5 (average)		10.12 [9.82,10.28]	3.31 ± 0.23 -0.67 ± 0.17 5.5 ± 0.4 17.9 ± 5.7	23.4 ± 5.7	0.76

a b LFUV ∼ 0.97 × L 1600

We use "normal" to refer to typical star-forming galaxies for their epoch; on the star formation sequence(Noeske et al.

2007), and/or with stellar masses near the knee of the stellar mass function(Muzzin et al. 2013).

http://people.umass.edu/apope1/FF/

acknowledge support from CONACYT grants CB-2011-01-1672 and CB-2011-01-167281, respectively. ML acknowledges the Centre National de la Recherche Scien-tifique for support. DM acknowledges the support of the NSF under Grant 1513473, and from HST-AR-14302, provided by NASA through a grant from STScI, which is operated by AURA, under NASA contract NAS5-26555. DLV acknowledges support from the NASA Keck PI Data Awards, administered by the NASA Exoplanet Science Institute. KEW gratefully acknowledge support by NASA through Hubble Fellowship grant #HF2-51368 awarded by the Space Telescope Science Institute, which is operated by the Association of Universities for Research in Astronomy, Inc., for NASA. Facilities: LMT, HST, Spitzer


John Bethencourt
email: bethenco@cs.cmu.edu

Amit Sahai
email: sahai@cs.ucla.edu

Brent Waters
email: bwaters@csl.sri.com

Ciphertext-Policy Attribute-Based Encryption

come

Introduction

In many situations, when a user encrypts sensitive data, it is imperative that she establish a specific access control policy on who can decrypt this data. For example, suppose that the FBI public corruption offices in Knoxville and San Francisco are investigating an allegation of bribery involving a San Francisco lobbyist and a Tennessee congressman. The head FBI agent may want to encrypt a sensitive memo so that only personnel that have certain credentials or at-tributes can access it. For instance, the head agent may specify the following access structure for accessing this information: (("Public Corruption Office" AND ("Knoxville" OR "San Francisco")) OR (management-level > 5) OR "Name: Charlie Eppes").

By this, the head agent could mean that the memo should only be seen by agents who work at the public corruption offices at Knoxville or San Francisco, FBI officials very high up in the management chain, and a consultant named Charlie Eppes. As illustrated by this example, it can be crucial that the person in possession of the secret data be able to choose an access policy based on specific knowledge of the underlying data. Furthermore, this person may not know the exact identities of all other people who should be able to access the data, but rather she may only have a way to describe them in terms of descriptive attributes or credentials.

Traditionally, this type of expressive access control is enforced by employing a trusted server to store data locally. The server is entrusted as a reference monitor that checks that a user presents proper certification before allowing him to access records or files. However, services are increasingly storing data in a distributed fashion across many servers. Replicating data across several locations has advantages in both performance and reliability. The drawback of this trend is that it is increasingly difficult to guarantee the security of data using traditional methods; when data is stored at several locations, the chances that one of them has been compromised increases dramatically. For these reasons we would like to require that sensitive data is stored in an encrypted form so that it will remain private even if a server is compromised.

Most existing public key encryption methods allow a party to encrypt data to a particular user, but are unable to efficiently handle more expressive types of encrypted access control such as the example illustrated above.

Our contribution. In this work, we provide the first construction of a ciphertext-policy attribute-based encryption (CP-ABE) to address this problem, and give the first construction of such a scheme. In our system, a user's private key will be associated with an arbitrary number of attributes expressed as strings. On the other hand, when a party encrypts a message in our system, they specify an associated access structure over attributes. A user will only be able to decrypt a ciphertext if that user's attributes pass through the ciphertext's access structure. At a mathematical level, access structures in our system are described by a monotonic "access tree", where nodes of the access structure are composed of threshold gates and the leaves describe attributes. We note that AND gates can be constructed as n-of-n threshold gates and OR gates as 1-of-n threshold gates. Furthermore, we can handle more complex access controls such as numeric ranges by converting them to small access trees (see discussion in the implementation section for more details).

Our techniques. At a high level, our work is similar to the recent work of Sahai and Waters [START_REF] Sahai | Fuzzy Identity Based Encryption[END_REF] and Goyal et al. [START_REF] Goyal | Attribute Based Encryption for Fine-Grained Access Conrol of Encrypted Data[END_REF] on key-policy attribute based encryption (KP-ABE), however we require substantially new techniques. In key-policy attribute based encryption, ciphertexts are associated with sets of descriptive attributes, and users' keys are associated with policies (the reverse of our situation). We stress that in keypolicy ABE, the encryptor exerts no control over who has access to the data she encrypts, except by her choice of descriptive attributes for the data. Rather, she must trust that the key-issuer issues the appropriate keys to grant or deny access to the appropriate users. In other words, in [START_REF] Sahai | Fuzzy Identity Based Encryption[END_REF][START_REF] Goyal | Attribute Based Encryption for Fine-Grained Access Conrol of Encrypted Data[END_REF], the "intelligence" is assumed to be with the key issuer, and not the encryptor. In our setting, the encryptor must be able to intelligently decide who should or should not have access to the data that she encrypts. As such, the techniques of [START_REF] Sahai | Fuzzy Identity Based Encryption[END_REF][START_REF] Goyal | Attribute Based Encryption for Fine-Grained Access Conrol of Encrypted Data[END_REF] do not apply to our setting, and we must develop new techniques.

At a technical level, the main objective that we must attain is collusion-resistance: If multiple users collude, they should only be able to decrypt a ciphertext if at least one of the users could decrypt it on their own. In particular, referring back to the example from the beginning of this Introduction, suppose that an FBI agent that works in the terrorism office in San Francisco colludes with a friend who works in the public corruption office in New York. We do not want these colluders to be able to decrypt the secret memo by combining their attributes. This type of security is the sine qua non of access control in our setting.

In the work of [START_REF] Sahai | Fuzzy Identity Based Encryption[END_REF][START_REF] Goyal | Attribute Based Encryption for Fine-Grained Access Conrol of Encrypted Data[END_REF], collusion resistance is insured by using a secret-sharing scheme and embedding independently chosen secret shares into each private key. Because of the independence of the randomness used in each invocation of the secret sharing scheme, collusion-resistance follows. In our scenario, users' private keys are associated with sets of attributes instead of access structures over them, and so secret sharing schemes do not apply.

Instead, we devise a novel private key randomization technique that uses a new two-level random masking methodology. This methodology makes use of groups with efficiently computable bilinear maps, and it is the key to our security proof, which we give in the generic bilinear group model [START_REF] Boneh | Hierarchical identity based encryption with constant size ciphertext[END_REF][START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF].

Finally, we provide an implementation of our system to show that our system performs well in practice. We provide a description of both our API and the structure of our implementation. In addition, we provide several techniques for optimizing decryption performance and measure our performance features experimentally.

Organization. The remainder of our paper is structured as follows. In Section 2 we discuss related work. In Section 3 we our definitions and give background on groups with efficiently computable bilinear maps. We then give our construction in Section 4. We then present our implementation and performance measurements in Section 5. Finally, we conclude in Section 6.

Related Work

Sahai and Waters [START_REF] Sahai | Fuzzy Identity Based Encryption[END_REF] introduced attribute-based encryption (ABE) as a new means for encrypted access control. In an attribute-based encryption system ciphertexts are not necessarily encrypted to one particular user as in traditional public key cryptography. Instead both users' private keys and ciphertexts will be associated with a set of attributes or a policy over attributes. A user is able to decrypt a ciphertext if there is a "match" between his private key and the ciphertext. In their original system Sahai and Waters presented a Threshold ABE system in which ciphertexts were labeled with a set of attributes S and a user's private key was associated with both a threshold parameter k and another set of attributes S ′ . In order for a user to decrypt a ciphertext at least k attributes must overlap between the ciphertext and his private keys. One of the primary original motivations for this was to design an error-tolerant (or Fuzzy) identity-based encryption [START_REF] Shamir | Identity Based Cryptosystems and Signature Schemes[END_REF][START_REF] Boneh | Identity Based Encryption from the Weil Pairing[END_REF][START_REF] Cocks | An identity based encryption scheme based on quadratic residues[END_REF] scheme that could use biometric identities.

The primary drawback of the Sahai-Waters [START_REF] Sahai | Fuzzy Identity Based Encryption[END_REF] threshold ABE system is that the threshold semantics are not very expressive and therefore are limiting for designing more general systems. Goyal et al. introduced the idea of a more general key-policy attributebased encryption system. In their construction a ciphertext is associated with a set of attributes and a user's key can be associated with any monotonic treeaccess structure. 1 The construction of Goyal et al. can be viewed as an extension of the Sahai-Waters techniques where instead of embedding a Shamir [START_REF] Shamir | How to share a secret[END_REF] secret sharing scheme in the private key, the authority embeds a more general secret sharing scheme for monotonic access trees. Goyal et. al. also suggested the possibility of a ciphertext-policy ABE scheme, but did not offer any constructions.

Pirretti et al. [START_REF] Pirretti | Secure Atrribute-Based Systems[END_REF] gave an implementation of the threshold ABE encryption system, demonstrated different applications of attribute-based encryption schemes and addressed several practical notions such as key-revocation. In recent work, Chase [START_REF] Chase | Multi-authority attribute-based encryption[END_REF] gave a construction for a multi-authority attribute-based encryption system, where each authority would administer a different domain of attributes. The primary challenge in creating multi-authority ABE is to prevent collusion attacks between users that obtain key components from different authorities. While the Chase system used the threshold ABE system as its underlying ABE system at each authority, the problem of multi-authority ABE is in general orthogonal to finding more expressive ABE systems.

In addition, there is a long history of access control for data that is mediated by a server. See for example, [START_REF] Kang | Access control mechanisms for inter-organizational workflow[END_REF][START_REF] Gavriloaie | No registration needed: How to use declarative policies and negotiation to access sensitive resources on the semantic web[END_REF][START_REF] Yu | A unified scheme for resource protection in automated trust negotiation[END_REF][START_REF] Li | Automated trust negotiation using cryptographic credentials[END_REF][START_REF] Harney | Principles of policy in secure groups[END_REF][START_REF] Mcdaniel | Methods and limitations of security policy reconciliation[END_REF] and the references therein. We focus on encrypted access control, where data is protected even if the server storing the data is compromised.

Collusion Resistance and Attribute-Based Encryption

The defining property of Attribute-Based Encryption systems are their resistance to collusion attacks. This property is critical for building cryptographic access control systems; otherwise, it is impossible to guarantee that a system will exhibit the desired security properties as there will exist devastating attacks from an attacker that manages to get a hold of a few private keys. While we might consider ABE systems with different flavors of expressibility, prior work [START_REF] Sahai | Fuzzy Identity Based Encryption[END_REF][START_REF] Goyal | Attribute Based Encryption for Fine-Grained Access Conrol of Encrypted Data[END_REF] made it clear that collusion resistance is a required property of any ABE system.

Before attribute-based encryption was introduced there were other systems that attempted to address access control of encrypted data [START_REF] Smart | Access control using pairing based cryptography[END_REF][START_REF] Bradshaw | Concealing complex policies with hidden credentials[END_REF] by using secret sharing schemes [START_REF] Ito | Secret Sharing Scheme Realizing General Access Structure[END_REF][START_REF] Brickell | Some ideal secret sharing schemes[END_REF][START_REF] Shamir | How to share a secret[END_REF][START_REF] Blakley | Safeguarding cryptographic keys[END_REF][START_REF] Benaloh | Generalized Secret Sharing and Monotone Functions[END_REF] combined with identity-based encryption; however, these schemes did not address resistance to collusion attacks. Recently, Kapadia, Tsang, and Smith [START_REF] Kapadia | Attribute-based publishing with hidden credentials and hidden policies[END_REF] gave a cryptographic access control scheme that employed proxy servers. Their work explored new methods for employing proxy servers to hide policies and use non-monontonic access control for small universes of attributes. We note that although they called this scheme a form of CP-ABE, the scheme does not have the property of collusion resistance. As such, we believe that their work should not be considered in the class of attribute-based encryption systems due to its lack of security against collusion attacks.

Background

We first give formal definitions for the security of ciphertext policy attribute based encryption (CP-ABE). Next, we give background information on bilinear maps. Like the work of Goyal et al. [START_REF] Goyal | Attribute Based Encryption for Fine-Grained Access Conrol of Encrypted Data[END_REF] we define an access structure and use it in our security definitions. However, in these definitions the attributes will describe the users and the access structures will be used to label different sets of encrypted data.

Definitions

Definition 1 (Access Structure [START_REF] Beimel | Secure Schemes for Secret Sharing and Key Distribution[END_REF]) Let {P 1 , P 2 , . . . , P n } be a set of parties. A collection A ⊆ 2 {P1,P2,...,Pn} is monotone if ∀B, C : if B ∈ A and B ⊆ C then C ∈ A. An access structure (respectively, monotone access structure) is a collection (respectively, monotone collection) A of non-empty subsets of {P 1 , P 2 , . . . , P n }, i.e., A ⊆ 2 {P1,P2,...,Pn} \{∅}. The sets in A are called the authorized sets, and the sets not in A are called the unauthorized sets.

In our context, the role of the parties is taken by the attributes. Thus, the access structure A will contain the authorized sets of attributes. We restrict our attention to monotone access structures. However, it is also possible to (inefficiently) realize general access structures using our techniques by having the not of an attribute as a separate attribute altogether. Thus, the number of attributes in the system will be doubled. From now on, unless stated otherwise, by an access structure we mean a monotone access structure.

An ciphertext-policy attribute based encryption scheme consists of four fundamental algorithms: Setup, Encrypt, KeyGen, and Decrypt. In addition, we allow for the option of a fifth algorithm Delegate.

Setup. The setup algorithm takes no input other than the implicit security parameter. It outputs the public parameters PK and a master key MK.

Encrypt(PK, M, A). The encryption algorithm takes as input the public parameters PK, a message M , and an access structure A over the universe of attributes. The algorithm will encrypt M and produce a ciphertext CT such that only a user that possesses a set of attributes that satisfies the access structure will be able to decrypt the message. We will assume that the ciphertext implicitly contains A.

Key Generation(MK, S).

The key generation algorithm takes as input the master key MK and a set of attributes S that describe the key. It outputs a private key SK.

Decrypt(PK, CT, SK). The decryption algorithm takes as input the public parameters PK, a ciphertext CT, which contains an access policy A, and a private key SK, which is a private key for a set S of attributes. If the set S of attributes satisfies the access structure A then the algorithm will decrypt the ciphertext and return a message M . Delegate(SK, S). The delegate algorithm takes as input a secret key SK for some set of attributes S and a set S ⊆ S. It output a secret key SK for the set of attributes S.

We now describe a security model for ciphertextpolicy ABE schemes. Like identity-based encryption schemes [START_REF] Shamir | Identity Based Cryptosystems and Signature Schemes[END_REF][START_REF] Boneh | Identity Based Encryption from the Weil Pairing[END_REF][START_REF] Cocks | An identity based encryption scheme based on quadratic residues[END_REF] the security model allows the adversary to query for any private keys that cannot be used to decrypt the challenge ciphertext. In CP-ABE the ciphertexts are identified with access structures and the private keys with attributes. It follows that in our security definition the adversary will choose to be challenged on an encryption to an access structure A * and can ask for any private key S such that S does not satisfy S * . We now give the formal security game.

Security Model for CP-ABE

Setup. The challenger runs the Setup algorithm and gives the public parameters, PK to the adversary.

Phase 1. The adversary makes repeated private keys corresponding to sets of attributes S 1 , . . . , S q1 .

Challenge. The adversary submits two equal length messages M 0 and M 1 . In addition the adversary gives a challenge access structure A * such that none of the sets S 1 , . . . , S q1 from Phase 1 satisfy the access structure. The challenger flips a random coin b, and encrypts M b under A * . The ciphertext CT * is given to the adversary.

Phase 2. Phase 1 is repeated with the restriction that none of sets of attributes S q1+1 , . . . , S q satisfy the access structure corresponding to the challenge.

Guess. The adversary outputs a guess b ′ of b.

The advantage of an adversary A in this game is defined as Pr

[b ′ = b] -1 2 .
We note that the model can easily be extended to handle chosen-ciphertext attacks by allowing for decryption queries in Phase 1 and Phase 2.

Definition 2 An ciphertext-policy attribute-based encryption scheme is secure if all polynomial time adversaries have at most a negligible advantage in the above game.

Bilinear Maps

We present a few facts related to groups with efficiently computable bilinear maps.

Let G 0 and G 1 be two multiplicative cyclic groups of prime order p. Let g be a generator of G 0 and e be a bilinear map, e : G 0 × G 0 → G 1 . The bilinear map e has the following properties:

1. Bilinearity: for all u, v ∈ G 0 and a, b ∈ Z p , we have e(u a , v b ) = e(u, v) ab . 2. Non-degeneracy: e(g, g) = 1.

We say that G 0 is a bilinear group if the group operation in G 0 and the bilinear map e : G 0 × G 0 → G 1 are both efficiently computable. Notice that the map e is symmetric since e(g a , g b ) = e(g, g) ab = e(g b , g a ).

Our Construction

In this section we provide the construction of our system. We begin by describing the model of access trees and attributes for respectively describing ciphertexts and private keys. Next, we give the description of our scheme. Finally, we follow with a discussion of security, efficiency, and key revocation. We provide our proof of security in Appendix A.

Our Model

In our construction private keys will be identified with a set S of descriptive attributes. A party that wishes to encrypt a message will specify through an access tree structure a policy that private keys must satisfy in order to decrypt.

Each interior node of the tree is a threshold gate and the leaves are associated with attributes. (We note that this setting is very expressive. For example, we can represent a tree with "AND" and "OR" gates by using respectively 2 of 2 and 1 of 2 threshold gates.) A user will be able to decrypt a ciphertext with a given key if and only if there is an assignment of attributes from the private key to nodes of the tree such that the tree is satisfied. We use the same notation as [START_REF] Goyal | Attribute Based Encryption for Fine-Grained Access Conrol of Encrypted Data[END_REF] to describe the access trees, even though in our case the attributes are used to identify the keys (as opposed to the data).

Access tree T . Let T be a tree representing an access structure. Each non-leaf node of the tree represents a threshold gate, described by its children and a threshold value. If num x is the number of children of a node x and k x is its threshold value, then 0 < k x ≤ num x . When k x = 1, the threshold gate is an OR gate and when k x = num x , it is an AND gate. Each leaf node x of the tree is described by an attribute and a threshold value k x = 1.

To facilitate working with the access trees, we define a few functions. We denote the parent of the node x in the tree by parent(x). The function att(x) is defined only if x is a leaf node and denotes the attribute associated with the leaf node x in the tree. The access tree T also defines an ordering between the children of every node, that is, the children of a node are numbered from 1 to num. The function index(x) returns such a number associated with the node x. Where the index values are uniquely assigned to nodes in the access structure for a given key in an arbitrary manner.

Satisfying an access tree. Let T be an access tree with root r. Denote by T x the subtree of T rooted at the node x. Hence T is the same as T r . If a set of attributes γ satisfies the access tree T x , we denote it as T x (γ) = 1. We compute T x (γ) recursively as follows. If x is a non-leaf node, evaluate T x ′ (γ) for all children x ′ of node x. T x (γ) returns 1 if and only if at least k x children return 1. If x is a leaf node, then T x (γ) returns 1 if and only if att(x) ∈ γ.

Our Construction

Let G 0 be a bilinear group of prime order p, and let g be a generator of G 0 . In addition, let e : G 0 × G 0 → G 1 denote the bilinear map. A security parameter, κ, will determine the size of the groups. We also define the Lagrange coefficient ∆ i,S for i ∈ Z p and a set, S, of elements in Z p : ∆ i,S (x) = j∈S,j =i x-j i-j . We will additionally employ a hash function H : {0, 1} * → G 0 that we will model as a random oracle. The function will map any attribute described as a binary string to a random group element. Our construction follows.

Setup. The setup algorithm will choose a bilinear group G 0 of prime order p with generator g. Next it will choose two random exponents α, β ∈ Z p . The public key is published as:

PK = G 0 , g, h = g β , f = g 1/β , e(g, g) α
and the master key MK is (β, g α ). (Note that f is used only for delegation.) Encrypt(PK, M, T ). The encryption algorithm encrypts a message M under the tree access structure T . The algorithm first chooses a polynomial q x for each node x (including the leaves) in the tree T . These polynomials are chosen in the following way in a topdown manner, starting from the root node R. For each node x in the tree, set the degree d x of the polynomial q x to be one less than the threshold value k x of that node, that is,

d x = k x -1.
Starting with the root node R the algorithm chooses a random s ∈ Z p and sets q R (0) = s. Then, it chooses d R other points of the polynomial q R randomly to define it completely. For any other node x, it sets q x (0) = q parent(x) (index(x)) and chooses d x other points randomly to completely define q x . Let, Y be the set of leaf nodes in T . The ciphertext is then constructed by giving the tree access structure T and computing

CT = T , C = M e(g, g) αs , C = h s , ∀y ∈ Y : C y = g qy(0) , C ′ y = H(att(y)) qy(0) .

KeyGen(MK, S).

The key generation algorithm will take as input a set of attributes S and output a key that identifies with that set. The algorithm first chooses a random r ∈ Z p , and then random r j ∈ Z p for each attribute j ∈ S. Then it computes the key as

SK = D = g (α+r)/β , ∀j ∈ S : D j = g r • H(j) rj , D ′ j = g rj .
Delegate(SK, S). The delegation algorithm takes in a secret key SK, which is for a set S of attributes, and another set S such that S ⊆ S. The secret key is of the form SK = (D, ∀j ∈ S : D j , D ′ j ). The algorithm chooses random r and rk ∀k ∈ S. Then it creates a new secret key as

SK = ( D = Df r , ∀k ∈ S : Dk = D k g r H(k) rk , D′ k = D ′ k g rk ).
The resulting secret key SK is a secret key for the set S. Since the algorithm re-randomizes the key, a delegated key is equivalent to one received directly from the authority.

Decrypt(CT, SK). We specify our decryption procedure as a recursive algorithm. For ease of exposition we present the simplest form of the decryption algorithm and discuss potential performance improvements in the next subsection.

We first define a recursive algorithm DecryptNode(CT, SK, x) that takes as input a ciphertext CT = (T , C, C, ∀y ∈ Y : C y , C ′ y ), a private key SK, which is associated with a set S of attributes, and a node x from T .

If the node x is a leaf node then we let i = att(x) and define as follows:

If i ∈ S, then DecryptNode(CT, SK, x) = e(D i , C x ) e(D ′ i , C ′ x ) = e g r • H(i) ri , h qx(0) e(g ri , H(i) qx(0) )
= e(g, g) rqx(0) .

If i / ∈ S, then we define DecryptNode(CT, SK, x) = ⊥.

We now consider the recursive case when x is a non-leaf node. The algorithm DecryptNode(CT, SK, x) then proceeds as follows: For all nodes z that are children of x, it calls DecryptNode(CT, SK, z) and stores the output as F z . Let S x be an arbitrary k x -sized set of child nodes z such that F z = ⊥. If no such set exists then the node was not satisfied and the function returns ⊥.

Otherwise, we compute

F x = z∈Sx F ∆ i,S ′ x (0) z , where i=index(z) S ′ x ={index(z):z∈Sx} = z∈Sx (e(g, g) r•qz (0) ) ∆ i,S ′ x (0) = z∈Sx (e(g, g) r•q parent(z) (index(z)) ) ∆ i,S ′ x (0) (by construction) = z∈Sx e(g, g) r•qx(i)•∆ i,S ′ x (0)
= e(g, g) r•qx(0) (using polynomial interpolation)

and return the result. Now that we have defined our function DecryptNode, we can define the decryption algorithm. The algorithm begins by simply calling the function on the root node R of the tree T . If the tree is satisfied by S we set A = DecryptNode(CT, SK, r) = e(g, g) rqR(0) = e(g, g) rs . The algorithm now decrypts by computing C/(e(C, D)/A) = C/ e h s , g (α+r)/β /e(g, g) rs = M.

Discussion

We now provide a brief discussion about the security intuition for our scheme (a full proof is given in Appendix A), our scheme's efficiency, and how we might handle key revocation.

Security intuition. As in previous attribute-based encryption schemes the main challenge in designing our scheme was to prevent against attacks from colluding users. Like the scheme of Sahai and Waters [START_REF] Sahai | Fuzzy Identity Based Encryption[END_REF] our solution randomizes users private keys such that they cannot be combined; however, in our solution the secret sharing must be embedded into the ciphertext instead to the private keys. In order to decrypt an attacker clearly must recover e(g, g) αs . In order to do this the attacker must pair C from the ciphertext with the D component from some user's private key. This will result in the desired value e(g, g) αs , but blinded by some value e(g, g) rs . This value can be blinded out if and only if enough the user has the correct key components to satisfy the secret sharing scheme embedded in the ciphertext. Collusion attacks won't help since the blinding value is randomized to the randomness from a particular user's private key.

While we described our scheme to be secure against chosen plaintext attacks, the security of our scheme can efficiently be extended to chosen ciphertext attacks by applying a random oracle technique such as that of the the Fujisaki-Okamoto transformation [START_REF] Fujisaki | Secure integration of asymmetric and symmetric encryption schemes[END_REF]. Alternatively, we can leverage the delegation mechanism of our scheme and apply the Cannetti, Halevi, and Katz [START_REF] Canetti | Chosen Ciphertext Security from Identity Based Encryption[END_REF] method for achieving CCA-security.

Efficiency. The efficiencies of the key generation and encryption algorithms are both fairly straightforward. The encryption algorithm will require two exponentiations for each leaf in the ciphertext's access tree. The ciphertext size will include two group elements for each tree leaf. The key generation algorithm requires two exponentiations for every attribute given to the user, and the private key consists of two group elements for "a : *0**" "a : 0***" "a : **0*" "a : ***0" every attribute. In its simplest form, the decryption algorithm could require two pairings for every leaf of the access tree that is matched by a private key attribute and (at most2 ) one exponentiation for each node along a path from such a leaf to the root. However, there might be several ways to satisfy a policy, so a more intelligent algorithm might try to optimize along these lines. In our implementation description in Section 5 we described various performance enhancements. Key-revocation and numerical attributes. Key-Revocation is typically a difficult issue in identitybased encryption [START_REF] Shamir | Identity Based Cryptosystems and Signature Schemes[END_REF][START_REF] Boneh | Identity Based Encryption from the Weil Pairing[END_REF] and related schemes. The core challenge is that since the party encrypting the data does not obtain the receiver's certificate on-line, he is not able to check if the the receiving party is revoked. In attribute-based encryption the problem is even more tricky since several different users might match the decryption policy. The usual solution is to append to each of the identities or descriptive attributes a date for when the attribute expires. For instance, Pirretti et al. [START_REF] Pirretti | Secure Atrribute-Based Systems[END_REF] suggest extending each attribute with an expiration date. For example, instead of using the attribute "Computer Science" we might use the attribute "Computer Science: Oct 17, 2006". This type of method has a several shortcomings. Since the attributes incorporate an exact date there must be agreement on this between the party encrypting the data and the key issuing authority. If we wish for a party to be able to specify policy about revocation dates on a fine-grained scale, users will be forced to go often to the authority and maintain a large amount of private key storage, a key for every time period.

Ideally, we would like an attribute-based encryption system to allow a key authority to give out a single key with some expiration date X rather than a separate key for every time period before X. When a party encrypts a message on some date Y , a user with a key expiring on date X should be able to decrypt iff X ≥ Y and the rest of the policy matches the user's attributes. In this manner, different expiration dates can be given to different users and there does not need to be any close coordination between the parties encrypting data and the authority.

This sort of functionality can be realized by extending our attributes to support numerical values and our policies to support integer comparisons. To represent a numerical attribute "a = k" for some n-bit integer k we convert it into a "bag of bits" representation, producing n (non-numerical) attributes which specify the value of each bit in k. As an example, to give out a private key with the 4-bit attribute "a = 9", we would instead include "a : 1***", "a : *0***", "a : **0*", and "a : ***1" in the key. We can then use policies of AND and OR gates to implement integer comparisons over such attributes, as shown for "a < 11" in Figure 1. There is a direct correspondence between the bits of the constant 11 and the choice of gates. Policies for ≤, >, ≥, and = can be implemented similarly with at most n gates, or possibly fewer depending on the constant. It is also possible to construct comparisons between two numerical attributes (rather than an attribute and a constant) using roughly 3n gates, although it is less clear when this would be useful in practice.

Implementation

In this section we discuss practical issues in implementing the construction of Section 4, including several optimizations, a description of the toolkit we have developed, and measurements of its performance.

Decryption Efficiency Improvements

While little can be done to reduce the group operations necessary for the setup, key generation, and encryption algorithms, the efficiency of the decryption algorithm can be improved substantially with novel techniques. We explain these improvements here and later give measurements showing their effects in Section 5.3.

Optimizing the decryption strategy. The recursive algorithm given in Section 4 results in two pairings for each leaf node that is matched by a private key attribute, and up to one exponentiation for every node occurring along the path from such a node to the root (not including the root). The final step after the recursive portion adds an additional pairing. Of course, at each internal node with threshold k, the results from all but k of its children are thrown away. By considering ahead of time which leaf nodes are satisfied and picking a subset of them which results in the satisfaction of the entire access tree, we may avoid evaluating DecryptNode where the result will not ultimately be used.

More precisely, let M be a subset of the nodes in an access tree T . We define restrict(T , M ) to be the access tree formed by removing the following nodes from T (while leaving the thresholds unmodified). First, we remove all nodes not in M . Next we remove any node not connected to the original root of T along with any internal node x that now has fewer children than its threshold k x . This is repeated until no further nodes are removed, and the result is restrict(T , M ). So given an access tree T and a set of attributes γ that satisfies it, the natural problem is to pick a set M such that γ satisfies restrict(T , M ) and the number of leaves in M is minimized (considering pairing to be the most expensive operation). This is easily accomplished with a straightforward recursive algorithm that makes a single traversal of the tree. We may then use DecryptNode on restrict(T , M ) with the same result.

Direct computation of DecryptNode. Further improvements may be gained by abandoning the DecryptNode function and making more direct computations. Intuitively, we imagine flattening out the tree of recursive calls to DecryptNode, then combining the exponentiations into one per (used) leaf node. Precisely, let T be an access tree with root r, γ be a set of attributes, and M ⊆ T be such that γ satisfies restrict(T , M ). Assume also that M is minimized so that no internal node has more children than its threshold. Let L ⊆ M be the leaf nodes in M . Then for each ℓ ∈ L, we denote the path from ℓ to r as ρ(ℓ) = (ℓ, parent(ℓ), parent(parent(ℓ)), . . . r) . Also, denote the set of siblings of a node x (including itself) as sibs(x) = { y | parent(x) = parent(y) }. Given this notation, we may proceed to directly compute the result of DecryptNode(CT, SK, r). First, for each ℓ ∈ L, compute z ℓ as follows.

z ℓ = x∈ρ(ℓ) x =r ∆ i,S (0)
where

i=index(x) S={ index(y) | y ∈ sibs(x) } Then DecryptNode(CT, SK, r) = ℓ∈L i=att(ℓ) e(D i , C ℓ ) e(D ′ i , C ′ ℓ ) z ℓ .
Using this method, the number of exponentiations in the entire decryption algorithm is reduced from |M |-1 (i.e., one for every node but the root) to |L|. The number of pairings is 2|L|.

Merging pairings. Still further reductions (this time in the number of pairings) are possible by combining leaves using the same attribute. If att(ℓ 1 ) = att(ℓ 2 ) = i for some ℓ 1 , ℓ 2 in L, then

e(Di, C ℓ 1 ) e(D ′ i , C ′ ℓ 1 ) ! z ℓ 1 • e(Di, C ℓ 2 ) e(D ′ i , C ′ ℓ 2 ) ! z ℓ 2 = e(Di, C z ℓ 1 ℓ 1 ) e(D ′ i , C ′ z ℓ 1 ℓ 1 ) • e(Di, C z ℓ 2 ℓ 2 ) e(D ′ i , C ′ z ℓ 2 ℓ 2 ) = e(Di, C z ℓ 1 ℓ 1 • C z ℓ 2 ℓ 2 ) e(D ′ i , C ′ z ℓ 1 ℓ 1 • C ′ z ℓ 2 ℓ 2
) .

Using this fact, we may combine all the pairings for each distinct attribute in L, reducing the total pairings to 2m, where m is the number of distinct attributes appearing in L. Note, however, that the number of exponentiations increases, and some of the exponentiations must now be performed in G 0 rather than G 1 . Specifically, if m ′ is the number of leaves sharing their attribute with at least one other leaf, we must perform 2m ′ exponentiations in G 0 and |L|m ′ in G 1 , rather than zero and |L| respectively. If exponentiations in G 0 (an elliptic curve group) are slower than in G 1 (a finite field of the same order), this technique has the potential to increase decryption time. We further investigate this tradeoff in Section 5.3.

The cpabe Toolkit

We have implemented the construction of Section 4 as a convenient set of tools we call the cpabe package [START_REF] Bethencourt | The cpabe toolkit[END_REF], which has been made available on the web under the GPL. The implementation uses the Pairing Based Cryptography (PBC) library [START_REF] Lynn | The Pairing-Based Cryptography (PBC) library[END_REF]. 3 The interface of the toolkit is designed for straightforward invocation by larger systems in addition to manual usage. It provides four command line tools.

cpabe-setup

Generates a public key and a master key.

cpabe-keygen

Given a master key, generates a private key for a set of attributes, compiling numerical attributes as necessary.

°cpabe-keygen -o sara priv key pub key master key \ sysadmin it department ³office = 1431³ ³hire date = ³ date +%s °cpabe-keygen -o kevin priv key pub key master key \ business staff strategy team ³executive level = 7³ \ ³office = 2362³ ³hire date = ³ date +%s °cpabe-enc pub key security report.pdf (sysadmin and (hire date < 946702800 or security team)) or (business staff and 2 of (executive level >= 5, audit group, strategy team))

Figure 2. Example usage of the cpabe toolkit. Two private keys are issued for various sets of attributes (normal and numerical) using cpabe-keygen. A document is encrypted under a complex policy using cpabe-enc.

cpabe-enc

Given a public key, encrypts a file under an access tree specified in a policy language. cpabe-dec Given a private key, decrypts a file.

The cpabe toolkit supports the numerical attributes and range queries described in Section 4.3 and provides a familiar language of expressions with which to specify access policies. These features are illustrated in the sample usage session of Figure 2.

In this example, the cpabe-keygen tool was first used to produce private keys for two new employees, "Sara" and "Kevin". A mix of regular and numerical attributes were specified; in particular shell backticks were used to store the current timestamp (in seconds since 1970) in the "hire date" attribute. The cpabe-enc tool was then used to encrypt a security sensitive report under a complex policy (in this case specified on the standard input). The policy allows decryption by sysadmins with at least a certain seniority (hired before January 1, 2000) and those on the security team. Members of the business staff may decrypt if they are in the audit group and the strategy team, or if they are in one of those teams and are an executive of "level" five or more. So in this example, Kevin would be able to use the key stored as kevin priv key to decrypt the resulting document, but Sara would not be able to use hers to decrypt the document. As demonstrated by this example, the policy language allows the general threshold gates of the underlying scheme, but also provides AND and OR gates for convenience. These are appropriately merged to simplify the tree, that is, specifying the policy "(a and b) and (c and d and e)" would result in a single gate. The tools also handle compiling numerical attributes to their "bag of bits" representation and comparisons into their gate-level implementation.

Performance Measurements

We now provide some information on the performance achieved by the cpabe toolkit. Figure 3 displays measurements of private key generation time, encryption time, and decryption time produced by running cpabe-keygen, cpabe-enc, and cpabe-dec on a range of problem sizes. The measurements were taken on a modern workstation. 4 The implementation uses a 160-bit elliptic curve group based on the supersingular curve y 2 = x 3 +x over a 512-bit finite field. On the test machine, the PBC library can compute pairings in approximately 5.5ms, and exponentiations in G 0 and G 1 take about 6.4ms and 0.6ms respectively. Randomly selecting elements (by reading from the Linux kernel's /dev/urandom) is also a significant operation, requiring about 16ms for G 0 and 1.6ms for G 1 .

As expected, cpabe-keygen runs in time precisely linear in the number of attributes associated with the key it is issuing. The running time of cpabe-enc is also almost perfectly linear with respect to the number of leaf nodes in the access policy. The polynomial operations at internal nodes amount to a modest number of multiplications and do not significantly contribute to the running time. Both remain quite feasible for even the largest problem instances.

The performance of cpabe-dec is somewhat more interesting. It is slightly more difficult to measure in the absence of a precise application, since the decryption time can depend significantly on the particular access trees and set of attributes involved. In an at- tempt to average over this variation, we ran cpabe-dec on a series of ciphertexts that had been encrypted under randomly generated policy trees of various sizes. The trees were generated by starting with only a root node, then repeatedly adding a child to a randomly selected node until the desired number of leaf nodes was reached. At that point random thresholds were selected for each internal node. Since the time to decrypt also depends on the particular attributes available, for each run of cpabe-dec, we selected a key uniformly at random from all keys satisfying the policy. This was accomplished by iteratively taking random subsets of the attributes appearing in leaves of the tree and discarding those that did not satisfy it. A series of runs of cpabe-dec conducted in this manner produced the running times displayed in Figure 3 (c).

These measurements give some insight into the effects of the optimizations described in Section 5.1 (all of which are implemented in the system). The line marked "naive" denotes the decryption time resulting from running the recursive DecryptNode algorithm and arbitrarily selecting nodes to satisfy each threshold gate. By ensuring that the final number of leaf nodes is minimized when making these decisions and replacing the DecryptNode algorithm with the "flattened" algorithm to reduce exponentiations, we obtain the improved times denoted "flatten". Perhaps most interestingly, employing the technique for merging pairings between leaf nodes sharing the same attribute, denoted "merge", actually increases running time in this case, due to fact that exponentiations are more expensive in G 0 than in G 1 .

In summary, cpabe-keygen and cpabe-enc run in a predictable amount of time based on the number of attributes in a key or leaves in a policy tree. The performance of cpabe-dec depends on the specific access tree of the ciphertext and the attributes available in the private key, and can be improved by some of the optimizations considered in Section 5.1. In all cases, the toolkit consumes almost no overhead beyond the cost of the underlying group operations and random selection of elements. Large private keys and policies are possible in practice while maintaining reasonable running times.

Conclusions and Open Directions

We created a system for Ciphertext-Policy Attribute Based Encryption. Our system allows for a new type of encrypted access control where user's private keys are specified by a set of attributes and a party encrypting data can specify a policy over these attributes specifying which users are able to decrypt. Our system allows policies to be expressed as any monotonic tree access structure and is resistant to collusion attacks in which an attacker might obtain multiple private keys. Finally, we provided an implementation of our system, which included several optimization techniques.

In the future, it would be interesting to consider attribute-based encryption systems with different types of expressibility. While, Key-Policy ABE and Ciphertext-Policy ABE capture two interesting and complimentary types of systems there certainly exist other types of systems. The primary challenge in this line of work is to find a new systems with elegant forms of expression that produce more than an arbitrary combination of techniques.

One limitation of our system is that it is proved secure under the generic group heuristic. We believe an important endeavor would be to prove a system secure under a more standard and non-interactive assumption. This type of work would be interesting even if it resulted in a moderate loss of efficiency from our existing system.

A Security Proof

In this section, we use the generic bilinear group model of [START_REF] Boneh | Hierarchical identity based encryption with constant size ciphertext[END_REF][START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF] and the random oracle model [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF] to argue that no efficient adversary that acts generically on the groups underlying our scheme can break the security of our scheme with any reasonable probability. At an intuitive level, this means that if there are any vulnerabilities in our scheme, then these vulnerabilities must exploit specific mathematical properties of elliptic curve groups or cryptographic hash functions used when instantiating our construction.

While from a security standpoint, it would be preferable to have a proof of security that reduces the problem of breaking our scheme to a well-studied complexity-theoretic problem, there is reason to believe that such reductions will only exist for more complex (and less efficient) schemes than the one we give here. We also stress that ours is the first construction which offers the security properties we are proposing here; we strongly encourage further research that can place this kind of security on a firmer theoretical foundation.

The generic bilinear group model. We follow [START_REF] Boneh | Hierarchical identity based encryption with constant size ciphertext[END_REF] here: We consider two random encodings ψ 0 , ψ 1 of the additive group F p , that is injective maps ψ 0 , ψ 1 : F p → {0, 1} m , where m > 3 log(p). For i = 0, 1 we write G i = {ψ i (x) : x ∈ F p }. We are given oracles to compute the induced group action on G 0 , G 1 and an oracle to compute a non-degenerate bilinear map e : G 0 × G 0 → G 1 . We are also given a random oracle to represent the hash function H. We refer to G 0 as a generic bilinear group.

The following theorem gives a lower bound on the advantage of a generic adversary in breaking our CP-ABE scheme.

Theorem 1 Let ψ 0 , ψ 1 , G 0 , G 1 be defined as above. For any adversary A, let q be a bound on the total number of group elements it receives from queries it makes to the oracles for the hash function, groups G 0 and G 1 , and the bilinear map e, and from its interaction with the CP-ABE security game. Then we have that the advantage of the adversary in the CP-ABE security game is O(q 2 /p).

Proof. We first make the following standard observation, which follows from a straightforward hybrid argument: In the CP-ABE security game, the challenge ciphertext has a component C which is randomly either M 0 e(g, g) αs or M 1 e(g, g) αs . We can instead consider a modified game in which C is either e(g, g) αs or e(g, g) θ , where θ is selected uniformly at random from F p , and the adversary must decide which is the case. It is clear that any adversary that has advantage ǫ in the CP-ABE game can be transformed into an adversary that has advantage at least ǫ/2 in the modified CP-ABE game. (To see this consider two hybrids: one in which the adversary must distinguish between M 0 e(g, g) αs and e(g, g) θ ; another in which it must distinguish between e(g, g) θ and M 1 e(g, g) αs . Clearly both of these are equivalent to the modified game above.) From now on, we will bound the adversary's advantage in the modified game.

We now introduce some notation for the simulation of the modified CP-ABE game. Let g = ψ 0 (1) (we will write g x to denote ψ 0 (x), and e(g, g) y to denote ψ 1 (y) in the future).

At setup time, the simulation chooses α, β at random from F p (which we associate with the integers from 0 to p -1). Note that if β = 0, an event that happens with probability 1/p, then setup is aborted, just as it would be in the actual scheme. The public parameters h = g β , f = g 1/β , and e(g, g) α are sent to the adversary.

When the adversary (or simulation) calls for the evaluation of H on any string i, a new random value t i is chosen from F p (unless it has already been chosen), and the simulation provides g ti as the response to H(i).

When the adversary makes its j'th key generation query for the set S j of attributes, a new random value r (j) is chosen from F p , and for every i ∈ S j , new random values r (j) i are chosen from F p . The simulator then computes: D = g (α+r (j) )/β and for each i ∈ S j , we have D i = g r (j) +tir (j) i and D ′ i = g r (j) i . These values are passed onto the adversary.

When the adversary asks for a challenge, giving two messages M 0 , M 1 ∈ G 1 , and the access tree A, the simulator does the following. First, it chooses a random s from F p . Then it uses the linear secret sharing scheme associated with A (as described in Section 4) to construct shares λ i of s for all relevant attributes i. We stress again that the λ i are all chosen uniformly and independently at random from F p subject to the linear conditions imposed on them by the secret sharing scheme. In particular, the choice of the λ i 's can be perfectly simulated by choosing ℓ random values µ 1 , . . . µ ℓ uniformly and independently from F p , for some value of ℓ, and then letting the λ i be fixed public linear combinations of the µ k 's and s. We will often think of the λ i as written as such linear combinations of these independent random variables later.

Finally, the simulation chooses a random θ ∈ F p , and constructs the encryption as follows: C = e(g, g) θ and C = h s . For each relevant attribute i, we have C i = g λi , and C ′ i = g tiλi . These values are sent to the adversary.

(Note, of course, that if the adversary asks for a decryption key for a set of attributes that pass the challenge access structure, then the simulation does not issue the key; similarly if the adversary asks for a challenge access structure such that one of the keys already issued pass the access structure, then the simulation aborts and outputs a random guess on behalf of the adversary, just as it would in the real game.)

We will show that with probability 1 -O(q 2 /p), taken over the randomness of the the choice of variable values in the simulation, the adversary's view in this simulation is identically distributed to what its view would have been if it had been given C = e(g, g) αs . We will therefore conclude that the advantage of the adversary is at most O(q 2 /p), as claimed.

When the adversary makes a query to the group oracles, we may condition on the event that (1) the adversary only provides as input values it received from the simulation, or intermediate values it already obtained from the oracles, and (2) there are p distinct values in the ranges of both φ 0 and φ 1 . (This event happens with overwhelming probability 1-O(1/p).) As such, we may keep track of the algebraic expressions being called for from the oracles, as long as no "unexpected collisions" happen. More precisely, we think of an oracle query as being a rational function ν = η/ξ in the variables θ, α, β, t i 's, r (j) 's, r (j) i 's, s, and µ k 's. An unexpected collision would be when two queries corresponding to two distinct formal rational functions η/ξ = η ′ /ξ ′ but where due to the random choices of these variables' values, we have that the values of η/ξ and η ′ /ξ ′ coincide.

We now condition on the event that no such unexpected collisions occur in either group G 0 or G 1 . For any pair of queries (within a group) corresponding to distinct rational functions η/ξ and η ′ /ξ ′ , a collision occurs only if the non-zero polynomial ηξ ′ξη ′ evaluates to zero. Note that the total degree of ηξ ′ξη ′ is in our case at most 5. By the Schwartz-Zippel lemma [START_REF] Schwartz | Fast probabilistic algorithms for verification of polynomial identities[END_REF][START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF], the probability of this event is O(1/p). By a union bound, the probability that any such collision happens is at most O(q 2 /p). Thus, we can condition on no such collision happening and still maintain 1 -O(q 2 /p) of the probability mass.

Now we consider what the adversary's view would have been if we had set θ = αs. We will show that subject to the conditioning above, the adversary's view would have been identically distributed. Since we are in the generic group model where each group element's representation is uniformly and independently chosen, the only way that the adversary's view can differ in the case of θ = αs is if there are two queries ν and ν ′ into G 1 such that ν = ν ′ but ν| θ=αs = ν ′ | θ=αs . We will show that this never happens. Suppose not.

t i t i ′ λ i t i ′ t i t i ′ λ i ′ t i r (j
Recall that since θ only occurs as e(g, g) θ , which lives in G 1 , the only dependence that ν or ν ′ can have on θ is by having some additive terms of the form γ ′ θ, where γ ′ is a constant. Therefore, we must have that νν ′ = γαsγθ, for some constant γ = 0. We can then artificially add the query νν ′ + γθ = γαs to the adversary's queries. But we will now show that the adversary can never construct a query for e(g, g) γαs (subject to the conditioning we have already made), which will reach a contradiction and establish the theorem.

What is left now is to do a case analysis based on the information given to the adversary by the simulation. For sake of completeness and ease of reference for the reader, in Table 1 we enumerate over all rational function queries possible into G 1 by means of the bilinear map and the group elements given the adversary in the simulation, except those in which every monomial involves the variable β, since β will not be relevant to constructing a query involving αs. Here the variables i and i ′ are possible attribute strings, and the variables j and j ′ are the indices of secret key queries made by the adversary. These are given in terms of λ i 's, not µ k 's. The reader may check the values given in Table 1 against the values given in the simulation above.

In the group G 1 , in addition to the polynomials in the table above, the adversary also has access to 1 and α. The adversary can query for arbitrary linear combinations of these, and we must show that none of these polynomials can be equal to a polynomial of the form γαs. Recall that γ = 0 is a constant.

As seen above, the only way that the adversary can create a term containing αs is by pairing sβ with (α + r (j) )/β to get the term αs + sr (j) . In this way, the adversary could create a query polynomial containing γαs + j∈T γ j sr (j) , for some set T and constants γ, γ j = 0.

In order for the adversary to obtain a query polynomial of the form γαs, the adversary must add other linear combinations in order to cancel the terms of the form j∈T γ j sr (j) .

We observe (by referencing the table above) that the only other term that the adversary has access to that could involve monomials of the form sr (j) are obtained by pairing r (j) + t i r (j) i with some λ i ′ , since the λ i ′ terms are linear combinations of s and the µ k 's.

In this way, for sets T ′ j and constants γ (i,j,i ′ ) = 0, the adversary can construct a query polynomial of the form:

γαs+ j∈T   γ j sr (j) + (i,i ′ )∈T ′ j γ (i,j,i ′ ) λ i ′ r (j) + λ i ′ t i r (j) i   +other terms
Now, to conclude this proof, we do the following case analysis:

Case 1 There exists some j ∈ T such that the set of secret shares L j = {λ i ′ : ∃i : (i, i ′ ) ∈ T ′ j } do not allow for the reconstruction of the secret s.

If this is true, then the term sr (j) will not be canceled, and so the adversary's query polynomial cannot be of the form γαs.

Case 2 For all j ∈ T the set of secret shares L j = {λ i ′ : ∃i : (i, i ′ ) ∈ T ′ j } do allow for the reconstruction of the secret s.

Fix any j ∈ T . Consider S j , the set of attributes belonging to the j'th adversary key request. By the assumption that no requested key should pass the challenge access structure, and the properties of the secret sharing scheme, we know that the set L ′ j = {λ i : i ∈ S j } cannot allow for the reconstruction of s.

Thus, there must exist at least one share λ i ′ in L j such that λ i ′ is linearly independent of L ′ j when written in terms of s and the µ k 's. By the case analysis, this means that in the adversary's query there is a term of the form λ i ′ t i r (j) i for some i ∈ S j . However, (examining the table above), there is no term that the adversary has access to that can cancel this term. Therefore, any adversary query polynomial of this form cannot be of the form γαs.

Figure 1 .

 1 Figure 1. Policy tree implementing the integer comparison "a < 11".

  Decryption time with various levels of optimization.

Figure 3 .

 3 Figure 3. Performance of the cpabe toolkit.

Table 1 . Possible query types from the adversary.

 1 ) + t i t i ′ r (j) αs + sr (j) λ i λ i ′ t i λ i λ i ′ λ i ′ r (j) + λ i ′ t i r t i t i ′ λ i λ i ′ t i λ i r (j) i + t i t i ′ λ i r

	(j)
	i ′

i

Goyal et al. show in addition how to construct a key-policy ABE scheme for any linear secret sharing scheme.

Fewer exponentiations may occur if there is an unsatisfied internal node along the path.

PBC is in turn based on the GNU Multiple Precision arithmetic library (GMP), a high performance arbitrary precision arithmetic implementation suitable for cryptography.

The workstation's processor is a 64-bit, 3.2 Ghz Pentium 4.

* Supported the US Army Research Office under the CyberTA Grant No. W911NF-06-1-0316.

† Supported by NSF CNS-0524252 and the US Army Research Office under the CyberTA Grant No. W911NF-06-1-0316.