  Measurements of the cross-correlation between the extragalactic gamma-ray
background (EGB) and large-scale structure provide a novel probe of dark matter
on extragalactic scales. We focus on luminous red galaxies (LRGs) as optimal
targets to search for the signal of dark matter annihilation. We measure the
cross-correlation function of the EGB taken from the Fermi Large Area Telescope
with the LRGs from the Sloan Digital Sky Survey. Statistical errors are
calculated using a large set of realistic mock LRG catalogs. The amplitude of
the measured cross-correlation is consistent with null detection. Based on an
accurate theoretical model of the distribution of dark matter associated with
LRGs, we exclude dark matter annihilation cross-sections over $\langle \sigma
v\rangle =3\times10^{-25}-10^{-26}\, {\rm cm}^3 \,{\rm s}^{-1}$ for a 10 GeV
dark matter. We further investigate systematic effects due to uncertainties in
the Galactic gamma-ray foreground emission, which we find to be an order of
magnitude smaller than the current statistical uncertainty. We also estimate
the contamination from astrophysical sources in the LRGs by using known scaling
relations between gamma-ray luminosity and star-formation rate, finding them to
be negligibly small. Based on these results, we suggest that LRGs remain ideal
targets for probing dark matter annihilation with future EGB measurement and
galaxy surveys. Increasing the number of LRGs in upcoming galaxy surveys such
as LSST would lead to big improvements of factors of several in sensitivity.
