Phonon polaritons (PhPs) are long-lived electromagnetic modes that originate from the coupling of infrared (IR) photons with the bound ionic lattice of a polar crystal. Cubic-boron nitride (cBN) is such a polar, semiconductor material which, due to the light atomic masses, can support high-frequency optical phonons. Here we report on random arrays of cBN nanostructures fabricated via an unpatterned reactive ion etching process. Fourier-transform infrared reflection spectra suggest the presence of localized surface PhPs within the reststrahlen band, with quality factors in excess of 38 observed. These can provide the basis of next-generation IR optical components such as antennas for communication, improved chemical spectroscopies, and enhanced emitters, sources, and detectors.