  The surfaces of three dimensional topological insulators (3D TIs) are
generally described as Dirac metals, with a single Dirac cone. It was
previously believed that a gapped surface implied breaking of either time
reversal $\mathcal T$ or U(1) charge conservation symmetry. Here we discuss a
novel possibility in the presence of interactions, a surface phase that
preserves all symmetries but is nevertheless gapped and insulating. Then the
surface must develop topological order of a kind that cannot be realized in a
2D system with the same symmetries. We discuss candidate surface states -
non-Abelian Quantum Hall states which, when realized in 2D, have
$\sigma_{xy}=1/2$ and hence break $\mathcal T$ symmetry. However, by
constructing an exactly soluble 3D lattice model, we show they can be realized
as $\mathcal T$ symmetric surface states. The corresponding 3D phases are
confined, and have $\theta=\pi$ magnetoelectric response. Two candidate states
have the same 12 particle topological order, the (Read-Moore) Pfaffian state
with the neutral sector reversed, which we term T-Pfaffian topological order,
but differ in their $\mathcal T$ transformation. Although we are unable to
connect either of these states directly to the superconducting TI surface, we
argue that one of them describes the 3D TI surface, while the other differs
from it by a bosonic topological phase. We also discuss the 24 particle
Pfaffian-antisemion topological order (which can be connected to the
superconducting TI surface) and demonstrate that it can be realized as a
$\mathcal T$ symmetric surface state.
