\section{Introduction}

Baryons in galaxy clusters, mainly in the form of stars in galaxies
and hot X-ray emitting plasma, trace the potential of the collapsed
structure in which they fall into. At the same time, their spatial
distribution and thermodynamical properties are affected by the
physical processes acting on them.
Measurement of direct cluster observables, such as stellar
  optical light and hot gas X-ray emission, is the only viable approach to
  investigate the physics that drives the evolution of such structures.
The observed relations among proxies of
the internal energy and entropy levels show that, at least in massive
systems, the dominant baryonic component of the intra--cluster medium
(ICM) has a luminosity, temperature and mass that well follow those
predicted under the assumptions of a plasma emitting by bremsstrahlung
and sitting in hydrostatic equilibrium with the underlying dark matter
potential (e.g. Kaiser 1991, Evrard \& Henry 1991).

Moreover, the fact that galaxy clusters are relatively well isolated
structures, that form in correspondence of the highest peaks
of the primordial gravitational fluctuations,
suggests that their relative baryon budget and the mass function are
highly sensitive tests of the geometry and matter content of the
Universe.  In particular, using X-ray observations of the baryonic
content to infer the gas and total mass of relaxed clusters in
hydrostatic equilibrium allows one to place a lower limit to the
cluster baryon mass fraction, which is expected to match the cosmic
value $\Omega_{\rm b}/\Omega_{\rm m}$ (White et al. 1993, Evrard 1997,
Mohr, Mathiesen \& Evrard 1999, Ettori \& Fabian 1999, Roussel, Sadat
\& Blanchard 2000, Allen et al. 2002, Ettori et al. 2003, Ettori 2003,
Allen et al. 2004).

The purpose of the present work is to use an extended set of
hydrodynamical simulations of galaxy clusters, treating a variety of
physical processes, to study how the spatial distribution of the
baryons, as contributed both by the stellar component and by the hot
X-ray emitting gas, are affected by the physical conditions within
clusters.
In this respect, our analysis extends
previous analyses of the baryon fraction in cluster simulations which
included only non--radiative physics (Evrard 1990, Metzler \& Evrard
1994, Navarro et al. 1995, Lubin et al. 1996, Eke et al. 1998, Frenk
et al. 1999, Mohr et al. 1999, Bialek et al. 2001), and the processes
of cooling and star formation (Muanwong et al. 2002, Kay et al. 2004,
Ettori et al. 2004, Kravtsov et al. 2005).

The paper is organized as follows: in Section~2, we describe our
dataset of simulated galaxy clusters; in Section~3, we present the
results obtained from this set of simulations on the gas and baryon
fraction, also comparing these results to the observational
constraints. In Section~4 we compare our results to previous analyses
based on different simulations. Finally, we summarize and discuss our
findings in Section~5.

\section{Properties of the simulated clusters}

We consider two sets of clusters, which have been selected from
different parent cosmological boxes. The first set is extracted from the
large--scale cosmological simulation presented in Borgani et
al. (2004).  The second one is a re-simulation of 9 galaxy clusters,
extracted from a pre-existing lower--resolution DM--only simulation.
Our simulations were carried out with {\tt GADGET-2} (Springel
2005), a new version of the parallel Tree+SPH simulation code {\tt
GADGET} (Springel et al. 2001). It includes an entropy-conserving
formulation of SPH (Springel \& Hernquist 2002), radiative cooling,
heating by a UV background, and a treatment of star formation and
feedback from galactic winds powered by supernova explosions
(Springel \& Hernquist 2003).

\subsection{Clusters extracted from a cosmological Box}

The first set of simulated clusters has been extracted from the
large-scale cosmological simulation of a ``concordance''
$\Lambda$CDM model ($\Omega_{0m}=0.3$, $\Omega_{0\Lambda}=0.7$,
$\Omega_{0\rm b}=0.019 h^{-2}$, $h=0.7$, $\sigma_8=0.8$; Borgani et
al. 2004).  Here we give only a short summary of its characteristics,
and refer to that paper for more details. The run follows the
evolution of $480^3$ dark matter particles and an equal number of gas
particles in a periodic cube of size $192 h^{-1}$ Mpc. The mass of the
gas particles is $m_{\rm gas}=6.89 \times 10^8 h^{-1} M_\odot$, while
the the Plummer-equivalent force softening is set to $7.5 h^{-1}$ kpc
from $z=0$ to $z=2$, while kept fixed in comoving units at higher
redshift.
At $z=0$ we extract a set of 439 mass-selected clusters with virial
masses $M_{\rm vir}> 5\times10^{13}h^{-1} M_{\odot}$.

The efficiency of conversion of the energy provided by SN explosions
into a kinetic feedback (i.e. winds) is set to 50 per cent, which gives a
wind speed of $\approx$340 km s$^{-1}$.

\subsection{Resimulated clusters}

This set includes simulations of
4 high mass systems with
$M_{200} = $(1.1--1.8)$\times 10^{15} h^{-1} M_{\odot}$. The
cluster regions were extracted from a dark-matter only simulation with
a box-size of $479\,h^{-1}\,{\rm Mpc}$ of the same cosmological model
as the first set, but with a higher normalization of the power
spectrum, $\sigma_8=0.9$ (see Yoshida, Sheth \& Diaferio 2001).  Using
the ``Zoomed Initial Conditions'' (ZIC) technique (Tormen 1997), they
were re-simulated with higher mass and force resolution by populating
their Lagrangian volumes in the initial domain with more particles,
while appropriately adding additional high--frequency modes. The
initial particle distributions (before displacement) are of glass type
(White 1996).
The mass resolution of the gas particles in these simulations $m_{\rm
gas}=1.7\times 10^8\,h^{-1}\,M_\odot$. Thus, the clusters were
resolved with between $2\times10^6$ and $4\times10^6$ particles,
depending on their final mass.  For all simulations, the gravitational
softening length was kept fixed at
$\epsilon=30.0\,h^{-1}\,\mathrm{kpc}$ comoving (Plummer-equivalent),
and was switched to a physical softening length of
$\epsilon=5.0\,h^{-1}\,\mathrm{kpc}$ at $z=5$.

For simulations including star formation and feedback the SN
efficiency in powering galactic winds is set to 50 per cent,
as in the cosmological box, which turns into a wind
speed of $\approx$340 km s$^{-1}$. For the sake of comparison, some
runs have also been performed also by switched off the winds
completely or increasing the SN efficiency to unity.

For some of the cluster simulations we also included the effect of
heat conduction. Its implementation in SPH, which is both stable and
manifestly conserves thermal energy even when individual and adaptive
time--steps, has been described by Jubelgas, Springel \& Dolag (2004).
This implementation assumes an isotropic effective conductivity
parameterized as a fixed fraction of the Spitzer rate, that we assume
to be 1/3. It also accounts for saturation, which can become relevant
in low-density gas. For more details on the properties of simulated
galaxy clusters including thermal conduction see Dolag et al. (2004).

Furthermore, some simulations were carried out using a modified
artificial viscosity scheme suggested by Morris \& Monaghan (1997),
where every particle evolves its own viscosity parameter. Whereas in
this scheme shocks are as well captured as in the standard one,
regions with no shocks do not suffer for a residual non--vanishing
artificial viscosity. Therefore turbulence driven by fluid
instabilities can be much better resolved and as a result of this,
galaxy clusters simulated with this new scheme can build up sufficient
level of turbulence--powered instabilities along the surfaces of the
large scale velocity structure present in cosmological structure
formation (Dolag et al. 2005).

\begin{figure}
  \epsfig{figure=ypar200_m.ps,width=0.5\textwidth}
\caption{The baryon and gas mass fractions at $R_{200}$ and $z=0$ as
functions of the virial mass. The solid dots with error-bars refer to
the mean and dispersion measured in the corresponding bins in virial
mass.  The number of objects in each bin is indicated.  The most
massive re-simulated systems are also shown.
The shaded regions indicate the $1 \sigma$ range of $Y_{\rm gas}$
and $Y_{\rm b}$ for the set of simulated clusters extracted
from the cosmological box.
}\label{fig:ybar_m}
\end{figure}

\begin{figure}
\vbox{
 \epsfig{figure=g51_fvir.ps,width=0.5\textwidth}
 \epsfig{figure=g51_fvir_z1.ps,width=0.5\textwidth}
}
\caption{The radial distribution of the gas and baryon mass fractions
(in unit of the cosmic baryonic value) at $z=0$ and $1$
for one of the four massive re--simulated systems.
The vertical dashed lines indicate the location of $R_{2500}$, $R_{500}$
and $R_{200}$ for the {\it Gravitational heating only} case.
}\label{fig:yb_r}
\end{figure}

In summary, this set of cluster was simulated 4 times, with different
kind of physics processes included:

\begin{itemize}
\item {\it Gravitational heating only (code=G)}.

\item {\it Gravitational heating only with low viscosity scheme (code=GV)}:
Like {\it G}, but using the alternative implementation of artificial
viscosity. In this simulation, galaxy clusters are found to have up to
30 per cent of their thermal energy in the turbulent motion of the ICM,
leading to a sizeable contribution of non--thermal pressure support in
the center of galaxy clusters;

\item {\it Cooling + Star Formation + Feedback with weak winds (code=FwW)}:
the wind speed is fixed at $\approx$340 km s$^{-1}$.

\item {\it Cooling + Star Formation + Feedback with weak winds and Conduction (code=FwWC)}:
Conduction efficiency set to be $1/3$ of the Spitzer rate.
\end{itemize}

In order to have under control the effect of changing the feedback
efficiency,
one high--mass cluster was
further simulated with the following setups:

\begin{itemize}

\item {\it Cooling + Star Formation + Feedback with no winds (code=F)}:
Like {\it FwW}, but with winds switched off.

\item {\it Cooling + Star Formation + Feedback with strong winds (code=FsW)}:
Like {\it FwW}, but with wind speed increased to
$\approx$480 km s$^{-1}$, corresponding to a SN efficiency of unity.

\end{itemize}

The center of each cluster is defined as the position of the
  particle having the minimum value of the gravitational
  potential. Starting from this position, we run a spherical
  overdensity algorithm to find the radius $R_{\Delta_c}$
  encompassing a given overdensity $\Delta_c$, with respect to the
  critical one at the redshift under exam,
and the mass $M_{\Delta_c}$ enclosed within this radius.
In the present work, we consider values of the overdensity
$\Delta_c$ equal to $2500$, $500$ and $200$.
The corresponding radii relate to the virial radius, which defines a
sphere with virial overdensity (of $\approx 101$ at $z=0$ and
$\approx 157$ at $z=1$ for our cosmological model and with
respect to the critical value), as
$(R_{2500}, R_{500}, R_{200}) \approx (0.2, 0.5, 0.7) \times R_{\rm vir}$.
For each cluster, the hot gas mass fraction and the stellar mass
fraction within a given radius $r$ are then calculated as $f_{\rm
gas}(<r) = M_{\rm gas}(<r) / M_{\rm tot}(<r)$ and $f_{\rm star}(<r) =
M_{\rm star}(<r) / M_{\rm tot}(<r)$, respectively.

\section{Results for the gas and stellar mass fractions}

For the sake of clarity, we define the quantities $Y_{\rm gas}$,
$Y_{\rm star}$ and $Y_{\rm b}$ as the ratios between
$f_{\rm gas}$, $f_{\rm star}$ and $f_{\rm b} = f_{\rm gas}+
f_{\rm star}$, and the cosmic value adopted in the present simulations,
$\Omega_{\rm b}/\Omega_{\rm m} = 0.13$.
Their mean values (and standard deviations of the observed
distributions, where available) at redshift
$z=0$, $0.3$, $0.7$ and $1$ are quoted in Table~\ref{tab:fgas}
for the different physical conditions considered.

We compare in Fig.~\ref{fig:ybar_m} the gas and baryon fraction as a
function of the virial mass, for both the simulated clusters extracted
from the cosmological box and for the subset of the re--simulated ones
with $M_{\rm 200} > 10^{15} h^{-1} M_{\odot}$. This plot demonstrates
that, when computed within the whole cluster virial region, there is
no relevant dependence upon mass of such fractions.  We remind the reader
that the two sets of clusters have been simulated for the same
cosmological model, the only difference being in the value of
$\sigma_8$, assumed to be 0.8 and 0.9 for the first and for the second
set, respectively.  In Fig.~\ref{fig:ybar_m}, the re-simulated
clusters indicated with a diamond correspond to the same simulation
physics as for the clusters extracted from the cosmological box. They
show a mean $Y_{\rm b}$ consistent with that measured for the
massive systems of the cosmological box, but with a slightly lower
value of $Y_{\rm gas}$. This is due to the increase in the cooling
efficiency with the amplitude of the power--spectrum, which produces
more evolved clusters (Borgani et al. 2005, in preparation).

\begin{figure*}
\hbox{
  \epsfig{figure=ypar2500.ps,width=0.33\textwidth}
  \epsfig{figure=ypar500.ps,width=0.33\textwidth}
  \epsfig{figure=ypar200.ps,width=0.33\textwidth}
}
\caption{The gas ({\it diamonds}) and total baryon ({\it dots})
mass fractions, in unit of the cosmic baryonic
value at $R_{2500}$ (left panel), $R_{500}$ (central panel) and
$R_{200}$ (right panel).
For each physical case considered, we plot the mean and standard
deviation values measured at $z=0$, $0.7$ and $1$.  The shaded region
show the error-weighted mean and standard deviation of (1) $f_{\rm
gas}(R_{2500})$ estimated from 26 X-ray luminous galaxy clusters in
Allen et al. (2004, quoted in Table~2 for a LCDM universe), (2)
$f_{\rm gas}(R_{500})$ from 35 highly luminous ($L_{\rm X} \ga
10^{45}$ erg s$^{-1}$) objects in Ettori \& Fabian (1999). The
observational data are normalized to $\Omega_{\rm b} h^2 = 0.0214 \pm
0.0020$ (Kirkman et al. 2003), $H_0 = 70$ km s$^{-1}$ Mpc$^{-1}$ and
$\Omega_{\rm m} = 0.3$.  }\label{fig:ybar}
\end{figure*}

The radial distribution of the gas and baryon mass fractions
in these massive systems present quite a similar
behavior. For one representative object, we plot in
Fig.~\ref{fig:yb_r} these ratios as a function of radius, out to
$3 \times R_{200}$,
at $z=0$ and $1$, for the six physical schemes
adopted in our analysis.
The total baryon fraction measured in the radiative models
is higher than the value obtained for the non--radiative runs
(code$=G, GV$) within the virial radius and
reaches the cosmic value at about $3 \times R_{200}$.
The gas fraction is larger when the winds are
stronger as a consequence of their effect in preventing gas removal
from the hot phase.
At $z=0$, it increases typically with radius reaching
50 and 80 per cent of the value measured at $R_{200}$
at $r \la 0.1 R_{200}$ and at $\sim 0.3 R_{200}$,
respectively.
At $z=1$, the gas fraction is less concentrated: the radii
at which the 50 and 80 per cent of $f_{\rm gas}(<R_{200})$
is reached are a factor 1.4 and 2 larger than at $z=0$.

The quantities $Y_{\rm gas}$ and $Y_{\rm b}$ at $R_{2500}$, $R_{500}$
and $R_{200}$, as a function of redshift and physics included in the
simulations, are plotted in Fig.~\ref{fig:ybar}.
In the inner cluster regions, the dissipative action of radiative
  cooling enhances the average $Y_{\rm b}$ to super-cosmic values at high
  redshift.  At late times cooling is less efficient, and $Y_{\rm b}$ declines,
  although to values ($\sim 0.9$ at $z=0$) that remain higher than those
  of the non-radiative runs.
A smaller scatter
and more widespread agreement among the different physical regimes are
instead found in the outskirts ($r \ga R_{500}$).  The gas fraction
within $R_{2500}$ is about $0.3$ times the cosmic value at $z=1$ and
$0.6$ at $z=0$, whereas is more tightly distributed around $0.6-0.7$
at larger radii, with evidence of larger values in the presence of
strong winds.  We also compare in Fig.~\ref{fig:ybar} our simulation
results with the observed $f_{\rm gas}$ distribution in highly X-ray
luminous clusters at $R_{2500}$ (from Allen et al. 2004) and at
$R_{500}$ (from Ettori \& Fabian 1999).
Simulations clearly indicate a sizeable underestimate of the hot
baryons budget, both at $R_{2500}$ and at $R_{500}$.
When extra physics is added to the action of
gravitational heating, lower hot gas fractions result.
The discrepancy with the inferred
observed fraction signals the existence of systematic errors,
either in our physical treatment, or in estimates of the observed
fraction, or possibly both.
It is worth noticing that total mass estimates, for instance, suffer
from systematic differences when measured from X-ray analysis and
from dark matter particles in simulations, mainly owing to
bias in the X-ray spectral temperature measurements
(see, e.g., Mazzotta et al. 2004, Vikhlinin 2005 and,
specifically related to the systematics in X-ray mass estimates,
Rasia et al. 2005).
The observed gas fraction measurements are well represented by
the values measured in the non--radiative simulations also in the inner
regions, where variations by $\la 15$ per cent due to the action
of non-thermal pressure support (induced by the reduced viscosity
scheme) encompass the observed variance.

The values of, and the relation between, $Y_{\rm gas}$ and $Y_{\rm
star}$ are shown in Fig.~\ref{fig:fgas} and
\ref{fig:fgas_r}.  At $R_{2500}$, the estimate of $Y_{\rm b}$ is
strongly affected by the physics involved in the accumulation of the
cluster baryons, with super-cosmic values mainly due to a very high
star-formation efficiency ($Y_{\rm star} > 0.5$), particularly at high
redshift (see Fig.~\ref{fig:fgas}). The effect of this cooling excess
is to sink more gas in the core to maintain the pressure support, thus
making the overall baryon fraction super-cosmic and the gas fraction
less concentrated at high redshift. At $R_{500}$ and $R_{200}$, the
dispersion in the estimate of $Y_{\rm b}$ is 2-3 per cent of the
measured mean (Fig.~\ref{fig:ybar}).  We explain the reduction in the
scatter at large radii by the common history that the baryons
experience in our simulations when the properties are averaged over a
volume large enough not to be dominated from the physics of the
core. With respect to the mean values measured at $R_{2500}$, $Y_{\rm
star}$ decreases by a factor $\ga 2$ and $Y_{\rm gas}$ increases by
more than 30 per cent, with peaks of 2-3 when no winds, or weak winds
combined with the effect of conduction, affect the ICM physics
(Fig.~\ref{fig:fgas_r}). The ratio $f_{\rm gas}/f_{\rm star}$, that
is $\la 1$ at $R_{2500}$ and $z\ga 0.3$, increases with both radius
and redshift and becomes $\simeq 3$ at $R_{200}$ and $z=0$ in the
presence of winds (see Fig.~\ref{fig:fgas_r}). Once again, the absence
of galactic winds increases the efficiency of star formation and
leaves the $f_{\rm gas}/f_{\rm star}$ ratio below $2$ within the
virial radius. These values are well above the observed constraints,
also plotted in Fig.~\ref{fig:fgas_r}.  Lin, Mohr \& Stanford (2003)
compare the gas mass measured in nearby X-ray bright galaxy clusters
with the stellar masses evaluated from K-band luminosities of the
member galaxies.  From their estimates, converted to the total mass
measurements in Arnaud et al.  (2005), we infer an average $M_{\rm
gas}/ M_{\rm star} \approx 8.7$ (r.m.s. $=2.7$) at $R_{500}$ in
systems with gas temperatures larger than 3 keV, that is still a
factor between 2.5 and 6 larger than what obtained in our simulated
objects (Fig.~\ref{fig:fgas_r}), thus witnessing the presence of
significant overcooling.

\begin{figure*}
\hbox{
  \epsfig{figure=gas.ps,width=0.43\textwidth}
  \epsfig{figure=gas_nv.ps,width=0.43\textwidth}
} \hbox{
  \epsfig{figure=csf.ps,width=0.43\textwidth}
  \epsfig{figure=csfc.ps,width=0.43\textwidth}
}  \hbox{
  \epsfig{figure=csfnw.ps,width=0.43\textwidth}
  \epsfig{figure=csfsw.ps,width=0.43\textwidth}
}
\caption{The comparison between the outputs of the 6 different
physical schemes investigated. The gas ({\it solid line}) and stellar
({\it dashed line}) mass fractions, normalized to the cosmic value,
are plotted at $R_{2500} (\approx 0.3 R_{200})$, $R_{500} (\approx 0.7
R_{200})$ and $R_{200}$.  Their evolution with redshift is indicated
by the thickness of the lines (from thickest line/larger symbols to
thinnest line/smaller symbols: $z=0$, $0.7$, $1$).  The shaded regions
indicate the $1 \sigma$ range of $Y_{\rm star}$, $Y_{\rm gas}$ and
$Y_{\rm b}$ measured at $R_{200}$ and $z=0$ for the cluster set
extracted from the cosmological box.  } \label{fig:fgas}
\end{figure*}

\begin{figure*}
\hbox{
  \epsfig{figure=csf_fs.ps,width=0.45\textwidth}
  \epsfig{figure=csfc_fs.ps,width=0.45\textwidth}
}  \hbox{
  \epsfig{figure=csfnw_fs.ps,width=0.45\textwidth}
  \epsfig{figure=csfsw_fs.ps,width=0.45\textwidth}
}
\caption{Ratios between
the cumulative gas and stellar mass
fractions within a given radius as a
function redshift
({\it solid line}: $z=0$; {\it dashed
line}: $z=0.7$; {\it dotted line}: $z=1$) for the different physics
included in the simulations.  The large dots show the mean value (and
relative standard deviation) obtained from the cosmological sample.
The diamonds indicate the ratios expected, for a given $M_{500}$, from
the equation~10 of Lin, Mohr \& Stanford (2003), based on
near--infrared observations of massive X-ray galaxy clusters.  }
\label{fig:fgas_r}
\end{figure*}

\section{Comparison to previous analyses}

While the comparison between results from different non--radiative
simulations is relatively straightforward, when extra-physics is
included, such as radiative cooling, star formation and stellar
feedback, the results on the hot and cool baryons distributions is
sensitive to the implemented scheme. Therefore, this difference has to
be taken into account in performing such a comparison.

In their non--radiative simulations, Eke, Navarro \& Frenk (1998)
found that the gas fraction within $R_{\rm vir}$ is, on average, 87
per cent of the cosmic value, that is reached at about $3 R_{\rm
vir}$.  For dynamically relaxed systems, they measure $Y_{\rm gas} =
0.824 \pm 0.033$ at $r = 0.25 R_{\rm vir} \approx R_{2500}$ (as quoted
in Allen et al. 2004).  No evident evolution is present between $z=1$
and $0$.  A comparable value was obtained as average of the baryon
fraction measured in a set of non--radiative simulations of one single
cluster presented in the Santa Barbara Comparison Project (Frenk et
al. 1999), with $f_{\rm b} / (\Omega_{\rm b}/\Omega_{\rm m})$ of
$0.92$ (rms: $0.07$) at the virial radius.  Similar results have been
obtained also in other SPH simulations (e.g. Bialek et al. 2001,
Muanwong et al. 2002).

These results agree with our estimates for
our simulations of massive galaxy clusters with gravitational heating
only: $Y_{\rm b}(<R_{200}) = 0.89 \pm 0.02$ ($0.90 \pm 0.03$ at
$R_{\rm vir}$).  A slight increase at high redshift is however measured
($Y_{\rm b} = 0.94 \pm 0.03$ at $z=1$).  On the contrary, the baryon
fraction decreases moving inwards, with $Y_{\rm b}(<R_{500}) = 0.87$
and $Y_{\rm b}(<R_{2500}) = 0.82$

Kravtsov, Nagai \& Vikhlinin (2005) studied the baryon fraction in nine
galaxy clusters spanning a decade in mass and simulated with the
Eulerian adaptive mesh refinement N-body+gasdynamics {\small ART} code,
for both non--radiative and radiative cases.
For non--radiative simulations, they measure $Y_{\rm b} \approx
1$ (at $r \ga 3 R_{\rm vir}$), $0.97 \pm 0.03$ (at $R_{\rm vir}$),
$0.94 \pm 0.03$ (at $R_{500}$) and $0.85 \pm 0.08$ (at $R_{2500}$),
that are consistently higher than our values by few per cent.
This systematic difference by $\approx 5$\% at $r \ga R_{2500}$
has been already shown by the comparison between the {\small ART}
and {\tt GADGET} codes discussed in Kravtsov et al. (2005)
and, even though smaller than the $10$\% differences measured
in the Santa Barbara cluster comparison project (Frenk et al. 1999)
between the gas fraction obtained from Eulerian and SPH codes,
is still relevant when using simulations to
calibrate systematics in the estimate of the baryon fraction
in clusters.

When the radiative cooling and other physical processes are turned on,
the number of reliable comparisons that can be done is reduced.  In
the radiative simulations of Muanwong et al. (2002), $Y_{\rm gas}$ is
between $0.6-0.7$ in high$-M$ systems and $Y_{\rm b} \approx 0.9$ at
the virial radius.  When pre--heating with an extra energy of 1.5 keV
per particle at $z=4$, these authors find $Y_{\rm gas} \sim Y_{\rm b}
\approx 0.8-0.9$.  Kravtsov et al. (2005) measure the gas fraction to
rise from $0.46 \pm 0.06$ (at $R_{2500}$) to $0.65 \pm 0.06$ (at
$R_{\rm vir}$), whereas $Y_{\rm b}$ remains always around $1$ (from
$1.22 \pm 0.11$ at $R_{2500}$ to $1.02 \pm 0.02$ at $R_{\rm
vir}$). These values are roughly in agreement with our results, in
particular for the set of simulated objects with weak winds: at $z=0$,
$Y_{\rm gas}=0.51 \pm 0.02$ at $R_{2500}$ and $0.70 \pm 0.03$ at
$R_{200}$, while $Y_{\rm b}$ is flat around $0.93 \pm 0.02$ and never
super-cosmic, i.e.  $Y_{\rm b} < 1$.  Different numerical
implementations of the cooling, star--formation and feedback processes
are expected to contribute to this systematic difference between the
predictions of {\small ART} and {\tt GADGET} simulations.  These
differences are, in fact, more significant in the radiative runs and
depend on the amount of baryons cooled in stars (see also Kravtsov et
al. 2005). Such differences, which are numerical in origin, should
definitely be considered as theoretical uncertainties, when using
simulations to calibrate systematic biases in the observational
estimate of the baryon fraction within clusters. The action of
stronger winds is to increase the gas fraction, whereas the absence of
winds reduces $Y_{\rm gas}$ to $0.29$ and $0.59$ at $R_{2500}$ and
$R_{200}$, respectively.

\section{Implications for the constraints on cosmological parameters}

Our results have a direct implication on the systematics that affect
the constraints on the cosmological parameters obtained through the
cluster baryon mass fraction (e.g. White et al. 1993, Evrard 1997,
Allen et al. 2002, Ettori et al. 2003, Ettori 2003, Allen et
al. 2004).  We remind that, once a representative gas fraction,
denoted here $\hat{f}_{\rm gas}$, is directly measured
from X-ray observations and a statistical relation between the average
$\hat{f}_{\rm star}$ and $\hat{f}_{\rm gas}$ is adopted,
the cosmic mass density parameter can be then evaluated as
\begin{equation}
\Omega_{\rm m} = \frac{Y_{\rm b} \ \Omega_{\rm b}}{\hat{f}_{\rm gas}
\left( 1 + \hat{f}_{\rm star}/\hat{f}_{\rm gas} \right)},
\label{eq:cosmo}
\end{equation}
where the ``hat" indicates the observed quantities and
the cosmic baryon density $\Omega_{\rm b}$ is assumed from
primordial nucleosynthesis calculations or the measured anisotropies
in the cosmic microwave background.  In recent years this method has
been also extended to the measure of the dark energy density parameter,
($\Omega_{\Lambda}$, $w$; see, e.g., Allen et al. 2002, Ettori et
al. 2003, Allen et al. 2004) under the assumption that the gas
fraction remains constant in redshift
(Sasaki 1996, Pen 1997). Since the gas fraction
scales with the angular diameter distance as $f_{\rm gas} \propto d_{\rm
A}^{1.5}$, the best choice of cosmological parameters is defined as
the set of values that minimizes the $\chi^2$ distribution of the
measured gas fraction at different redshifts
with respect to the reference value:
\begin{equation}
f^{\Lambda CDM}_{\rm gas} = \frac{Y_{\rm b} \ \Omega_{\rm b}
\Omega_{\rm m}^{-1}} {\left( 1 + \hat{f}_{\rm star}/\hat{f}_{\rm gas}
\right)} \left[ \frac{d_{\rm A}(z; \Omega_{\rm m}=0.3;
\Omega_{\Lambda}=0.7)}{d_{\rm A}(z; \Omega_{\rm m}; \Omega_{\Lambda})}
\right]^{1.5}.
\label{eq:fgas}
\end{equation}

Despite its conceptual simplicity and straightforward application,
this method makes some assumptions that have to be tested before
the error bars estimated for the matter and dark--energy density parameters
can be accepted as robust and reliable determination of both
statistical and systematic uncertainties.  In the present discussion,
we highlight two of the assumptions generally adopted, but never
verified: (1) the mean value of $Y_{\rm b}$ does not evolve with
redshift, (2) a fixed ratio between $f_{\rm star}$ and $f_{\rm gas}$
holds in a cluster at any radius and redshift.  As we have shown here,
both these assumptions are not valid in our simulated dataset whatever
is the physics included in the simulations, in particular when
considering the inner part of the clusters.  Allen et al. (2004) use
the simulation results by Eke et al. (1998) to fix $Y_{\rm b}=0.824
\pm 0.033$ at $r \approx R_{2500}$ for their sample of {\it Chandra}
exposures of the largest relaxed clusters with redshift between $0.07$
and $0.9$. We notice, for instance, that, while this value is in
agreement with our simulation results at $z=0$ in the runs with
{\it Gravitational heating only} ($Y_{\rm b}=0.82 \pm 0.06$), it is
definitely lower than what we estimate at higher redshift (e.g. $Y_{\rm
b}=0.86, 0.89, 0.91$ at $z=0.3, 0.7, 1$, respectively).
This increase of $Y_{\rm b}$ with redshift is the consequence of the
different accretion pattern of shock-heated baryons at different epochs.
At later times, accreting gas had more time to be pre-shocked into filaments.
As a consequence, they have a relatively higher entropy, thus relatively
increasing the radius (in unit of the virial radius) where
accretion shocks take place.
This is the reason why, as shown in Fig.~\ref{fig:yb_r}, at $z=1$
$f_{\rm b}$ reaches the cosmic value at relatevely smaller radii than at $z=0$.

Since the tighter cosmological constraints provided by the cluster gas
fraction alone are on $\Omega_{\rm m}$ (of the order of 16 per cent at
$1 \sigma$ level; e.g. Allen et al. 2004), we try to quantify the
effect of the variation of the baryonic components with the radius
and the redshift on this estimate.
To this purpose, we use equation~\ref{eq:cosmo}
and evaluate first how $\Omega_{\rm m}$ changes by varying $Y_{\rm b}$.
In runs with gravitational heating only, the increasing baryon fraction with
redshift induces larger estimate of $\Omega_{\rm m}$ with respect to what
obtained from local measurements of $Y_{\rm b}$:
\begin{equation}
\frac{ \Omega_{\rm m}^{\prime} - \Omega_{\rm m} }{\Omega_{\rm m}} =
 \frac{\Delta \Omega_{\rm m}}{\Omega_{\rm m}} =
 \frac{Y_{\rm b}(<R_{\Delta}, z=z_o)}{Y_{\rm b}(<R_{\Delta}, z=0)} -1
\end{equation}
is $+0.09$ at $R_{\Delta}=R_{2500}$ and $z_o=0.7$ for the case with
gravitational heating only and $+0.11$ at $z_o=1$.
(Here the prime symbol $^{\prime}$ indicates the corrected value with
respect to the reference one).
Using instead the runs with reduced viscosity, the deviation decreases
to about $+0.05$. As for the radiative runs, the bias is of the order
of 20 per cent, that reduces to 2 per cent in presence of strong winds
at $z=1$.  When outer cluster regions are mapped (i.e. $r \sim R_{500}$),
the deviation converges to similar amounts due to the limited impact of
cooling and feedback over large volumes: variations between $+0.03$
(weak winds) and $+0.10$ (strong winds) become comparable to $\Delta
\Omega_{\rm m}/\Omega_{\rm m} \approx +0.08$ as measured in
non--radiative runs.

A further contribution to the uncertainties comes from the dependence
upon the radius and redshift of the ratio $f_{\rm star}/f_{\rm gas}$.
In the observational determination of the baryon fraction from
eqn.~\ref{eq:cosmo}, this quantity is generally assumed to be $0.16$,
as measured in the Coma cluster within the virial radius [e.g. White
et al. 1993; note that our estimate from Lin et al. (2003) and
adopting the total mass measurements in Arnaud et al. (2005) is $0.11
\pm 0.04$].  If we compare the ratio $\phi = f_{\rm star}/f_{\rm gas}$
measured for a Coma--like simulated cluster at $R_{200}$ and $z=0$
with the estimates at other redshifts ($z_o =0.7$ and $1$;
see, e.g., Fig.~\ref{fig:fgas_r}), we evaluate from
equation~\ref{eq:cosmo}
\begin{equation}
\frac{\Omega_{\rm m}^{\prime} - \Omega_{\rm m}}{\Omega_{\rm m}} =
\frac{\Delta \Omega_{\rm m}}{\Omega_{\rm m}} =
\frac{ 1 + \phi(<R_{\Delta}, z=0) }{1 + \phi(<R_{\Delta}, z=z_o)}
\; -1 \approx -0.05\,.
\end{equation}
When $\phi = f_{\rm star}/f_{\rm gas}$ measured locally at $R_{2500}$ is
compared with the corresponding value at different redshifts, the
deviation ranges between $-0.74$ (when winds are excluded) and $-0.38$
(when strong winds are present), whereas it is about $-0.10$ at
$R_{500}$.

As for the runs with gravitational heating only the effect of the
variation of $Y_{\rm b}$ with redshift and overdensity implies $\Delta
\Omega_{\rm m}/\Omega_{\rm m} \la +0.11$, thus comparable to the
current statistical uncertainties from {\it Chandra} observations of
the massive clusters out to $z=1.3$ (Ettori et al. 2003, Allen et
al. 2004). However, when the extra-physics of the radiative runs is
included, $\Delta \Omega_{\rm m}/\Omega_{\rm m}$ has two contributions
of $\approx +0.10$ and $\la -0.05$, due to an increase with redshift
of (1) $Y_{\rm b}$ (see Fig.~\ref{fig:ybar}) and (2) the stellar to
gas mass fraction ratio (see Fig.~\ref{fig:fgas_r}).  Both these
effects are caused by a more efficient star formation in high redshift
clusters.

In general, our results indicate that it may be dangerous to use
simulations to calibrate observational biases for precision
determination of cosmological parameters from the gas fraction in
clusters. Although none of our simulation models includes a fair
description of the actual ICM physics, it is interesting that
different models provide different redshift--dependent corrections for
the estimate of the cosmic baryon fraction from observations of the
gas and star density distribution within clusters. If applied to
observational data, such corrections would induce sizeable differences
in the determination of the matter and dark energy density parameters.

\section{Summary and discussion}

We have analyzed the distribution of gas and stellar mass fraction in
simulated massive X-ray galaxy clusters as function of (i) the radius
expressed in the form of $R_{2500}$, $R_{500}$ and $R_{200}$, (ii) the
redshift at which the structure is identified, (iii) the physical
processes determining the evolution of the baryons in the cluster
potential wells (i.e. gravitational heating, radiative cooling, star
formation, conduction and galactic winds powered by supernova
explosions).

Our main results can be summarized as follows.
\begin{enumerate}

\item As for the cluster set extracted from a cosmological box, which
are simulated by including cooling, star formation and feedback with
weak (340 km s$^{-1}$) winds, we find at $R_{200}$ $Y_{\rm b}=0.93$,
$Y_{\rm gas}=0.74$ and $Y_{\rm star}=0.20$, with scatter around these
values of 2, 4 and 8 per cent, respectively.  These results are
virtually independent of the cluster mass over the range $M_{\rm vir}
\approx (0.5 - 13) \times 10^{14} h^{-1}M_{\odot}$.  The dispersion relative
to the mean value measured at $R_{2500}$ is a factor of about $3$
larger than $R_{200}$.

\item In the four massive ($M_{200} > 10^{15} h^{-1}M_{\odot}$)
galaxy clusters simulated with 6 different physical schemes, we find
that the cosmic value of the baryon fraction $\Omega_{\rm
b}/\Omega_{\rm m}$ is reached at about $3 \times R_{200}$.  The
gas fraction increases radially, reaching 50 (80) per cent of the
value measured at $R_{200}$ at $r \approx 0.1 (0.3) R_{200}$
at $z=0$. At $z=1$ the same values are reached at radii which
are about 40 per cent larger. This indicates that $f_{\rm gas}$ tends
to be less concentrated at higher redshift, where the more efficient
star formation causes a more efficient removal of gas from the hot
phase in the central cluster regions.
We also find that in these clusters the amount of
hot baryons, in unit of the cosmic value, is less scattered and
less dependent on the particular physics adopted when it is measured
over larger cluster regions.
In the runs with {\it Gravitational heating only}, $Y_{\rm b} = f_{\rm bar} /
(\Omega_{\rm b}/\Omega_{\rm m})$ ranges between $0.82 \pm 0.06$ (at
$R_{2500}$) and $0.89 \pm 0.02$ (at $R_{200}$) at $z=0$. It increases
at $z=1$ to $0.91 \pm 0.10$, $0.95 \pm 0.04$ and
$0.94 \pm 0.03$ at $R_{2500}$, $R_{500}$ and $R_{200}$, respectively.
This increase of $Y_{\rm b}$ with $z$ owes to the smaller radii
(in units of the virial radius)
at higher redshift where shock-heated baryons accrete, permitting
the $f_{\rm b}$ values to reach the cosmic value at higher overdensities,
for example, at $z=1$ than at $z=0$ (see, e.g., Fig.~\ref{fig:yb_r}).
These values are roughly in agreement with observational
constraints obtained from highly X-ray luminous clusters (e.g. Ettori
\& Fabian 1999, Allen et al. 2004) at $R_{2500}$ and $R_{500}$.
Using an SPH scheme with reduced viscosity, the non--thermal pressure
support contributed by turbulent gas motions, reduces the gas fraction
by 15 per cent at $R_{2500}$ and by $\sim$5 per cent at $r>R_{500}$.

Adding extra-physics to the action of gravity reduces the amount of
diffuse baryons by 20--40 (20--65) per cent at $R_{500}$ ($R_{2500}$).
This is due to the high star formation efficiency that is not
sufficiently mitigated by our assumed supernova feedback. The presence
of strong winds (assumed here $v \la 480$ km s$^{-1}$) induces the
following effects: (1) a reduction of $Y_{\rm star}$ by about a factor
of $2$ with respect to the case with no winds; (2) a milder radial
dependence of $Y_{\rm star}$ and $Y_{\rm gas}$; (3) larger values for
the ratio between $f_{\rm gas}$ and $f_{\rm star}$, that is however
still smaller, by about a factor $2.5$, than the observed values (Lin
et al. 2003) .

\item At $R_{2500}$, the estimate of $Y_{\rm b}$ is strongly affected
by the physics included in the simulations.  Super-cosmic values are
found for the radiative runs, as a consequence of the exceedingly
efficient cooling process, which causes a rapid sinking of baryons in
the cluster cores.  Moreover, differences in the formation history of
individual clusters contribute to a wider spread in the $Y_{\rm b}$
values, as shown in the runs including only gravitational heating. In
these cases, the standard deviation is of about 10 per cent.

\item At $R_{500}$ and $R_{200}$, the dispersion in the estimate of
$Y_{\rm b}$ is 2-3\% of the measured mean.  With respect to the mean
values measured at $R_{2500}$, $Y_{\rm star}$ decreases by a factor
$\ga 2$ and $Y_{\rm gas}$ increases by more than $1.3$, with peaks of
2-3 in the simulations without winds, or with weak winds combined with
conduction at $1/3$ the Spitzer value.

We explain the reduction in the scatter at $r>R_{500}$ by the common
history that the baryons experience when their properties are averaged
over a large enough volume. In the outer regions, the gas evolution is
mainly driven by the action of gravity. The
ratio $f_{\rm gas}/f_{\rm star}$, that is $\la 1$ at $R_{2500}$ and $z
\ga 0.3$, increases with radius and redshift and becomes $\simeq 3$
at $R_{200}$ and $z=0$ in the presence of winds.

\item Our results have direct implications on the calibration of the
systematic effects that limit the use of the X-ray gas mass fraction
as a cosmological tool (e.g. Evrard 1997, Ettori et al. 2003, Allen et
al. 2004). Owing to the uncertainties in the modelization of the ICM,
we emphasize that our simulations cannot be used to calibrate the
observed $f_{\rm gas}$. However, our results emphasize the potential
problems related to the estimate of the cosmic baryon fraction from
the gas mass fraction as measured in central cluster regions; i.e. the
variation of $Y_{\rm b}$ with redshift and a proper estimate
of the contribution of stars in galaxies to the total cluster baryon
budget as a function of radius and redshift.

For the non--radiative runs the effect of the variation of $Y_{\rm b}$
with redshift and overdensity implies a $\Delta \Omega_{\rm
m}/\Omega_{\rm m} \la +0.11$ that is comparable to the typical
statistical uncertainties from {\it Chandra} observations of the
massive clusters out to redshift $z=1.3$ (Ettori et al. 2003, Allen et
al. 2004). However, when star formation and feedback are also
included, $\Delta \Omega_{\rm m}/\Omega_{\rm m}$ has two contributions
of $\approx +0.10$ and $\la -0.05$, due to an increase with redshift
of (1) $Y_{\rm b}$ (see Fig.~\ref{fig:ybar}) and (2) ration between
stellar and gas mass (see Fig.~\ref{fig:fgas_r}).
\end{enumerate}

Our results show that star formation in our radiative runs is still
too efficient, especially in the cluster central regions, even in the
presence of rather strong galactic winds.  As a result, the impact of
cooling and star formation in the simulated clusters is still much
larger than in realistic cases.  On the one hand, this calls for the
need to introduce more effective feedback mechanisms, e.g. related to
Active Galactic Nuclei, which are able to prevent overcooling in the
central cluster regions (see, e.g., the effect of the injection
of supersonic AGN jets in the ICM of simulated clusters in Zanni et al. 2005).
On the other hand, our analysis demonstrates
that using simulations to calibrate the systematic uncertainties in
the estimate of cosmological parameters from the cluster gas mass
fraction may be quite problematic, especially if it has to be used as
a high--precision tool to measure the cosmic density parameters
associated to matter and dark energy.

\section*{ACKNOWLEDGEMENTS}
The simulations have been performed using the IBM-SP4 machine at the
``Consorzio Interuniversitario del Nord-Est per il Calcolo
Elettronico'' (CINECA, Bologna), with CPU time assigned thanks to the
INAF--CINECA grant, the IBM-SP3 machine at the Italian Centre of
Excellence ``Science and Applications of Advanced Computational
Paradigms'', Padova and the IBM-SP4 machine at the ``Rechenzentrum der
Max-Planck-Gesellschaft'' at the ``Max-Planck-Institut f\"ur
Plasmaphysik'' with CPU time assigned to the ``Max-Planck-Institut
f\"ur Astrophysik''.  This work has been partially supported by the
INFN--PD51 grant and by MIUR. The anonymous referee is thanked
for insightful comments.


\section{Introduction}
Presence of  cosmic infrared background radiation (CIB) in
extragalactic space has now been confirmed by experiments, and its
intensity is measured (see, e.g., reviews \cite{franceschini,
hauser}), though the precision of these measurements is still not
so high, especially if to compare with those for relic radiation.
Nevertheless, we know enough to estimate some effects caused by
the presence of the extragalactic infrared background. One of such
effects is neutrino production due to high energy cosmic ray
proton interactions with CIB photons, considered in
\cite{stanev,b1,b2}. Here we will focus on the other point: high
energy cosmic ray spectrum modification due to interactions with
CIB photons.

\section{Extragalactic cosmic ray proton spectrum}
For the calculation of cosmic ray (CR) energy spectrum at high
energies, we assume it to be extragalactic and proton dominated
from the energy $E_0=3\times 10^{17} eV$. The sources of these CRs
are assumed to be distributed isotropically and uniformly
throughout the Universe. In this case it is very convenient to use
cosmological transport equation written as
\begin{equation}
\label{eq1} \frac{\partial n (E,z)}{\partial
z}+\frac{\partial}{\partial E} \left[\beta(E,z)n(E,z)\right] -
\frac{3n(E,z)}{1+z}=g(E,z).
\end{equation}
We work in in the continuous energy loss approximation introduced
in \cite{berezinsky} and neglect possible proton absorbtion. In
(\ref{eq1}), $n(E,z)$ is the number density of CR protons with a
given redshift $z$, the function $\beta(E,z)$ is the change of
proton energy in unit interval of $z$,
$$
\beta(E,z)=\frac{dE}{dz} = \frac{E}{1+z} - b(E,z)
\frac{dt}{dz},
$$
where the first term in r.h.s. is due to adiabatic energy losses
(caused by cosmological expansion), $b(E,z)=-dE/dt$, and is simply
connected with the proton cooling rate $t_p^{-1}(E,z)$. For the
case of proton interactions with photon gas it is given by the
formula
$$
t_{p}^{-1}(E,z)=\frac{1}{E}b(E,z)=\frac{c}{2\gamma_p^{2}} \int
\limits_{\epsilon_{th}}^{\infty} d \epsilon_{r}
\sigma(\epsilon_{r}) f(\epsilon_{r}) \epsilon_{r}\int \limits_{
\epsilon_{th}/{2\gamma_p} }^{\infty} d\epsilon
\frac{n^{photon}(\epsilon,z)}{\epsilon^2},
$$
where $\gamma_p=E/m_p$ is proton Lorenz factor, $\epsilon_{r}$ is
the photon energy in the CR proton rest system,
$\sigma(\epsilon_{r})$ is the photoabsorbtion cross section,
$f(\epsilon_{r})$ is the average relative proton energy loss in
$p\gamma$-collision (in the observer system),  $\epsilon_{th}$ is
the threshold of the photoabsorbtion reaction.

Protons lose their energy interacting with photons via $p\gamma\to
\pi X$ and $p\gamma\to pe^{+}e^{-}$ reactions. Here, we suppose
that $\gamma$ can be relic photon (they have black body spectral
distribution with $T\approx 2.7K$) or background infrared photon.

Thus, in our approximation the total cooling rate should be
written as a sum of two components: cooling due to interactions
with relic and infrared components of the extragalactic radiation
background,
$$
t_p^{-1}(E,z) = t_{p,relic}^{-1}(E,z) + t_{p,infr}^{-1}(E,z).
$$

The function $g(E,z)$ in r.h.s. of the kinetic equation
(\ref{eq1}) describes the combined source of extragalactic cosmic
rays. This source function can be written in the form
\begin{equation}
\label{eq5} g(E,z)=\rho(z)\eta(z)f(E)\frac{dt}{dz}.
\end{equation}
Here, $\rho(z)$ is the number density of local CR sources (e.g.,
AGNs) in the proper (physical) volume, $\rho(z)=\rho_0 (1+z)^3$,
$\eta(z)$ is the activity of each local source (the integrated
number of produced particles per second), $\eta(z)=(1+z)^{m}
\eta_0\theta(z_{max}-z)$. Writing this, we assume that the
cosmological evolution of cosmic ray sources can be parametrized
by power law with the sharp cut-off at some epoch with redshift
$z_{max}$ ($m$ and $z_{max}$ are considered as parameters of a
model of the combined source). At last, the function $f(E)$ in
eq.(\ref{eq5}) describes a form of the differential energy
spectrum of the local source. For a simple power law injection
spectrum we can write
$$
f(E)=\frac{\gamma - 1}{E_0} \Big(\frac{E}{E_0}\Big)^{-\gamma}.
$$

Now supposing some values for the presented parameters we can
solve (\ref{eq1}). One more thing needed is infrared photon number
density for different redshifts, $n^{IR}(E_{\gamma},z)$, to
calculate energy losses in infrared background. As for the case of
relic photons, the dependence of $n^{relic}(E_{\gamma},z)$ on $z$
is trivial: they always have black body spectrum, with temperature
$T(z)=T(0)(1+z)$.

\section{Cosmic infrared radiation background}
Extragalactic infrared background had been formed by
infrared-luminous galaxies in the late Universe. For the
calculation of CIB it is again convenient to use the cosmological
transport equation which is analogous to that used in the previous
section. The function which must be found is the number density of
infrared photons at different cosmological epochs,
$n^{IR}(E_{\gamma},z)$.

The resulting expression for the number density of infrared
photons in extragalactic space is \cite{b1}
\begin{equation}
\label{eq6} n^{IR}(E_{\gamma},z)=\int \limits_{z}^{z_{max}} dx
\left(\frac{1+z}{1+x}\right)^3 \int \frac{dL}{L} \rho(x,L)
S^{IR}\left(E_{\gamma} \frac{1+x}{1+z},L\right) \cdot
\frac{1}{E_{\gamma}} \Big| \frac{dt}{dx} \Big|,
\end{equation}
where $L$ is the luminosity of infrared-bright galaxy emitting
photons, $S^{IR}(E_{\gamma},L)$ describes the spectrum of this
radiation (it is called the spectral energy distribution),
$\rho(z,L)$ is the number density of infrared-bright galaxies with
a given luminosity.

From direct measurements we can learn  $\rho(0,L)$ and
$S^{IR}(E_{\gamma},L)$. Then we can assume some kind of the
cosmological evolution to obtain $\rho(z,L)$. Next step is to
calculate $n^{IR}(E_{\gamma},0)$ making use of formula
(\ref{eq6}), and compare it with the measured CIB intensity. One
of the results of such estimations is the well-known fact
\cite{franceschini,hauser} that we need to assume strong evolution
of background sources in the far infrared region to explain
observed CIB intensity (say, $\nu I(\nu)\sim 30nW m^{-2}sr^{-1}$
at $\lambda \sim 100\mu m$).

In fact, we include in our calculations only far and partially
middle infrared background regions, not considering near infrared
and optic regions. For the present calculations, we used the same
parametrization of the function $\rho(z,L)$ and same input data as
described in \cite{b2}. But we should mention that the effect
under discussion (CR spectrum modification) does not depend
greatly on the type of infrared sources evolution, but much more
on the CIB intensity at $z=0$ (that is, at our time).

\section{Results and conclusions}
On Fig. \ref{fig1}a we show the proton cooling rate in infrared
photon gas (together with corresponding function for the relic
photon case), both curves shown for $z=0$. The asymptotic value of
$t_p^{-1}$ at highest energies is proportional to the total number
density of photons, so for $E>10^{20} eV $ cooling on infrared
photons gives a small contribution, $\sim 0.5\%$. But one can see
from the figure that at proton energy $\sim (3\div 4)\times
10^{19} eV$, the contribution of infrared photons in total cooling
rate is noticeable.

For calculation of the CR spectrum we used the following set of
parameters determining the spectrum slope and cosmological
evolution of CR sources: $\gamma=2.5, m=3.5, z_{max}=5$. We
assumed here that extragalactic spectrum of CRs dominates
beginning from $E_0=3\times 10^{17}eV$. The theoretical CR
spectrum at $z=0$ was normalized on experimental data; from such a
normalization we obtained the value of the product $\rho_0 \eta_0$
entering eq.(\ref{eq5}) for the source function of the CR proton
kinetic equation, $\rho_0 \eta_0 \approx 1.4\times 10^{-42}
cm^{-3} s^{-1} $.

The results of two calculations of extragalactic CR proton
spectrum (with and without taking into account energy losses on
infrared photons) are shown on Fig. \ref{fig1}b. Both curves have
characteristic dip and cut-off features; one can see that
extragalactic CR spectrum near GZK cut-off gets modified when
taking into account interactions with infrared background.

In this work we used concrete model parameters for CR source
properties and the certain model for CIB, for the estimation of CR
extragalactic spectrum modification at $10^{19}-10^{20} eV$.
Certainly, new experimental data for CIB intensity as long as
improvement of our knowledge of CR sources will help to determine
more precisely the magnitude of this effect.


\section{Introduction}
\label{section:Introduction}

The extensive use of digital images and videos in today's digital
world makes the security and privacy issues more and more important.
To fulfill such an increasing demand, various encryption algorithms
have been proposed in recent years as possible solutions to content
protection of digital images and videos
\cite{Cheng:PartialImageEncryption:IEEETSP2000,
Qiao:ComparisonMPEGEncryption:CG98, Shi:MPEGEncryption:MMTA2004,
Furht:MultimediaSecurity:Handbook2004,
Furht:MultimediaSecurity:Book2005,
Ahl:ImageVideoEncryption:Book2005, Zeng:MultimediaSecurity:Book2006,
Wu&Kuo:MHTEncryption:IEEETMM2004,
Zeng:VideoScrambling:IEEETCASVT2002,
Zeng:VideoScrambling:IEEETMM2003, Wu:JointMMEncryption:IEEETIP2006},
among which MPEG videos attract special attention due to its
prominent prevalence in consumer electronic markets
\cite{MPEG1-ISOStandard, MPEG2-ISOStandard, MPEG4-ISOStandard}. As
an important way of designing MPEG-video encryption schemes, secret
Huffman tables have been suggested in some designs
\cite{Shi:SecretHuffmanCoding:MM98, Shi:MPEGEncryption:MMTA2004,
Kankanhalli:VideoScrambler:IEEETCE2002,
Wu&Kuo:AudiovisualEncryption:SPIE2001,
Wu&Kuo:EntropyCodecEncryption:SPIE2001,
Xie&Kuo:MHTEncryption:SPIE2003, Wu&Kuo:MHTEncryption:IEEETMM2004}.

The MPEG-video encryption scheme proposed in
\cite{Shi:SecretHuffmanCoding:MM98} (i.e., Algorithm 1 in
\cite{Shi:MPEGEncryption:MMTA2004}) is a light-weight scheme, which
encrypts the plain-video by shuffling VLC (variable-length coding)
entries of same size in each Huffman table. However, because the bit
length of each VLC codeword does not change, the position of each
VLC codeword in the video stream does not change either. Thus, an
attacker can uniquely locate (and thus determine) all VLC codewords
contained in the cipher-video stream, if the plain-video stream or
an independent part (such as a picture or a slice) is known. Once
all distinct VLC codewords are obtained, the whole secret Huffman
table is uniquely reconstructed and the encryption scheme is broken.
That is, this light-weight scheme is not secure against
known/chosen-plaintext attacks. In addition, as pointed out in
\cite{Shi:MPEGEncryption:MMTA2004}, the key space of this encryption
scheme is very limited (especially for Huffman tables with a small
number of VLC entries), so even a brute-force attack may become
feasible.

The MPEG-video encryption scheme proposed in
\cite{Kankanhalli:VideoScrambler:IEEETCE2002} can be considered as
an enhanced version of that in \cite{Shi:SecretHuffmanCoding:MM98}.
In this scheme, five different Huffman tables are shuffled
separately and the shuffling operations are generalized to work on
VLC entries with different sizes, in the hope that the key space can
be enlarged and the security against plaintext attacks can be
improved. Furthermore, as a second guard on the security, random bit
flipping operations are also introduced to further encrypt each
secret Huffman table.

In \cite{Wu&Kuo:AudiovisualEncryption:SPIE2001,
Wu&Kuo:EntropyCodecEncryption:SPIE2001,
Xie&Kuo:MHTEncryption:SPIE2003, Wu&Kuo:MHTEncryption:IEEETMM2004},
multiple Huffman tables (MHT) are introduced, from which one table
is secretly chosen for the encryption of each VLC codeword. A
so-called ``Huffman tree mutation process" is also proposed in
\cite{Wu&Kuo:AudiovisualEncryption:SPIE2001,
Wu&Kuo:EntropyCodecEncryption:SPIE2001,
Wu&Kuo:MHTEncryption:IEEETMM2004} to derive more candidate Huffman
tables from several original tables. \iffalse But this process does
not change the size of each VLC entry, so it contributes nothing to
the security against plaintext attacks. It is just an easy way to
get a large number of candidate Huffman tables for encryption
purpose.\fi

This paper mainly focuses on security problems with the MPEG-video
encryption scheme proposed in
\cite{Kankanhalli:VideoScrambler:IEEETCE2002}. Our cryptanalysis
shows that this scheme is not sufficiently secure against DAC
(divide-and-conquer) ciphertext-only attack, partial-key attack and
known-plaintext attack, and very weak against chosen-plaintext
attack.

The rest of this paper is organized as follows. In the next section,
a brief introduction to the MPEG-video encryption scheme under study
is given. Then, the main cryptanalysis results are presented in
detail in Sect.~\ref{section:Cryptanalysis}, with some experimental
results. Finally Section~\ref{section:Improving} gives a discussion
on how to improve the security of the MPEG-video encryption scheme,
and the last section concludes this paper.

\section{MPEG-Video Encryption Scheme Under Study}

Given an uncompressed video as the input, an MPEG\footnote{To keep
the description simpler, here we mainly considers MEPG-1/2 encoder.
For special features of MPEG-4 encoder with respect to MPEG-1/2, see
\cite{MPEG4-ISOStandard} for more details.} encoder compresses the
video stream frame by frame in the following steps
\cite{MPEG1-ISOStandard, MPEG2-ISOStandard}:
\begin{enumerate}
\item (optional, for interlaced MPEG-2 videos only) separate a
frame into two field-pictures: a top field and a bottom field;

\item employ differential encoding and motion compensation
techniques to remove most redundancy existing between adjacent
pictures;

\item divide the current picture into a number of slices, each of
which is composed of one or more $16\times 16$ macroblocks;

\item decompose each macroblock into 6, 8 or 12 blocks of size
$8\times 8$: 4 luminance blocks; 1, 2 or 4 Cb chrominance blocks; 1,
2 or 4 Cr chrominance blocks;

\item perform DCT (discrete cosine transform) for each
$8\times 8$ block, and then quantize the 64 DCT coefficients with a
quantiser marix;

\item transform the $8\times 8$ block into a 1-D vector in one of
two possible zigzag scanning orders, and then represent all 64
quantized DCT coefficients (except DC coefficients in intra-blocks)
with a number of RLE (run-length encoding) pairs;

\item encode most DCT coefficients (i.e., RLE pairs) and all
motion vectors using VLC (variable-length-coding) codewords under
the control of some Huffman tables, and represent other DCT
coefficients with fix-length bits strings.
\end{enumerate}
A Huffman table is a two-column tale for realizing the Huffman
coding algorithm \cite{Huffman:HuffmanCoding:PIRE1952,
HuffmanCoding}, which is an entropy encoding algorithm and
transforms an input value into a VLC-codeword with the following
rule: the more frequently the input value occurs, the shorter the
corresponding VLC-codeword should be, and vice versa. In such a way,
one can compress the input data in a lossless form. There are in
total 15 Huffman tables used in MPEG-2 standards
\cite{MPEG2-ISOStandard} (less tables are used in MPEG-1 standard
\cite{MPEG1-ISOStandard}), among which ten tables are used to encode
data elements in various headers and the following five tables are
used to encode visual information -- DCT coefficients in each block
and motion vectors in each macroblock:
\begin{itemize}
\item Table B-10: for encoding motion vectors;

\item Table B-12: for encoding the bit size of the differential
values of DC coefficients in intra luminance blocks;

\item Table B-13: for encoding the bit size of the differential
values of DC coefficients in intra chrominance blocks;

\item Table B-14: for encoding all DCT coefficients of non-intra
blocks and AC coefficients of intra blocks with
\textit{intra\_vlc\_format}=0, where \textit{intra\_vlc\_format} is
a picture-specific flag defined in MPEG-2 standard (which is always
set to be 0 for MPEG-1 videos);

\item Table B-15 (not used in MPEG-1 standard): for encoding all AC
coefficients of intra blocks with \textit{intra\_vlc\_format}=1.
\end{itemize}
As an example of the Huffman tables, Table~\ref{table:B12} shows
Table B-12 used in MPEG-2 standard.

\begin{table}[!htbp]
\caption{Table B-12 in MPEG-2 standard: Variable length codes for
\textit{dct\_dc\_size\_luminance}}
\centering \label{table:B12}
\begin{tabular}{c|c}
\hline Variable length code &
\textit{dct\_dc\_size\_luminance}\\
\hline 100 & 0\\
\hline 00 & 1\\
\hline 01 & 2\\
\hline 101 & 3\\
\hline 110 & 4\\
\hline 1110 & 5\\
\hline 11110 & 6\\
\hline 111110 & 7\\
\hline 1111110 & 8\\
\hline 11111110 & 9\\
\hline 111111110 & 10\\
\hline 111111111 & 11\\
\hline
\end{tabular}
\end{table}

The encryption scheme proposed in
\cite{Kankanhalli:VideoScrambler:IEEETCE2002} is designed by
encrypting the original Huffman tables, i.e., using different
(secret) Huffman tables to replace the original ones. The
aforementioned five Huffman tables, B-10, B-12, B-13, B-14 and B-15,
are chosen to be encrypted separately. These secret Huffman tables
are derived from the original ones by combining the following two
encryption operations.
\begin{itemize}
\item \textit{Shuffling VLC-codewords}: grouping all VLC-codewords into several
subsets according to their bit lengths, and then randomly shuffling
these VLC-codewords within each subset.

\item \textit{Random bit flipping}: randomly flipping the last bit
of each VLC-codeword, and adjusting (if needed) other VLC-codewords
to keep the prefix rule valid.
\end{itemize}
After encrypting all the five Huffman tables with both of the above
two methods, the bit length of some VLC-codewords should be slightly
changed to enhance the security against plaintext attacks (as
discussed in Sect.~\ref{section:Introduction} of this paper) but
should not be changed too much, to avoid a large influence on
compression efficiency.

In \cite{Kankanhalli:VideoScrambler:IEEETCE2002}, the key space was
estimated by enumerating all ``good" encryption methods\footnote{An
encryption method is ``good" if it can produce unintelligible
images. Note that the number of ``good" encryption methods may be
larger if a looser definition of ``unintelligible images" is used.}
of the shuffling operation and the random bit flipping operation, as
shown in Table~\ref{table:keyspace}.
\begin{table}[!htbp]
\caption{The number of good encryption methods of each Huffman table
(Table 3.6 of \cite{Kankanhalli:VideoScrambler:IEEETCE2002}).}
\centering \label{table:keyspace}
\begin{tabular}{c|c}
\hline Huffman table & Number of good
encryption methods\\
\hline B-10 & $3!$\\
\hline B-12 & $7!\times 2^6$\\
\hline B-13 & $6!\times 2^8$\\
\hline B-14 & $6!$\\
\hline B-15 & $16!$\\
\hline
\end{tabular}
\end{table}
Then, the key space size was calculated to be the product of the
five numbers given in the table:
\[
(3!)\times\left(7!\times 2^6\right)\times\left(6!\times
2^8\right)\times(6!)\times(16!)\approx 5.37\times 10^{27}\approx
2^{92}.
\]
As a result of the large key space, it was claimed that the scheme
is sufficiently secure. In the next section, we will point out that
this claim is not grounded.

In \cite{Kankanhalli:VideoScrambler:IEEETCE2002}, an additional
measure is also suggested to further enhance the security against
plaintext attacks -- reshuffling the Huffman tables after a certain
number of frames. In the following, we will mainly consider the
basic scheme without the reshuffling mechanism. The effect of the
reshuffling mechanism will be discussed later in
Sect.~\ref{section:Improving}.

\section{Cryptanalysis}
\label{section:Cryptanalysis}

In this section, we re-study the security of the aforementioned
MPEG-video encryption scheme based on secret Huffman tables, and
point out that it is not so secure as claimed in
\cite{Kankanhalli:VideoScrambler:IEEETCE2002}, especially against
the chosen-plaintext attack. In this section, the terms and
notations in MPEG-2 standard \cite{MPEG2-ISOStandard} will be used,
except those existing in MPEG-1 videos only. The following terms are
used throughout this section to facilitate the description: 1) the
term ``picture" is used instead of ``frame", since the encryption
scheme is independent of the syntax differences between a picture
and a frame; 2) macroblock is abbreviated as ``MB"; 3) a
self-defined term ``MB header" is used to denote the set of all data
elements occurring before the first encoded block in an MB (if none
of the blocks is coded, the MB header is the MB itself).

\subsection{Ciphertext-only attack}

The ciphertext-only attack is the most common attack in practice,
since in general the communication channels are open to the public,
which means that an attacker can observe a number of ciphertexts and
use them to break an encryption scheme
\cite{Schneier:AppliedCryptography96, MOV:CyrptographyHandbook1996}.
There are two different goals in a ciphertext-only attack:
recovering the plaintexts and recovering the secret key. The latter
means that the encryption scheme can be completely broken. This
paper mainly focuses on the recovery of the secret key, i.e., the
secret Huffman tables in the MPEG-video encryption scheme under
study.

The simplest ciphertext-only attack is to exhaustively search all
possible keys to find the unique correct one, which is called the
brute-force attack \cite{Schneier:AppliedCryptography96,
MOV:CyrptographyHandbook1996}. Here, a criterion is needed to verify
each searched key. For the MPEG-video encryption scheme under study,
the occurrence of syntax errors can serve as such a criterion for
detecting wrong keys (i.e., wrongly guessed Huffman tables). When a
wrong Huffman table is used to decrypt a cipher-video, syntax errors
may occur in the decoding procedure due to (but not limited to) the
following reasons.
\begin{itemize}
\item
As mentioned in Sect.~\ref{section:Introduction} of this paper, to
ensure the security against plaintext attacks, there are at least
two different bit lengths in a Huffman table. However, once the bit
length of a data element (i.e., the bit length of the corresponding
VLC-codeword) is wrong, all the following data elements in the
current slice cannot be correctly decoded. For example, if
$dct\_dc\_size$\footnote{Italic symbols mean data elements defined
in the MPEG-2 standard, or in the MPEG-1 standard if it does not
defined in the MPEG-2 standard. For example, here ``$dct\_dc\_size$"
denotes the bit size of a DC differential value, as defined in Sect.
7.2.1 of \cite{MPEG2-ISOStandard}.} is not decoded correctly in an
intra-block, all the following data elements in the current slice
cannot be correctly located and decoded.

\item
For each Huffman table, not all VLC-codewords are valid. For
example, in Table B-10, all VLC-codewords have less than 7 zero bits
and the prefix ``0000 0010" never occurs.

\item
There always exist 23 continuous zero bits between two adjacent MBs.

\item
There may exist some marker bits (must be ``1") in the bit stream:
\begin{itemize}
\item
(not valid for MPEG-1 videos) when $concealment\_motion\_vectors=1$
in an intra-block, there exists a marker bit in the MB header;

\item
(for MPEG-1 videos only) in D-picture, the last bit of each MB must
be a marker bit named $end\_of\_macroblock$.
\end{itemize}

\item
There exist some constraints on the decoded data elements:
\begin{itemize}
\item
each decoded DCT coefficient should not be out of the range
$[-2048,+2047]$ after quantization;

\item
each decoded motion vector should not be out of the range defined in
Table 7-8 of the MPEG-2 standard \cite{MPEG2-ISOStandard}, and must
be within the reference picture after adding the coordinates of the
predicted MB.

\iffalse\item all data elements in an MB should be compliant with
the slice and the picture that contain the MB, for example, in an
I-picture, macroblock\_intra must be 1 and macroblock\_pattern must
be 0.\fi
\end{itemize}

\item
There must be an EOB VLC-codeword at the end of each block, before
which the total number of decoded DCT coefficients must not be
greater than 64.

\item
The number of MBs within each picture should not be greater than a
maximal value.

\item
Some slice headers may be skipped when the video is decoded with
wrong Huffman tables, which is forbidden for most videos (for
example, the MPEG-1 video and the MPEG-2 video with a restricted
slice structure).
\end{itemize}

By detecting the above syntax errors occurring in the decoding
procedure, one can distinguish most wrong Huffman tables. In
addition, there generally exist a lot of information redundancies in
each decoded block, MB, slice, picture and between adjacent blocks,
MBs, pictures and frames. Therefore, even when no syntax error is
detected, one can still distinguish the wrong Huffman table if a
meaningless picture or a number of slices are decoded or if there
exists excessive noise between many adjacent blocks.

Now, let us see how frequently these syntax errors occur. To make
things simpler, denote the average probability of occurrence of a
syntax error at each syntax element by $p$. Then, for a picture with
$L$ syntax elements, the probability that at least one syntax error
occurs within this picture will be $P(L)=1-(1-p)^L$. For an MPEG-1
video of size $M\times N$, the number of syntax elements is about
$6MN\lambda$, where $\lambda$ is a factor determined by the average
number of syntax elements in each block and ranges roughly from
$1/64$ to 1. As an example, taking $M=176$, $N=144$, $\lambda=1/64$
and $p=0.001$, one can easily calculate and obtain $L=2376$ and
$P(L)\approx 0.9072$. Since the value of $\lambda$ is generally
larger than $1/64$ and the value of $p$ might not be so small, it is
generally a high-probability event to observe at least one syntax
error within one MPEG-picture. Note that in reality the values of
$p$ and $\lambda$ vary in a wide range due to the following reasons:
1) there are a lot of possibilities of encoding a video within the
framework of MPEG standards; 2) there are some optional data
elements in MEPG standards; 3) the occurrence of some kinds of
syntax elements depends on the contents of the encoded blocks or
other syntax elements; 4) different blocks correspond to different
distributions of DCT coefficients, which directly influence the
values of $\lambda$ and $p$; 5) different Huffman tables (especially
these short VLC-entries) correspond to different value of $p$.
Therefore, instead of estimating the values of $p$ and $L$, the
efficiency of the syntax-error detection process will be shown by
carrying out experiments on some sample videos.

Because the five Huffman tables are used for different parts of the
whole video bit-stream, it is possible to separately guess them one
by one. This means that one can use the so-called divide-and-conquer
(DAC) attack \cite{Schneier:AppliedCryptography96,
MOV:CyrptographyHandbook1996} to break the MPEG-video encryption
scheme. In other words, the key space of the encryption scheme will
be the \textbf{\em sum}, not the \textbf{\em product}, of the
sub-spaces of the five tables. Next, let us see how to separately
break the five Huffman tables by detecting syntax errors in the
video decoding procedure.

\subsubsection{Reconstructing Table B-10}

Following the MPEG-2 standard, Tables B-12/13/14/15 are all
independent of the decoding of the first MB header in a
slice\footnote{All other MBs cannot be located without knowing
Tables B-12/13/14/15.}, which makes the separate reconstruction of
Table B-10 possible. When a wrong Table B-10 is used, the following
syntax errors may occur when the first MB header of a slice is
decoded.
\begin{itemize}
\item
Some decoded motion vectors may be invalid, especially for those MBs
near the picture edge.

\item When $concealment\_motion\_vectors=1$ in an intra-block, the
marker bit in the MB will be wrong (i.e., equal to 0) with a
probability of 0.5 (under the assumption that each bit in the video
stream is distributed uniformly).

\item
When $macroblock\_pattern=1$, ``0000 0000 0" never occurs in
$coded\_block\_pattern$ encoded by Table B-9.
\end{itemize}
Note that in each slice only the first MB header can be used to
detect syntax errors about Table B-10, so the average number of
involved syntax elements in each block (i.e., the value of $\lambda$
corresponding to this table) may be too small, especially for
pictures with a small number of slices and/or slow motion. When such
an event happens, one has to exhaustively search through Table B-10
and other Huffman tables. Experiments showed that this event really
happened for many MPEG videos.

\subsubsection{Reconstructing Table B-14}

Since all DCT coefficients in a non-intra MB are encoded with Table
B-14, syntax errors may occur when continuous non-intra MBs in a
slice are decoded with a wrong Table B-14. Because most MBs in a
P/B-picture are non-intra MBs, the occurrence probability of syntax
errors (i.e., the value of $p$ corresponding to this table) will be
relatively high.

To test how frequently syntax errors of this kind occur in real
attacks, we observed the decoding process by exchanging the
following two VLC-entries in Table B-14 -- ``11s" and ``011s", which
represent RLE-codewords (0,1) and (1,1), respectively\footnote{The
two VLC-codewords were chosen due to their frequent occurrence in
the MPEG-1/2 video stream.}. For a large number of test MPEG-1/2
videos, syntax errors started to occur after a few number of MBs
were decoded. See Fig.~\ref{figure:BreakingB14} for the decoding
results of an MPEG-1 video ``Carphone" (of size $176\times 144$) and
an MPEG-2 video ``Tennis"\footnote{The 1st picture of ``Tennis" is
encoded with $intra\_vlc\_format=1$, while the 2nd picture with
$intra\_vlc\_format=0$.} (of size $704\times 576$). If the whole
Huffman table is heavily shuffled, syntax errors will occur even
more frequently.

\newlength\sfigwidth
\setlength\sfigwidth{0.24\textwidth}

\begin{figure}[!htbp]
\centering
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Carphone2}
a)
\end{minipage}
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Carphone2_B14_raw}
b)
\end{minipage}
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Tennis2}
c)
\end{minipage}
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Tennis2_B14_raw}
d)
\end{minipage}
\caption{The decoded results of an MPEG-1 video ``Carphone" and an
MPEG-2 video ``Tennis", when only two VLC-codewords were exchanged
in Table B-14: a) the 2nd picture of ``Carphone"; b) the decoded 2nd
picture of ``Carphone"; c) the 2nd picture of ``Tennis"; d) the
decoded 2nd picture of ``Tennis". The light grey areas in the
decoded frames denote decoding failures caused by syntax errors (the
same hereinafter). Note that the decoded pictures are displayed as
raw data (i.e., the differential pictures) since the reference
I-pictures are normally unknown at this stage.}
\label{figure:BreakingB14}
\end{figure}

\subsubsection{Reconstructing Table B-12}

Once Table B-14 is reconstructed, Table B-12 can be further
exhaustively searched in intra MBs with $intra\_vlc\_format=0$. If
the attacker can get at least one MPEG-1 cipher-video, Table B-12
can always be broken separately (Table B-15 is not used in MPEG-1
videos, which means $intra\_vlc\_format=0$). If all intra MBs in all
known plain-videos are encoded with $intra\_vlc\_format=1$, Table
B-12 has to be exhaustively searched together with Table B-15 (see
below), which is generally a rare event when an attacker can collect
a number of cipher-pictures to carry the ciphertext-only attack.

In the case that only two VLC-codewords, ``00" and ``01", in Table
B-12 were swapped, we tested the decoding results of some MPEG-1/2
videos. Figure~\ref{figure:BreakingB12} gives the results of the
MPEG-1 video ``Carphone" and the MPEG-2 video ``Tennis". One can see
that the syntax errors still occur very frequently. Note that the
swapped VLC-codewords have the same bit length, so a stronger
shuffling of Table B-12 shall cause much more syntax errors.

\begin{figure}[!htbp]
\centering
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Carphone1}
a)
\end{minipage}
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Carphone1_B12}
b)
\end{minipage}
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Tennis1}
c)
\end{minipage}
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Tennis1_B12}
d)
\end{minipage}
\caption{The decoded results of the MPEG-1 video ``Carphone" and the
MPEG-2 video ``Tennis", when only two VLC-codewords were exchanged
in Table B-12: a) the 1st picture of ``Carphone"; b) the decoded 1st
picture of ``Carphone"; c) the 1st picture of ``Tennis"; d) the
decoded 1st picture of ``Tennis".} \label{figure:BreakingB12}
\end{figure}

\subsubsection{Reconstructing Table B-15}

If Table B-12 has been successfully guessed, Table B-15 can be
exhaustively searched in luminance blocks of intra MBs with
$intra\_vlc\_format=1$, just like the case of reconstructing Table
B-14. If Table B-12 cannot be separately broken, Tables B-12 and
B-15 have to be exhaustively searched together.

By swapping ``10s" and ``010s", which represent (0,1) and (1,1),
respectively, in Table B-15, we tested the decoding results of some
MPEG-2 videos (note that this table is not used in the MPEG-1
standard). Figure~\ref{figure:BreakingB15} gives the results of the
MPEG-2 video ``Tennis". It can be seen again that many syntax errors
still occur.

\begin{figure}[!htbp]
\centering
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Tennis1}
a)
\end{minipage}
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Tennis1_B15}
b)
\end{minipage}
\caption{The decoded result of the MPEG-2 video ``Tennis", when only
two VLC-codewords were exchanged in Table B-15: a) the 1st picture
of the original video; b) the decoded 1st picture.}
\label{figure:BreakingB15}
\end{figure}

\subsubsection{Reconstructing Table B-13}

After Tables B-12, 14 and 15 are broken, Table B-13 can be
exhaustively searched in chrominance blocks of intra MBs. If there
are intra MBs with $intra\_vlc\_format=0$, Table B-13 can be
exhaustively broken immediately after Table B-14 is broken, without
knowing Table B-15.

By exchanging two VLC-codewords, ``01" and ``10", in Table B-13, we
tested the decoding results of some MPEG-1/2 videos. The results
corresponding to the MPEG-1 video ``Carphone" and the MPEG-2 video
``Tennis" are shown in Fig.~\ref{figure:BreakingB13}. Again, many
syntax errors can be observed. Due to a similar reason in the case
of Table B-12, even more syntax errors are expected in a real
shuffling of Table B-13.

\begin{figure}[!htbp]
\centering
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Carphone1}
a)
\end{minipage}
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Carphone1_B13}
b)
\end{minipage}
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Tennis1}
c)
\end{minipage}
\begin{minipage}{\sfigwidth}
\centering
\includegraphics[width=\textwidth]{Tennis1_B13}
d)
\end{minipage}
\caption{The decoded results of the MPEG-1 video ``Carphone" and the
MPEG-2 video ``Tennis", when only two VLC-codewords were exchanged
in Table B-13: a) the 1st picture of ``Carphone"; b) the decoded 1st
picture of ``Carphone"; c) the 1st picture of ``Tennis"; d) the
decoded 1st picture of ``Tennis".} \label{figure:BreakingB13}
\end{figure}

Finally, based on the above analysis and experimental results, let
us estimate the complexity of the above DAC attack under four
different conditions as follows:
\begin{itemize}
\item \textit{when Table B-10 is separately reconstructed}:
\begin{itemize}
\item \textit{when Table B-12 is separately searched}:
$(3!)+(7!\times 2^6)+(6!\times 2^8)+(6!)+(16!)\approx 2^{44.3}$;

\item \textit{when Table B-12 is searched together with Table
B-15}: $(3!)+(7!\times 2^6)\times(16!)+(6!\times 2^8)+(6!)\approx
2^{62.5}$;
\end{itemize}

\item \textit{when Table B-10 is not separately reconstructed}:
\begin{itemize}
\item \textit{when Table B-12 is separately searched}:
$(3!)\times((7!\times 2^6)+(6!\times 2^8)+(6!)+(16!))\approx
2^{46.8}$;

\item \textit{when Table B-12 is searched together with Table
B-15}: $(3!)\times((7!\times 2^6)\times(16!)+(6!\times
2^8)+(6!))\approx 2^{65.1}$.
\end{itemize}
\end{itemize}
One can see that in all cases the complexity will be much smaller
than the one given in \cite{Kankanhalli:VideoScrambler:IEEETCE2002}:
$(3!)\times(7!\times 2^6)\times(6!\times
2^8)\times(6!)\times(16!)\approx 2^{92}$. Considering that Table
B-12 can be separately searched in most cases, this Huffman table
based encryption can be easily broken with a practically small
complexity.

As discussed above, since each picture of a cipher-video contains a
large number of VLC data elements, syntax errors about Tables B-12,
B-13, B-14 and B-15 will generally occur in each picture with a
relatively high probability. That is, except Table B-10, all other
Huffman tables can be separately broken in most cases, where note
that Table B-10 makes the smallest contribution to the whole key
space among all the five tables. So, it is expected that only a few
number of cipher-pictures (or even a few number of consecutive
cipher-slices) is enough to carry out the above DAC attack
effectively.

\subsection{Partial-key attack}

There exists another serious defect in the MPEG-video encryption
scheme under study: with a partially-recovered key (i.e., partial
entries of the Huffman tables), it is still possible to decrypt a
cipher-video, if this cipher-video does not contain any undetermined
entries in the Huffman tables. For example, if the ``Escape" entry
in Table B-14 or B-15 is not reconstructed, one can still use the
partially-reconstructed Huffman tables to decrypt a cipher-video
that does not contain Escape DCT coefficients. Thus, the complexity
of finding a practicable Huffman table is generally smaller than the
complexity of exactly recovering the whole Huffman table itself,
where the word ``practicable" means that a partially-reconstructed
Huffman table can be used to decrypt some specific target
ciphertexts, though not all possible ciphertexts.

Furthermore, Table B-15 is a very special Huffman table, since it
never occurs in MPEG-1 videos and may not occur in some MPEG-2
videos as well. So, Table B-15 can be simply neglected when breaking
such videos, which means that Table B-12 can always be searched
separately. In this case, the key space under the DAC
ciphertext-only attack becomes even smaller:
\begin{itemize}
\item \textit{when Table B-10 is separately reconstructed}:
$(3!)+(7!\times 2^6)+(6!\times 2^8)+(6!)=507606\approx 2^{19.0}$;

\item \textit{when Table B-10 is not separately reconstructed}:
$(3!)\times((7!\times 2^6)+(6!\times 2^8)+(6!))=3045600\approx
2^{21.5}$.
\end{itemize}
One can see that the key space is so small that it is even possible
to find the secret Huffman tables within seconds on a PC with a 1GHz
CPU (note that 1G$=2^{30}\gg 2^{21.5}$).

\subsection{Chosen-plaintext attack}

The chosen-plaintext attack is a very strong attack, in which one
can (intentionally) choose some plaintexts and observe the
corresponding ciphertexts to break an encryption scheme
\cite{Schneier:AppliedCryptography96, MOV:CyrptographyHandbook1996}.
With the help of some chosen plaintexts and ciphertexts, it is
possible to directly determine the secret Huffman tables without
exhaustively guessing them in all possible candidates. In the
following, we show how to choose the data elements in a plain-video
to carry out a successful chosen-plaintext attack.

\subsubsection{Reconstructing Table B-10}

Choose a P/B-picture so that all MBs are encoded as ``Not Coded",
i.e., only MB headers occur in this picture and all blocks are
skipped. Given any two MBs in a slice, one can easily locate the 23
zero bits between the two MBs and all data elements occurring before
motion vectors in the first MB header. Note that the data elements
in the second MB header can be intentionally chosen to facilitate
such a locating procedure. Then, one can extract a bit segment from
the first MB header, which is composed of two or four motion
vectors. In the extracted bit segment, the values of
$motion\_residuals$, dmvectors and the sign bits of the motion
vectors can be chosen to uniquely distinguish each $motion\_code$,
i.e., each VLC-codeword encoded with the secret Table B-10. If
necessary, $f\_code[r][s]$ can also be intentionally chosen to help
the extraction of the VLC-encoded $motion\_codes$. By choosing the
values of 17 consecutive $motion\_codes$ to be 0, ..., 16,
respectively, all entries in Table B-10 can be uniquely determined.
Apparently, to completely break Table B-10, only a few MBs (not a
full picture) are needed.

\subsubsection{Reconstructing Table B-14}

After reconstructing Table B-10, one can continue to break Table
B-14 in non-intra MBs. The entries in Table B-14 can be
reconstructed as follows:
\begin{itemize}
\item
\textit{EOB and Escape entries}: At the beginning of the first MB in
a slice, choose the following two plain-blocks (in the zigzag
scanning order, the same hereinafter): block \#1 --
``$\overbrace{0,\cdots,0}^{run_e}$, $level_e$, 0, $\cdots$", block
\#2 -- ``$\overbrace{0,\cdots,0}^{run_e}$, $-level_e$, 0, $\cdots$",
where $(run_e,level_e)$ forms an Escape RLE-codeword (i.e., not a
valid entry in Table B-14). Then, the video bitstream corresponding
to the two plain-blocks will be: ``Escape, $run_e$, $level_e$, EOB,
Escape, $run_e$, $-level_e$, EOB". By choosing $run_e$, $level_e$ to
be some special values and locating the two fixed-length bit
strings: ``$run_e$, $level_e$" and ``$run_e$, $-level_e$", it is
easy to determine the Escape and EOB VLC-codewords of Table B-14.

\item
\textit{Other entries}: Choose a block with two RLE-codewords:
``$\overbrace{0,\cdots,0}^{run}$, $level$,
$\overbrace{0,\cdots,0}^{run_e}$, $level_e$, 0, $\cdots$" where
$(run,level)$ is a valid entry in Table B-14 and $(run_e,level_e)$
is an Escape RLE-codeword. By choosing $(run_e,level_e)$ properly,
one can easily extract the VLC-codeword of $(run,level)$ from the
bit stream. Repeating this process for all RLE-codewords in Table
B-14, one can completely recover the whole Table B-14.
\end{itemize}
In the above reconstruction process, the number of required blocks
is equal to the number of entries in Table B-14, which means only
tens of MBs.

\subsubsection{Reconstructing Tables B-12 and B-13}

Since AC coefficients of intra-blocks are encoded in a similar way
to the motion vectors, the method of reconstructing Table B-10 can
also be used to break Tables B-12 and B-13. To break the entry
corresponding to $dct\_dc\_size=s$, choose an intra-block as
follows: ``$level$, $\overbrace{0,\cdots,0}^{63}$", where $level$
has $s$ significant bits. Then, the video bitstream corresponding to
this block will be ``$dct\_dc\_size$, $dc\_dct\_differential$, EOB".
Since EOB and $dc\_dct\_differential$ are both known, it is easy to
determine the VLC-encoded $dct\_dc\_size$. Given 12 luminance blocks
with $s=0\sim 11$, Table B-12 can be completely reconstructed.
Similarly, given 12 chrominance blocks with $s=0\sim 11$, Table B-13
can be completely reconstructed. Apparently, the number of required
chosen MBs is 3, 6 or 12 according to the value of $chroma\_format$
(4, 2 or 1).

\subsubsection{Reconstructing Table B-15}

After reconstructing Tables B-12 and B-13, one can break Table B-15
by choosing some intra-blocks, in the same way of reconstructing
Table B-14.

As a whole, one can see that only tens of chosen MBs are enough to
break all the five secret Huffman tables. When the picture is not
too small, this means that only one chosen picture is enough to
break the whole encryption scheme. So the MPEG-video encryption
scheme is very weak against chosen-plaintext attack.

\subsection{Known-plaintext attack}

The known-plaintext attack is a weak version of chosen-plaintext
attack, in which one can only passively observe a number of
plaintexts and the corresponding ciphertexts to break an encryption
scheme \cite{Schneier:AppliedCryptography96,
MOV:CyrptographyHandbook1996}.

Apparently, if some chosen blocks mentioned in the above-mentioned
chosen-plaintext attack are observed in a known-plaintext attack,
the corresponding entries in the involved Huffman tables can be
immediately reconstructed. In addition, the FLC (fixed-length
coding) data element following $dct\_dc\_size$ can be used in
known-plaintext attack to uniquely locate $dct\_dc\_size$. This
means that Tables B-12 and B-13 may be reconstructed directly. Also,
the reconstructed VLC-entries in a Huffman table can be used to
locate other undetermined VLC-entries and to detect wrong candidate
entries, which can further reduce the attack complexity. Generally
speaking, the complexity of the known-plaintext attack shall be much
smaller than the complexity of the DAC brute-force attack, though
more plain-MBs are required as compared with chosen-plaintext
attack.

\section{Improving the MPEG-Video Encryption Scheme}
\label{section:Improving}

Though the main focus of this cryptanalysis paper is to point out
some security flaws of the MPEG video encryption scheme proposed in
\cite{Kankanhalli:VideoScrambler:IEEETCE2002}, in this section we
give a brief discussion on how to improve the security of the MPEG
video encryption scheme under study, hoping that more sequential
studies in this research area can be motivated.

To improve the security of the MPEG-video encryption scheme, a
simple way is to change the Huffman tables frequently. In
\cite{Kankanhalli:VideoScrambler:IEEETCE2002}, it was suggested to
reshuffle the Huffman tables after certain number of frames.
Generally speaking, these reshuffling operations might be enough to
provide an acceptable resistance against ciphertext-only attack.
However, even reshuffling these Huffman tables frame by frame is
generally not sufficient for the security against the above
chosen-plaintext attack, since a few number of slices may be enough
to break the secret Huffman tables. From the most conservative point
of view, one has to reshuffle the Huffman tables for each
VLC-codeword. Such a heavy reshuffling process will dramatically
reduce the speed of the whole system and become impractical in many
real applications.

Another possible solution is to use multiple Huffman tables as
suggested in \cite{Wu&Kuo:AudiovisualEncryption:SPIE2001,
Wu&Kuo:EntropyCodecEncryption:SPIE2001,
Xie&Kuo:MHTEncryption:SPIE2003, Wu&Kuo:MHTEncryption:IEEETMM2004}.
As a typical implementation of this kind of MHT-encryption schemes,
a stream cipher (or a secure PRNG) is adopted to determine the
secret Huffman table from multiple candidate tables for each
VLC-codeword. However, as is well known in cryptology, a stream
cipher is not secure against plaintext attacks if the key is reused
to encrypt more than two plain messages. Thus, in real applications,
to further guarantee the security of this MHT-encryption scheme
against plaintext attacks, one of the following practical measures
may be adopted to avoid potential security defects that may arise
from the embedded stream cipher.

\begin{itemize}
\item
\textit{Avoiding reuse of the same secret key to encrypt two videos,
i.e., changing the secret key for different videos}: this measure
has to be used together with a key management system and may not be
very useful in low-cost video applications (such as storage of
private videos in personal computers and mobile devices).

\item
\textit{Assigning a unique ID (UID) for each video (by the
manufacturer or by the end user), and then using the UID to
initialize the stream cipher together with the secret key}: this
measure can be considered as a special case of the above measure,
but it can work without a key management system.

\item
\textit{Using plaintext or ciphertext feedback to make the stream
cipher dependent on the whole plain-video}: this measure will bring
up an error-propagation problem, but can work well in error-free
environments.

\item
\textit{Combining the secret selection of the Huffman tables with a
block cipher to construct a product cipher}: the block cipher should
be sufficiently simple and fast, and can even be insecure when used
separately (for example, with a small block size). This measure may
lead to some new designs of MPEG video encryption schemes and needs
future studies.
\end{itemize}

Finally, note that the security defects about the DAC brute-force
attack and the partial-key attack cannot be essentially avoided even
with the above countermeasures, since they are actually caused by
the inherent feature of an MPEG-video's syntax structure. This
implies that only using secret Huffman tables is not sufficient to
provide an acceptable security level for all MPEG-videos. Some more
powerful techniques, such as secret permutation of DCT coefficients
and encryption of VLC indices
\cite{Zeng:VideoScrambling:IEEETCASVT2002,
Zeng:VideoScrambling:IEEETMM2003, Wu:JointMMEncryption:IEEETIP2006},
have to be introduced to achieve such a goal for MPEG-video
encryption. In future, we will investigate how to combine different
encryption methods to design MPEG-video encryption scheme with high
level of security.

\section{Conclusions}

This paper has analyzed the security of a recently-proposed
MPEG-video encryption scheme, which bases its security of the use of
some secret Huffman tables. As a result, it is found that the scheme
is not sufficiently secure against DAC (divide-and-conquer)
brute-force attack and known-plaintext attack, and is very weak
against the chosen-plaintext attack. Another serious security defect
of this scheme is that a partially-known key may be used to decrypt
some cipher-videos, which further causes a reduction of the key
space. Based on our cryptanalytic results, a brief discussion is
also given on how to further improve the security of the MPEG-video
encryption scheme under study.

\bibliographystyle{IEEEtran}