To be efficient, data protection algorithms should generally exploit the properties of the media information in the transform domain. In this paper, we will advocate the use of non-linear image approximations using highly redundant dictionaries, for security algorithms. We show that a flexible image representation based on a multidimensional and geometry-based coding scheme, has precious attributes for security information embedding. Redundant expansions provide very good approximation properties, as well as an increased resiliency to coding noise, and a simple stream structure enables easy manipulations. This paper describes simple examples of image scrambling and watermarking applications, based on a Matching Pursuit image coder. It illustrates the very interesting potential of redundant decompositions for data protection and security applications.