The threshold implementation method of Substitution box(S-box) has been proposed by Nikova et al. for resisting first-order Differential power attacks with glitches. To lower the time complexity for a threshold implementation of a specific non-linear function, one needs to decompose the function first and then search possible share methods for it. However, the time complexity for this search process is still non-trivial. In this paper, an effective method of searching threshold implementations of4-bit S-boxes is proposed. It mainly consists of two stages.For the decomposing stage, an efficient way of decomposing an S-box is introduced. For the sharing stage, the search complexity is lowered by the technique of time memory trade-off. As a result, threshold implementations of various lightweight block ciphers’ S-boxes are given. Moreover, our method is applied to each 4-bit involutive S-box and some candidates of threshold implementations are presented. The threshold implementation method of Substitution box (S-box) has been proposed by Nikova et al. For resisting first-order Differential power attacks with glitches. To lower the time complexity for a threshold implementation of a specific non-linear function, one needs To decompose the function first and then search possible share methods for it. However, the time complexity for this search process is still non-trivial. In this paper, an effective method of Searching thresholds of 4-bit S-boxes is proposed. It mainly consists of two stages. For the decomposing stage, an efficient way of decomposing an S-box is introduced. For the sharing stage, the search complexity is lowered by the technique of time memory trade-off. various lightweight block ciphers’ S-boxes are given. Furthermore, our method is applied to each 4-bit involutive S-box and some candidates of threshold implementations are presented.