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 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.