Privacy preserving data mining and statistical disclosure control have received a great deal of attention during the last few decades. Existing techniques are generally classified as restriction and data modification. Within data modification techniques noise addition has been one of the most widely studied but has traditionally been applied to numerical values, where the measure of similarity is straightforward. In this paper we introduce VICUS, a novel privacy preserving technique that adds noise to categorical data. Experimental evaluation indicates that VICUS performs better than random noise addition both in terms of security and data quality.