Commonly used encryption methods treat the plaintext merely as a stream of bits, disregarding any specific format that the data might have. In many situations, it is desirable and essential to have the ciphertext follow the same format as the plaintext. Moreover, ciphertext length expansion is also not allowed in these situations. Encryption of credit card numbers and social security numbers are the two most common examples of this requirement. Format-Preserving Encryption (FPE) is a symmetric key cryptographic primitive that is used to achieve this functionality. Initiated by the work of Black and Rogaway (CT-RSA 2002), many academic solutions have been proposed in literature that have focused on designing efficient FPE schemes. However, almost all the existing FPE schemes are based on Feistel construction and have efficiency issues. In this work, we propose a new family of efficient FPE schemes that are Substitution-Permutation (SP) based constructions at their core. We term it as SPF family of FPE schemes. All the underlying SP transformations in these constructions have been defined such that they preserve the format of the data. We then demonstrate an instance of our construction applicable for digits. We show that our scheme is at least 5 times more efficient than existing FPE designs for most of the practical applications. © Springer International Publishing AG 2017.