Nowadays, multimedia data protection widely uses data hiding technology like Digital Watermarking or steganography. Among the large offer of watermarking techniques several ones are now based on the side information scheme proposed by Costa. These techniques mainly use scalar quantization for embedding a given information. Such solutions have good properties in terms of robustness and capacity but has lack of statistical transparency. In this paper we propose a new watermarking scheme based on a floating quantizer with a fractal structure. The aim of this study is to get rid of the unwanted fluctuations in the probability density function (PDF) of the watermarked signal, caused by the use of a scalar quantizer in the Scalar Costa Scheme approach (SCS). We present here the structure of a Fractal based Costa Scheme (FCS) and detail its performances. Afterwards, we compare the performances of our FCS proposed method with those obtained with the reference SCS. We show that we are able to reduce the statistical distortions obtained with this proposed scheme and keep good robustness properties.