ABSTRACT The success of AES encryption standard created challenges for the cryptographers to construct
strong substitution-boxes using different underlying approaches. It is because they are solely responsible to
decide the robustness of cryptosystem against linear and differential cryptanalyses. With an aim to fulfill the
mentioned requirement of robustness, a novel group theoretic and graphical method is proposed to construct
S-box with optimal features. Firstly, a strong S-box is generated with the help of orbits of coset graphs
and the action of proposed powerful permutation of symmetric group S256. In addition, a specific group is
designed the action of whose pairs of permutations has the ability to generate as many as 462422016 strong
S-boxes. Few of such proposed S-boxes are reported and assessed against standard performance parameters
to validate the effectiveness of proposed findings. The features of proposed S-boxes are compared with
most of the recent S-boxes to validate the superior performance. Moreover, they are also applied for image
encryption to demonstrate their suitability for multimedia security applications.