  In theories with a low quantum gravity scale, global symmetries are expected
to be violated, inducing excessive proton decay or large Majorana neutrino
masses. The simplest cure is to impose discrete gauge symmetries, which in turn
make neutrinos massless. We construct models that employ these gauge symmetries
while naturally generating small neutrino masses. Majorana (Dirac) neutrino
masses are generated through the breaking of a discrete (continuous) gauge
symmetry at low energies, e.g., 2 keV to 1 GeV. The Majorana case predicts
\Delta N_\nu \simeq 1 at BBN, neutrinoless double beta decay with scalar
emission, and modifications to the CMB anisotropies from domain walls in the
universe as well as providing a possible Dark Energy candidate. For the Dirac
case, despite the presence of a new light gauge boson, all laboratory,
astrophysical, and cosmological constraints can be avoided.
