  Interesting phases of quantum matter often arise when the constituent
particles -- electrons in solids -- interact strongly. Such strongly
interacting systems are however quite rare and occur only in extreme
environments of low spatial dimension, low temperatures or intense magnetic
fields. Here we introduce a new system in which the fundamental electrons
interact only weakly but the low energy effective theory is described by
strongly interacting Majorana fermions. The system consists of an Abrikosov
vortex lattice in the surface of a strong topological insulator and is
accessible experimentally using presently available technology. The simplest
interactions between the Majorana degrees of freedom exhibit an unusual
nonlocal structure that involves four distinct Majorana sites. We formulate
simple lattice models with this type of interaction and find exact solutions in
certain physically relevant one- and two-dimensional geometries. In other cases
we show how our construction allows for the experimental realization of
interesting spin models previously only theoretically contemplated.
