In this paper, a new encryption scheme with three different modes of operations is proposed based on dual space-filling curves (SFSs) and a fractional wavelet transform (FrWT). This scheme is initially proposed for images and then extended to videos. The core idea behind the proposed schemes is to decompose an image/video first by the FrWT followed by the shuffling of each sub-band coefficients by means of a dual SFC. At last, an inverse FrWT is performed to get the encrypted image/video. A reliable decryption process is also proposed to construct the original image from the encrypted image. The experimental results, security and comparative analysis demonstrate the efficiency and robustness of the proposed scheme. Further, this paper also proposes an efficient implementation of an FrWT based on chaotic maps. © 2011 The Author. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved.