This paper reports on the frictional properties of smooth rubber substrates sliding against rigid surfaces covered with various densities of colloidal nano-particles (average diameter 77 nm). Friction experiments were carried out using a transparent Poly(dimethyl siloxane) (PDMS) rubber contacting a silica lens with silica nano-particles sintered onto its surface. Using a previously described methodology (Nguyen textit{et al.}, textit{J. of Adhesion} textbf{87} (2011) 235-250 ), surface shear stress and contact-pressure distribution within the contact were determined from a measurement of the displacement field at the surface of the PDMS elastomer. Addition of silica nano-particles results in a strong, pressure-independent enhancement of the frictional shear stress as compared to the smooth lens. The contribution of viscoelastic losses to these increased frictional properties is analyzed in the light of a numerical model that solves the contact problem between the rubber and the rough surface. An order-of-magnitude agreement is obtained between experimental and theoretical results, the latter showing that the calculation of viscoelastic dissipation within the contact is very sensitive to the details of the topography of the rigid asperities.