Surface plasmon polaritons are commonly believed to be a future basis for the next generation of optoelectronic and all-optical devices. To achieve this, it is critical that the surface plasmon polariton modes be strongly confined to the surface and have a sufficiently long propagation length and a nanosize wavelength. As of today, in the visible part of the spectrum, these conditions are not satisfied for any type of surface plasmon polaritons. In this paper, we demonstrate that in the ultraviolet range, surface plasmon polaritons propagating along a periodically nanostructured aluminum-dielectric interface have all these properties. Both the confinement length and the wavelength of the mode considered are smaller than the period of the structure, which can be as small as 10 nm. At the same time, the propagation length of new surface plasmon-polaritons can reach dozens of its wavelengths. These plasmon polaritons can be observed in materials that are uncommon in plasmonics such as aluminum. The suggested modes can be used for miniaturization of optical devices.