Threshold implementation (TI) is a masking method that provides security against first-order DPA with minimal assumptions on the hardware. It is based on multi-party computation and secret sharing. In this paper, we provide an efficient technique to find TIs for all 3 and 4-bit permutations which also covers the set of 3×3 and 4×4 invertible S-boxes. We also discuss alternative methods to construct shared functions by changing the number of variables or shares. Moreover, we further consider the TI of 5-bit almost bent and 6-bit almost perfect nonlinear permutations. Finally, we compare the areas of these various TIs.